School problem from senior developer interview

#challenge #career #math #python

I was asked this problem years ago at interview for Java developer. It was about using BigInt really, but that's not important. I later slightly extended it and started asking when I interview other people in my turn (usually big-data or data science developers). Curiously, it puzzles about 40% people pretending for several kilo-dollars salary :o

Code could be written in 3 minutes (e.g. in Python), but then people sometimes stuck for hour. I think most of you, Friends, will solve it easily - but you can check your colleagues for fun. So here it is:

Statement

Fibonacci numbers (we all know them) are defined as:

fib = [0, 1, 1, 2, 3, 5, 8, ...]

# or in other words
fib[0] = 0
fib[1] = 1
# ...
fib[n] = fib[n-1] + fib[n-2]

Write the program (usually in Python) which finds index, where Fibonacci value ends with specific digits. For example ending 12345 could be found at fib[155].

Then find the following:

For which index X fib[X] ends with five digits `55555` ?  
For which index Y fib[Y] ends with seven digits `7770777` ?  
For which index Z fib[Z] ends with eight digits `20200123` ?

This value 20200123 is just today's date, nothing special about it. :)

P.S. I think it's ok to drop X, Y, Z in the comments when you find them. Code - as you wish...

P.P.S. if can't solve at once, this problem may give inspiration, though of course you'd better try solving on your own first... If it is necessary I'll update the post with explanation in about three days, though I believe it is too simple for most of readers.

Top comments (8)

Jannik Wempe • Jan 23 '20

That was a fun task and I could refresh some aspects of python doing it. Thanks!

Until now (programm is still executing) I just have the following solution:
X -> 92740
Y -> ???
Z -> ???

I am pretty sure that my solution is far from perfect, since it has a huge runtime and memory consumption. Therefore I'm really looking forward to a better approach.

Rodion Gorkovenko • Jan 23 '20

Jannik, Hi!

Thanks for attempt!

Yep, it is just a matter of making it work without speed degradation due to number length increase :)

Arseniy Krasnov • Jan 24 '20 • Edited

There a trick you can use:

last 2 and 3 digits of fibonacci repeats each 1500 terms
last 4 digits repeats each 15,000
last 5 digits repeats each 150,000
last 6 digits repeats each 1,500,000
last 7 digits repeats each 15,000,000

x = 92.740
y = 4.562.603
z = 280.555.264

Rodion Gorkovenko • Jan 25 '20

Nice idea about finding "the loop length" after which "endings" repeat :) Perhaps some other puzzle could be invented from it.

However my approach was simpler - just taking modulo by 10eX where X is amount of digits in the number we seek. Then numbers won't grow longer than this.

I suspect your and mine approaches are really two versions of the same fact, however