Sequences picoCTF 2022 Solution

Description

1. Step 1

   Read the real recurrence from sequences.py

   Observation

   I noticed the challenge description says the naive recursion 'never finishes,' which suggested the first step is to read the actual script to extract the exact coefficients, base cases, and target index before attempting any optimization.

   sequences.py defines a 4-term linear recurrence of the form M(i) = a*M(i-1) + b*M(i-2) + c*M(i-3) + d*M(i-4). The script uses coefficients 21, 301, -9549, 55692 (so M(i) = 21*M(i-1) + 301*M(i-2) - 9549*M(i-3) + 55692*M(i-4)), base cases 1, 2, 3, 4, and a target index of 20,000,000 (2 * 10^7). Confirm these by reading your downloaded sequences.py - copy the coefficients and the index verbatim, they are the only inputs the solution needs.

   Learn more

   A linear recurrence is a sequence where each term is a fixed linear combination of the previous terms. Fibonacci (f(n) = f(n-1) + f(n-2)) is the 2-term example. This challenge uses a 4-term recurrence with specific integer coefficients written directly in sequences.py.

   The author's recursion recomputes the four predecessors of every term independently, which is exponential: computing the 20-millionth term this way would take longer than the age of the universe. Memoization brings it down to O(n) time and O(n) space, but n = 2 * 10^7 still makes that impractically slow and memory-hungry in pure Python.

   There is no encryption anywhere in this challenge. The flag is simply the printed value of the recurrence at the target index, formatted as the script expects. The entire difficulty is computing that one number fast enough.

2. Step 2

   Compute the nth term with matrix exponentiation

   Observation

   I noticed the target index is roughly 20 million and the recurrence has exactly 4 terms, which suggested encoding the state as a 4x4 companion matrix and using square-and-multiply exponentiation to reduce the O(n) traversal to O(log n) matrix multiplications.

   Encode the recurrence as a 4x4 companion matrix M acting on the state vector [M(i-1), M(i-2), M(i-3), M(i-4)]. Then [M(n), ...]^T = M^(n-3) * [M(3), M(2), M(1), M(0)]^T. Raise M to the power with fast exponentiation. Use Python integers (or gmpy2.mpz for speed) - these are exact integers, so keep full precision and do NOT reduce modulo anything unless sequences.py itself prints a modular result. An alternative is to diagonalize M (P * D^n * P^-1) and clear denominators with a single final division to avoid floating-point rounding; the integer matrix-power approach below sidesteps that issue entirely.

   python

   python3 -c "
   # Fill the coefficients, base cases, and index from sequences.py.
   # Example values shown; confirm them in sequences.py before running.
   # Recurrence: M(i) = c1*M(i-1) + c2*M(i-2) + c3*M(i-3) + c4*M(i-4)
   c1, c2, c3, c4 = 21, 301, -9549, 55692
   base = [3, 2, 1, 0]              # placeholder order; see note below
   init = [1, 2, 3, 4]             # M(0), M(1), M(2), M(3) from sequences.py
   N = 20_000_000                  # target index from sequences.py
   
   def mat_mul(A, B):
       n = len(A)
       C = [[0]*n for _ in range(n)]
       for i in range(n):
           for k in range(n):
               if A[i][k]:
                   aik = A[i][k]
                   row = B[k]
                   Ci = C[i]
                   for j in range(n):
                       Ci[j] += aik * row[j]
       return C
   
   def mat_pow(M, p):
       n = len(M)
       R = [[1 if i==j else 0 for j in range(n)] for i in range(n)]  # identity
       while p:
           if p & 1:
               R = mat_mul(R, M)
           M = mat_mul(M, M)
           p >>= 1
       return R
   
   # Companion matrix: state [M(i-1), M(i-2), M(i-3), M(i-4)] -> [M(i), ...]
   M = [
       [c1, c2, c3, c4],
       [1,  0,  0,  0],
       [0,  1,  0,  0],
       [0,  0,  1,  0],
   ]
   
   # State vector at i=3 is [M(3), M(2), M(1), M(0)]
   state = [init[3], init[2], init[1], init[0]]
   P = mat_pow(M, N - 3)
   val = sum(P[0][j] * state[j] for j in range(4))
   print('M(N) =', val)
   # Format exactly as sequences.py does to read the flag.
   "

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Replace the recursion with a memoized version using functools.lru_cache or a dictionary cache to store already-computed terms

   Memoization brings the call tree from exponential down to O(n), but n is 20,000,000. In pure Python this means 20 million function calls and a dictionary with 20 million entries, which exhausts memory and takes several minutes to finish. Matrix exponentiation is the correct approach because it completes in O(log n) matrix multiplications - about 24 iterations - regardless of how large n is.

   Tried: Add a 'mod 2**64' or similar modular reduction inside mat_mul to keep intermediate integers small and speed up the multiplication

   The sequences.py script prints the exact integer value of the recurrence term and formats it directly into the flag. If you reduce modulo anything that sequences.py does not also reduce by, your final value will be a residue, not the true term, and the formatted flag will be wrong. Only reduce modulo p if sequences.py itself contains a 'mod p' or '% p' expression in its flag-printing line.

   Learn more

   The key identity: the recurrence M(i) = c1*M(i-1) + c2*M(i-2) + c3*M(i-3) + c4*M(i-4) is a single linear map on the state vector. Stacking it gives [M(i), M(i-1), M(i-2), M(i-3)]^T = M * [M(i-1), M(i-2), M(i-3), M(i-4)]^T, where the first row of the 4x4 matrix holds the coefficients and the subdiagonal shifts the state down.

   By induction, applying the map n - 3 times from the base state gives the answer: state(n) = M^(n-3) * state(3). Computing M^(n-3) with square-and-multiply costs only O(4^3 * log n) integer multiplications, which is instant even for n = 2 * 10^7.

   Two implementation notes: (1) these are exact integers and they grow large, so use Python's arbitrary-precision ints (or gmpy2.mpz to speed up the big multiplications); (2) double-check the index convention in sequences.py (0-based vs 1-based, and exactly which term is requested) and adjust the N - 3 exponent and the starting state to match.

3. Step 3

   Format the computed value as the flag

   Observation

   I noticed the description says 'the flag is the formatted value the script prints' with no separate decryption step, which suggested that sequences.py already contains the flag-printing logic and the only remaining action is to feed the computed integer back into that exact formatting.

   Once the matrix power finishes, sequences.py formats the computed term into the flag. Apply the exact formatting the script uses (string conversion / wrapping in picoCTF{...} as written in the file) and submit. There is no XOR, AES, or any other decryption - the flag is the number itself, formatted.

   Learn more

   The challenge tests one thing: knowing that linear recurrences reduce to matrix exponentiation (or matrix diagonalization), which collapses an intractable O(exp) or O(n) computation down to O(log n). The flag derivation is whatever printing/formatting sequences.py already contains - typically the integer value placed into the flag wrapper.

   Matrix exponentiation for linear recurrences is a staple of competitive programming and shows up across many CTF problems in disguise: Fibonacci variants, tiling counts, and path-counting in graphs all reduce to raising a transition matrix to a power. Recognizing the pattern is the transferable skill here.

Flag

The flag is the recurrence value at the target index (around the 20-millionth term), formatted exactly as sequences.py prints it. Compute it with matrix exponentiation (or matrix diagonalization) in O(log n) time. Read the exact coefficients, base cases, and index from your downloaded sequences.py. No decryption is involved.