Fibonacci Sum

Computer Science Level 5

Zeckendorf's Theorem states that every positive integer can be written uniquely as a sum of distinct non-neighboring Fibonacci number .

Find the sum of indices (0-indexing) such that their responding Fibonacci terms sums up to 99887766554433221100 .

Clarification :

$F_0 = 1, F_1 = 1$ and so on.
For 10, the answer is $F_5 + F_2 = 8 + 2 = 10$ . Sum of indices is $5+2=7$ .

The answer is 1476.

2 solutions

Beakal Tiliksew
May 27, 2016

The proof of Zeckendorf implies that the Zeckendorf representation can be found by always taking the largest Fibonacci number less than the target number, subtracting it out, and repeating the process.

def largestfib(n):
    count=0
    a,b=1,1
    while True:
        if b>n:
            break
        else:
           a,b=b, a+b
           count+=1
    return [a, count]

larg=99887766554433221100
indexsum=0
while larg>0:
    indexsum+=largestfib(larg)[1]
    larg-=largestfib(larg)[0]
print indexsum

Rushikesh Jogdand
Jul 10, 2016

fib=[1,1]
while fib[-1]<=99887766554433221100:
    fib.append(fib[-1]+fib[-2])
n=99887766554433221100
s=0
for i in range(len(fib)-1,-1,-1):
    if fib[i]<=n:
        s+=i
        n-=fib[i]
print(s)

Fibonacci Sum

The answer is 1476.

2 solutions

0 pending reports