All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Fibonacci Tail 2 (Posted on 2023-11-08) Difficulty: 3 of 5
What is the smallest positive integer N, such that the base ten representation of Nth Fibonacci number ends in six zeroes?

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Computer solution | Comment 1 of 2
I did not test every number up to 750,000, but seeing the patterns, I suspect this is the answer.

I used a recursive program for Fibonacci which saves to a dictionary.
If I start with too large a number, the  program chokes on recursion depth.  But if I start small enough and increase gradually, it was able to go high enough.
At first, using smaller parameters, I found the patterns below, and eventually found that:
Fib(750000) ends in 6 zeros

Patterns: 
Every 15th Fib is a multiple of 10
Every 150th Fib is a multiple of 100
Every 750th Fib is a multiple of 1000
Fib(7500) ends in 4 zeros
Fib(75000) ends in 5 zeros
Fib(150000) also ends in 5 zeros

Fib(750000) ends in 6 zeros
This number is 15674 digits long

The program output was quite long, here is the start and end.
The second number of the pair is the number of zeros at the end of that Fibonacci number.
[[750, 3], [1500, 3], [2250, 3], [3000, 3], [3750, 3], [4500, 3], [5250, 3], [6000, 3], [6750, 3], [7500, 4], [8250, 3], [9000, 3], [9750, 3], [10500, 3], [11250, 3], [12000, 3], [12750, 3], [13500, 3], [14250, 3], [15000, 4], [15750, 3],  ... ... ,
...  ...
[741750, 3], [742500, 4], [743250, 3], [744000, 3], [744750, 3], [745500, 3], [746250, 3], [747000, 3], [747750, 3], [748500, 3], [749250, 3], [750000, 6]]

----------------------
def endzeros(n):
    """ how many zeros at the end of n """
    s = str(n)[::-1]
    count = 0
    for i,v in enumerate(s):
        if v == '0':
            count += 1
        else:
            return count
    return count

d = {0:0, 1:1, 2:1}
def fib(n):
    """ Efficient Fibonacci using dictionary,
    but not requiring dictionary to be already defined """
    global d
    if 'd' not in globals(): 
        d = {1:1, 2:1}
    if n in d:
        return d[n]
    else:
        ans = fib(n-1) + fib(n-2)
        d[n] = ans
        return ans

listanswers = []
for i in range(750,750001,750):
    listanswers.append([i, endzeros(fib(i))])
print(listanswers)

  Posted by Larry on 2023-11-08 08:59:12
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information