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 13th, 2020, 12:59pm)

Title: Fibonacci number starting with 123456789
Post by towr on May 13th, 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 12th, 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 12th, 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 13th, 2020, 5:06pm
I would propose F158349400.

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
phin/sqrt(5) ~= 123456789.5 * 10k
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 14th, 2020, 2:28am
I should have thought of that .5
Aside from that I used the same approach.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board