Euler Solution 104

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Created page with "= 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 A...")
m (Solutions for Problem 104)
Line 41: Line 41:
     print "Answer: ", n
     print "Answer: ", n
     break
     break
 +
 +
[[Category:Euler]]

Revision as of 04:53, 8 March 2011

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:
 if n % 5000 == 0: print n
 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