// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (21 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 104 Solution

Project Euler 104 Solution

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:

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.

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
download arrowUse 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.
|329468|

Afterthoughts

Project Euler 104 Solution last updated

Discussion

3 Responses to “Project Euler 104 Solution”

  1. sorry but 329468 is not the solution 🙂

    Posted by diego | September 10, 2011, 9:52 PM
  2. Can you explain how t gets the top 9 digits?

    Posted by Daniel | October 19, 2009, 7:58 PM

Post a comment