Euler Solution 104

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 104

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.


Python by Althalus

Runtime: 3.64 seconds

This is version 3. Version one took a few nights. Version two took 5 minutes.

from itertools import permutations
from math import sqrt, log10

def is_pandigital(n):
        n = str(n)
        return set('123456789') == set(str(n))

def first_9_digits (n):
 # Based on notes in this link (the fibonacci sequence has more to it than first appears):
 # http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
 phi = (1 + sqrt(5)) / 2
 # The result of the logarithm gives us xxxx.yyyyy - 
 # xxxx + 1 = number of digits in the fib number
 # 10 ** yyyyy = the actual fib number (or an approximation thereof
 log_res = n * log10(phi) + log10(1/sqrt(5))
 # Given the above, we eliminate xxxxx and give us just enough of yyyyy to get
 # the 9 digits required.
 # print log_res, log_res -int(log_res)
 return int(10**(log_res - int(log_res) + 8)) 

# Simple fib sequence
cur, prev = 1, 1
n = 2
while True:
 prev, cur = cur%1000000000, (cur+prev)%1000000000
 n += 1
 last_nine = cur % 1000000000
 if is_pandigital(last_nine):
  if is_pandigital(first_9_digits(n)):
   print "Answer: ", n
   break
Personal tools