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