# 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)):