1000-digit Fibonacci number
2014-09-17
Problem 025: 1000-digit Fibonacci number
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn?1 + Fn?2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
Solution:
v
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000001 00000000000000000000000000000000000000000000000001
>5567***00p"2"10p 230p>v
> > 00g40p050p>40g1-40p40g10g%"4"+40g10g/1+g"0"-:40g10g%1+40g10g/1+g"0"-50g++ v
v< v< |g04p+1/g01g04+1%g01g04+"0"p+1/g01g04+"4"%g01g04+"0"%+55p05/+55:<
^<|-*+55"d"-g07g00<|-"0"g+1/g01g07+"4"%g01g07<p070p03+1g03<
>30g.@ >70g1+70p ^
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000001 00000000000000000000000000000000000000000000000001
>5567***00p"2"10p 230p>v
> > 00g40p050p>40g1-40p40g10g%"4"+40g10g/1+g"0"-:40g10g%1+40g10g/1+g"0"-50g++ v
v< v< |g04p+1/g01g04+1%g01g04+"0"p+1/g01g04+"4"%g01g04+"0"%+55p05/+55:<
^<|-*+55"d"-g07g00<|-"0"g+1/g01g07+"4"%g01g07<p070p03+1g03<
>30g.@ >70g1+70p ^
Start
??
Pause
Reset
Output:
Stack: (0)
Explanation:
And for like the 5th time i implement an long addition algorithm. On the right side is the current number and on the left side the last number. The only interesting thing here is probably that I calculate the next number and move the current to the left in a single cycle.
| Interpreter steps: | 745 055 403 |
| Execution time (BefunExec): | 1min 56s (6.37 MHz) |
| Program size: | 123 x 28 |
| Solution: | 4782 |
| Solved at: | 2014-09-17 |