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 A-Z
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 2004-06-15 14:26:26