Prove that in the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the two previous) there's at least one number that ends in 999999.
If the numbering is such that F(0)=0 and F(1)=1, then F(1,499,998) and every 1.5 millionth Fibonacci number after that ends in 999999, but just the one was necessary as an existence proof. This was found by
DEFLNG AZ
first = 0
second = 1
fibNo = 1
DO
nxt = (first + second) MOD 1000000
first = second: second = nxt
fibNo = fibNo + 1
IF nxt = 999999 THEN
PRINT fibNo, nxt
END IF
LOOP
which gave (before being stopped):
1499998 999999
2999998 999999
4499998 999999
5999998 999999
7499998 999999
8999998 999999
10499998 999999
11999998 999999
Now if someone can prove the existence without brute force, that would be great.
Edited on June 15, 2004, 3:19 pm

Posted by Charlie
on 20040615 14:26:26 