# Euler Solution 104

### From ProgSoc Wiki

# 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