Large Fibonacci Numbers Part 3

Number Theory Level 3

$\left ( F(10^1) \bmod 1 \right ) + \left ( F(10^2) \bmod 2 \right ) + \left ( F(10^3) \bmod 3 \right ) + \left ( F(10^4) \bmod 4 \right )$

Let $F(n)$ denote the nth Fibonacci number. What is the value of the expression above?

To clarify: $F(0) = 0, F(1) = F(2) = 1$ are the initials terms of the Fibonacci sequence.

1 solution

David Holcer
Apr 19, 2015

fib=[0,1]
while True:
    fib.append(fib[-1]+fib[-2])
    if len(fib)==10**4+1:
        break
summ=fib[10**2]%2+fib[10**3]%3+fib[10**4]%4
print summ

Note that we need 10^4+1 fibonacci numbers because 0 is the 0th, and we do not subtract one from (e.g fib[10**2]) because 0 is the 0th number.

Can you solve it with only pen and paper?

Chung Kevin - 6 years, 1 month ago