## Project Euler 104: Find the first Fibonacci number for which the ends are pandigital.

#### Problem Description

The Fibonacci sequence is defined by the recurrence relation:

F_{n} = F_{n−1} + F_{n−2}, where F_{1} = 1 and F_{2} = 1.

It turns out that F_{541}, 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_{2749}, 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.

#### Project Euler 104 Solution

Runs < 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 =", fk
```

Use this link to get the Project Euler 104 Solution Python 2.7 source.#### Answer

Slowly 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.

#### Afterthoughts

- The constants in this solution are from the formula: t = n * log10(phi) + log10(1/sqrt(5)).
- Function
`is_pandigital`

is listed in Common Functions and Routines for Project Euler

*Project Euler 104 Solution last updated*

sorry but 329468 is not the solution 🙂

sorry.. im bad

Can you explain how t gets the top 9 digits?