Project Euler Problem 104 Statement
The Fibonacci sequence is defined by the recurrence relation:
$F_n = F_{n - 1} + F_{n - 2}$, where $F_1 = 1$ and $F_2 = 1$.
It turns out that $F_{541}$, 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 $F_{2749}$, which contains $575$ digits, is the first Fibonacci number for which the first nine digits are $1$-$9$ pandigital.
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$.
Solution
Python Source Code
def solve(l1=1, l2=1, f1=1, f2=1, n=2):
while n:
n += 1
l1, l2 = l2, (l1 + l2) % 10**9
f1, f2 = f2, f1 + f2
if f2 > 10**18: f1, f2 = f1 // 10, f2 // 10
for v in (l2, f2 // 10**(len(str(f2))-9)):
m = 0
for _ in range(9): m |= 1 << (v % 10); v //= 10
if m != 1022: break
else: return n
print(solve())