wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Fibonacci number starting with 123456789
        
(Message started by: towr on May 13^th, 2020, 12:59pm)

Title: Fibonacci number starting with 123456789
Post by towr on May 13^th, 2020, 12:59pm

Can you find a Fibonacci number that starts with 123456789... ?

Title: Re: Fibonacci number starting with 123456789
Post by Grimbal on Aug 12^th, 2020, 6:38am

I can't give it in full, but I can give you the start of it. :)

More seriously, given that Fibonacci numbers are based on the golden ratio, the initial digits should cover quite uniformly all possibilities. You should find every sequence of 9 digits among the initial digits of the first few bilions of Fibonacci numbers.

But since the sequence is exponential these numbers tend to be huge, especially near the end.

Title: Re: Fibonacci number starting with 123456789
Post by towr on Aug 12^th, 2020, 10:55am

There's a way to find one reasonably quickly. (i.e. a lot faster than generating each Fibonacci number in turn and check.)

And basically the question is: what is lowest N such that the Nth fibonacci number starts with 123456789

Another fun question is to find the first Fibonacci number with more than 7 (or 8) digits so that the first 7 (or 8) and last 7 (or 8) digits are the same (or mirror each other)

Title: Re: Fibonacci number starting with 123456789
Post by Grimbal on Aug 13^th, 2020, 5:06pm

I would propose F_158349400.

https://www.wolframalpha.com/input/?i=Fibonacci+158349400

It has 33093068 digits. You understand I can't give it in full.

I wrote a clever program that solves
phiⁿ/sqrt(5) ~= 123456789.5 * 10^k
by solving
n log(phi) - k log(10) ~= log(123456789.5 * sqrt(5))
for integer n and k.

But it found a solution with k<0 and n<0. Trying to limit k and n to positive values it fails due to the limited precision of doubles in java.

So in the end I wrote a brute force program that gave me the answer in a few seconds.

Title: Re: Fibonacci number starting with 123456789
Post by towr on Aug 14^th, 2020, 2:28am

I should have thought of that .5
Aside from that I used the same approach.