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[1298]

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
 
    res = s.recvuntil('Answer: ')
    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:
        print 'not found'
        ans = raw_input('Input answer: ')
    else:
        ans = int(m.group(1))
    print 'Answer =', ans
    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')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
ans = raw_input('Input answer: ')
print 'Answer =', ans
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')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
ans = sympy.binomial(2*n, n)/(n+1)
print 'Answer =', ans
s.send('%d\n' % ans)
problem_number += 1
 
s.interactive()

This program works fine once every 3 times. Programming is difficult.

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}