# BCTF 2015 experiment (English version)

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.
$nc 104.197.7.111 13135 According to the description, we can get flag after solving 50 questions. It seems easy, isn't it? First 10 are questions judging the answer is integer or not. Then, problems changed to asking about a sequence. Description: The prime numbers. The sequence starts with: 2,3,5,7,11,13,17,19,23,29 (first term is for n = 1) n = 2418, Answer: First several are fixed problems, but others are random. We are given about 2 minutes, so we have enough time to solve it. The sequence are found in THE ON-LINE ENCYCLOPEDIA OF INTEGER SEQUENCES with the very same description. I calculated the number based on it many times, then I noticed that the answer was in the calculated table in LINKS section. Last 5 questions, we couldn't solve with the same way! Luckily, they are fixed problems but needed little long time to find the answer. Q46: Prime number (n is over 20 million) Q47: Very large Catalan number Q48: Number of sets of rooted connected graphs where every block is a complete graph. Q49: Shapes of height-balanced AVL trees with n nodes. Q50: a(n) = number of partitions of n (the partition numbers) modulo 1000000007 Although I couldn't understand the means of Q48-50, I copy-and-pasted expressions to Pari/GP and Mathematica and made my computer work hard. Q46 ? prime(23338403) %1 = 439756091  Q48 etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 700}]  Q49 a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, Expand[x+B[x^2+2*x*y, x, d, a+b, a]], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; a Expand function is a very important technique. Without it, this calculation took very very long time and the question would be time out. Q50 ? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))}; ? a(23370) % 1000000007 %2 = 438545155  Finally, I wrote code below. import re import time import gmpy import sympy import requests from pwn import * s = remote('104.197.7.111', 13135) s.recvuntil("Okay, let's begin with simple questions.\n") problem_number = 1 for _ in range(10): print 'No. %d --------------------------' % problem_number x = s.recvuntil('Answer (yes/no): ') print x m = re.search('Is (.+) an integer or not?', x) expr = m.group(1) try: ans = str(safeeval.expr(expr)) print expr print ans if ('.' not in ans) or re.search(r'\.0+$', ans):
s.send('yes\n')
else:
s.send('no\n')
except:
s.send('no\n')
problem_number += 1

print s.recvuntil('Time for calculating weird integer sequences.')

for i in range(35):
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = s.recvuntil('\n')[:-1]

buf = s.recv(1)
seq = None
if 'T' in buf:
s.recvuntil('starts with: ')
seq = s.recvuntil('\n')[:-1]

print 'Description:', desc
print 'The sequence starts with:', seq
search = 'name:"%s"' % desc
if seq and len(seq) < 40:
search += ' seq:"%s"' % seq

print 'Searching %s' % search
res = requests.get('http://oeis.org/search', params={'q': search})

m = re.search('<a href="/A([0-9]+)"', res.text)
num = m.group(1)
print 'found page:', num

m = re.search(r' = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n

res = requests.get('http://oeis.org/A%s/b%s.txt' % (num, num))
m = re.search('^%d +(-?[0-9]+)' % n, res.text, re.MULTILINE)
if m is None:
else:
ans = int(m.group(1))
s.send(str(ans) + '\n')
problem_number += 1
time.sleep(0.2)

print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
s.send('%s\n' % ans)
problem_number += 1

print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}