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.


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.

  • \$\begingroup\$ Can you really not factor out 5**.5? \$\endgroup\$ Apr 6 '11 at 12:34
  • \$\begingroup\$ @Peter:Thanks,I missed that somehow :-( \$\endgroup\$
    – Quixotic
    Apr 6 '11 at 12:37
  • 2
    \$\begingroup\$ Don't double post, if the mods on SO judge your question to be better suited for this site they will move it here. \$\endgroup\$ Apr 6 '11 at 14:05
  • 1
    \$\begingroup\$ As for golfing, you are doing it wrong, you don't need the fast formula, you need the short formula, and there is incidentally some extremely short formula to be found for this problem. Binet's is probably longer than the normal recurrence implementation, and if you really must use Binet's you can skip the -(1-5**.5)**n part and just round the result. \$\endgroup\$ Apr 6 '11 at 15:02

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.


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.

  • 2
    \$\begingroup\$ Ehh could you please un-golf in English ?! \$\endgroup\$
    – Quixotic
    Apr 6 '11 at 19:06
  • 1
    \$\begingroup\$ Description is reasonable, use ~] and n}% (or p}%) to save a couple more characters. \$\endgroup\$
    – Nabb
    Apr 8 '11 at 7:54
  • \$\begingroup\$ Thanks, now I wonder why I continue forgetting such simple stuff? \$\endgroup\$ Apr 8 '11 at 10:45
  • \$\begingroup\$ Accepted as you shown a very short procedure. \$\endgroup\$
    – Quixotic
    Apr 8 '11 at 12:57

Python, 99 98 93 characters

exec'G=F[input():];print sum(G[:10])+G[246]%10;'*input()
  • \$\begingroup\$ Could you please explain G=F[input():]? I can understand what it is doing but what I can't is how and why? Thanks, \$\endgroup\$
    – Quixotic
    Apr 6 '11 at 19:09
  • \$\begingroup\$ It just takes the input (i) and grabs a slice of F starting at that input. It is equivalent to doing i=input() then using F[i:i+10] and F[i+246], but a bit shorter. \$\endgroup\$ Apr 6 '11 at 19:41
  • 1
    \$\begingroup\$ If you use Binnet's formula+eBusiness idea you can reach 72 bytes python and with some crazy golfing even 62 bytes. \$\endgroup\$
    – Quixotic
    Apr 10 '11 at 11:35

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)

  • \$\begingroup\$ User mohit would like to see that proof but can not yet comment. \$\endgroup\$ Jun 16 '11 at 16:32
  • \$\begingroup\$ @dmckee, @mohit: Added \$\endgroup\$
    – Timwi
    Jun 16 '11 at 23:32

05AB1E, 10 bytes


Port of @Timwi's Perl answer, so make sure to upvote him as well!

Try it online or verify the first \$[0,n]\$ test cases.

A straight-forward implementation would be 11 bytes instead:


Try it online or verify the first \$[0,n]\$ test cases.


31S          # Push 31 as a list of digits: [3,1]
   b         # Convert both to a binary string: [11,1]
    +        # Add each to the (implicit) input-integer: [i+11,i+1]
     Åf      # Get the n'th Fibonacci number for each: [F(i+11),F(i+1)]
       Æ     # Reduce the pair by subtracting: F(i+11)-F(i+1)
        ¤    # Get its last digit (without popping)
         +   # And add it to the result
             # (after which it is output implicitly)

9Ý           # Push a list in the range [0,9]: [0,1,2,3,4,5,6,7,8,9]
  Ƶ‘         # Push compressed integer 246
    ª        # Append it to the list: [0,1,2,3,4,5,6,7,8,9,246]
     +       # Add each to the (implicit) input-integer: 
             #  [i,i+1,i+2,i+3,i+4,i+5,i+6,i+7,i+8,i+9,i+246]
      Åf     # Get the n'th Fibonacci number for each
        `    # Pop the list, and push all values separated to the stack
         θ   # Pop the last number (the F(i+246)), and only leave its last digit
          O  # Sum all values on the stack
             # (after which the resulting sum is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ƶ‘ is 246.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.