Fibonacci_Not! - 65 (Algorithmic)

Writeup by GenericNickname

Created: 2015-12-08

Problem

What would be a CTF without a typical algorithm problem? This will test your system more than anything. Seeing as the Fibonacci sequence is overused, lets change it slightly shall we?

Given F(x) = G(x) - W(x)

G(x) = [G(x-1)+G(x-2)]^2

W(x) = [W(x-1)]^2 + [W(x-2)]^2

What is the sum of the digits of F(30)?

G(0) = 0 G(1) = 1

W(0) = 0 W(1) = 1

Answer

Overview

Implement the algorithm and calculate the answer.

Details

I chose to use python for this, and simply implemented the math using recursion:

import time,math

def g(x) :
    print x
    if x == 0 : return 0
    if x == 1 : return 1
    a = g(x - 1)
    b = g(x - 2)
    res = (a + b) * (a + b)
    return res

def w(x) :
    print x
    if x == 0 : return 0
    if x == 1 : return 1
    a = w(x - 1)
    b = w(x - 2)
    res = a * a + b * b
    return res

def f(x) :
    return g(x) - w(x)

def sum_digits(n):
    s = 0
    count = 0
    while n:
        s += n % 10
        n /= 10
        count += 1
        print count
    return s

num = f(30)
print sum_digits(num)

Unfortunately, this was taking way too long to run (the number would calculate but python was taking to long to count the digits), so we decided to switch to using sage. The only difference in the sage code was that

num = f(30)
print sum_digits(num)

became

num = f(30)
digits = num.digits()
print len(digits)
print sum(digits)

The sage script, which can be downloaded here finished the calculations in less than a minute. The script told us that the number had 98574916 digits which summed to 443589491, which is correct!

Flag

443589491