Project Euler 104: Find the first Fibonacci number for which the ends are pandigital.
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.
Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.
Even calculating the Fibonacci sequence without any optimization this solution was lightning fast. Getting the bottom 9 digits was easy and has been done in previous problems. The top 9 required the formula:
phi = (1 + sqrt(5)) / 2
t = n * log10(phi) + log10(1/sqrt(5))
t = int((pow(10, t – int(t) + 8)))
So, after finding a candidate with the bottom 9 digits pandigital we query the formula to see if the top 9 are pandigital. The first one found will be our first solution.
Project Euler 104 SolutionRuns < 0.050 seconds in Python 2.7.
from Euler import is_pandigital def top_digits(n): t = n * 0.20898764024997873 + (-0.3494850021680094) t = int((pow(10, t - int(t) + 8))) return t fk, f0, f1 = 2, 1, 1 while not is_pandigital(f1) or not is_pandigital(top_digits(fk)): f0, f1 = f1, (f1+f0) % 10**9 fk += 1 print "Project Euler 104 Solution =", fkUse this link to get the Project Euler 104 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- The constants in this solution are from the formula: t = n * log10(phi) + log10(1/sqrt(5)).
is_pandigitalis listed in Common Functions and Routines for Project Euler