Problem Description

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

It turns out that F₅₄₁, 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 F₂₇₄₉, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F_k is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

Analysis

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.

Solution

Runs < 2 seconds in Python.

from Euler import is_pandigital
 
def top_digits(n):
# t = n * log10(phi)          + log10(1/sqrt(5))
  t = n * 0.20898764024997873 - 0.34948500216800940
  t = int((pow(10, t - int(t) + 8)))
  return t
 
fn, f0, f1 = 2, 1, 1
while not is_pandigital(f1) or not is_pandigital(top_digits(fn)):
 f0, f1 = f1, (f1+f0)%10**9
 fn += 1
print "Answer to PE104 = ", fn

Comments