Python Challenges: Find the index of the first term in the Fibonacci sequence to contain 500 digits

Last update on December 21 2024 07:49:45 (UTC/GMT +8 hours)

Write a Python program to find the index of the first term in the Fibonacci sequence to contain 500 digits.

In mathematics, the Fibonacci numbers, commonly denoted F_n form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1
The Fibonacci sequence is defined by the recurrence relation:
F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.
Hence the first 12 terms will be:
F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144
The 12^th term, F₁₂, is the first term to contain three digits.

Sample Solution:

Python Code:

import itertools
def Fibonacci_sequence(n):
	DIGITS = n
	prev_num = 1
	cur_num = 0
	for i in itertools.count():
		# At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
		if len(str(cur_num)) > DIGITS:
			raise RuntimeError("Not found")
		elif len(str(cur_num)) == DIGITS:
			return str(i)
		prev_num, cur_num = cur_num, prev_num + cur_num

print(Fibonacci_sequence(500))

Sample Output:

2390

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to find the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9.
Next: Write a Python program that takes a string and encode it that the amount of symbols would be represented by integer and the symbol.