Sum of Fibonacci numbers

Question

I found this task here.

Given the ith (1<=i<=35) Fibonacci number F(i) calculate the sum of the ith till i+9th number F(i)+F(i+1)+...+F(i+9) and the last digit of the i+246th one F(i+246)

I have been trying to solve this using python and some tricks(Binnet's formula and a tricky recurrence):

 f=lambda n:((1+5**.5)**n-(1-5**.5)**n)/(2**n*5**.5)
 exec"n=input();print int(55*f(n)+88*f(n+1)+f(n+6)%10);"*input()

but I didn't yet managed to squeeze thought the give source code limit which is 111 and mine is 115,any hints how to improve my solution?

I am a rather newbie to python so any sort of help resulting in a successful solution will be much appreciated.

Thanks,

PS:After posting the same question in stackoverflow I thought that this should be more appropriate here as this site is precisely for Puzzles and Codegolf.

Answer 1

GolfScript 28 26 characters

Since the problem is here we might as well golf it. Anyone who plan on participating on spoj.pl better close their eyes while they read this.

~](;{11.@5+{.@+}*;.10%+n}%

It basically says: For all input, start with the numbers 11 and 11, do input+5 Fibonacci iterations, discard the highest of the two results, add itself mod 10 to the lowest result, done. As a formula this can be describes as 11*Fib(input+6) + (11*Fib(input+6)) mod 10.

Why does this work? It is simply a condensed way of calculating two second identities in the same run, one could start at [0 1] and [55 89], do a run on both of the same length and subtract the first result from the second to get the sum of a series of 10 Fibonacci numbers, but one may as well do the subtraction on the initial sets, thus getting the set [55 88], that can be stepped back a few steps to [11 11] which is short to write.

The Fibonacci series mod 10 has a period of 60, so Fib(i+246) mod 10 = Fib(i+6) mod 10.

Answer 2

Python, 99 98 93 characters

F=[0,1]
exec'F+=[F[-2]+F[-1]];'*300
exec'G=F[input():];print sum(G[:10])+G[246]%10;'*input()

Answer 3

Perl, 78

sub F{$c=shift;$c>1?F($c-2)+F($c-1):$c}$_=<>;$x=F($_+11)-F($_+1);print$x+$x%10

This makes use of my observation that

• the sum of F(i) to F(i+9) is equal to F(i+11) − F(i+1) — proof:

     F(i) + F(i+1) + F(i+2) + F(i+3) + F(i+4) + F(i+5) + F(i+6) + F(i+7) + F(i+8) + F(i+9)
  =      F(i+2)    +     F(i+4)      +     F(i+6)      +     F(i+8)      +    F(i+10)
  =      F(i+2)    - F(i+3) + F(i+5) +     F(i+6)      +     F(i+8)      +    F(i+10)
  =           -F(i+1)       +      F(i+7)              +     F(i+8)      +    F(i+10)
  =           -F(i+1)       +              F(i+9)                        +    F(i+10)
  =           -F(i+1)       +                           F(i+11)
  

• F(i+246) mod 10 is equal to (F(i+11) − F(i+1)) mod 10 (discovered by experimentation; no idea how to prove this)