Is there Fibonacci number with last digits An = ..99..99 [1000 nines]?

Question

Fibonacci secuence is defined as A_n = A_(n-1) + A_(n-2):

1, 1, 2, 3, 5, 8,.....

Here is a hint for you, Martin.

Do not try to keep all digits, just leave compute the last 3 or 4 digits. Because the last digits of the sum depend only on the last digits of the operands. If I recall it correctly in basic it is done something like this:

A3 = A1 + A2 mod 1000
A1 = A2
A2 = A3

Try to run it and see if 999 is there.

Answer 1

Yes, it does.

If we consider the fibonacci numbers modulo m (in this case, m = 10^1000), then we are asking whether -1 (== m-1) occurs somewhere in the sequence.

First note that knowing any two consecutive numbers in the sequence completely determines the rest of the sequence, since we can go forward by adding, and backward by subtracting (it is convenient to consider the sequence as extending backwards indefinitely in this case).

But modulo m, there are only m^2 possible ways to pick the two consecutive numbers, which means that these pairs must start to repeat somewhere.

Now, the classical sequence starts as 0,1,1, etc. (I've added the zero behind). By the argument above, this will appear somewhere later on as well (don't know exactly where).

Now start extending this backwards. We know that the number before has to be 1 (since we have to add it to 0 to get 1).

Then we have 1,0,1,1.

But what can come before this? It's -1. So there is definitely some fibonacci number that ends in 1000 nines (this is true for any number of nines).

Answer 2

I wrote a computer program to display all these fibonacci numbers, and although the program was only about 10 lines long, quite short, what it displayed supprised me. It only displayed 45 numbers before the numbers got so huge that they caused an overflow error. the 45th number displayed was 1836311903, which is nearly 2 billion. So to find out if there is a fibonacci number ending in all those 9`s would require a computer program that uses many many bytes to store all the digits, the program I wrote just used a single variable, which was why I only got the first 45 numbers. The fibonacci numbers though get rarer and rarer as the numbers get bigger, so I very much doubt if there is such a number that consists of only 9`s. By the way I set up the array to calculate 2000 numbers, so was quite disapointed when the program only gave me 45 numbers.

Answer 3

Hmmm let's look at the first few:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610... it sort of looks like we might hit all remainders mod 10^n

I guess another way to go at this is to look at the closed form for fibonacci numbers (1/root5)*[(1 + root5)/2]^n - (1/root5)*[(1 - root5)/2]^n ...

Answer 4

Hey, i wrote a computer program also:

the first number to end with a single 9 in the end is
element #12: 89

to end with 99:
#53, 32951280099

to end with 999:
#1499: 517606941956996249658777002798
690079708505906715917116465751
862303123751775090279443954790
285574684207884613780357937681
295556889276956316403838802325
435841449277090817151139862267
793126965367311785578469123467
889110011946793807157460260551
783045362164182187703788927673
583820016960118723560163036004
9131029846999

to end with 9999:
#14999: It's really quite long... :) (about 7 times as long as the previous one), so I will spare you.

to end with 99999: #149999
to end with 999999: #1499999
to end with 9999999: #14999999

and so on...

hey Martin, way to go Java, now isn't it! :)

so this does look like a pattern...


now as far as the proof that number must exist,

first we know that Sumudu's proof doesnt work :( counter-example: look at the sequence

1, 4, 7, 10, 13, ...

any two numbers determine the entire sequence, and if we're looking at modulo 3, there
are only 3^2 = 9 ways to pick two consecutive numbers, nevertheless no member of the
sequence X ever produces X modulo 3 = 0.

Now as far as a proof that works, i really have no idea... Gotta refresh my memory as far as groups theory, cyclic rings etc. - stay on hold...