Problem #104 concerns Fibonacci numbers which contain each of the digits 1-9 in their leftmost and their rightmost digits. The question reads:
Project Euler Problem 104: Pandigital Fibonacci ends
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
It turns out that F541, 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 F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.
Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.
My solution for this question is not rigorous, and it probably wouldn’t get the correct answer if the question asked for the nth index with this property. However, it was efficient enough to solve this problem within a reasonable amount of time. Here’s my solution:
Solution #1: Arbitrary Precision of Leftmost Digits Approach
It is easy to determine the rightmost 9 digits of the nth Fibonacci number by simply storing the number mod 10^9. The difficulty comes in investigating the leftmost 9 digits. To do this, I arbitrarily stored the leftmost 15 digits and recursively updated them to get approximate leftmost 15 digits for each Fibonacci number. My hope is that the leftmost 9 digits of this recursive result will have the correct leftmost 9 digits for successive Fibonacci numbers. By checking the leftmost and rightmost 9 digits for the pandigital property, it is possible to find the first index with the given property. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #104
'''
import time
def isPandigital(x):
return sorted(x) == ["1","2","3","4","5","6","7","8","9"]
def projectEulerProblemOneHundredFour(n):
firstL = 1
secondL = 1
firstF = 1
secondF = 1
i = 3
while(True):
temp = firstL+secondL
secondL = firstL
firstL = temp%(10**9)
temp = firstF + secondF
secondF = firstF
if(temp>10**n):
temp = int(str(temp)[0:n])
secondF/=10
firstF = temp
if isPandigital(str(firstL)):
if isPandigital(str(firstF)[0:9]):
return i
i+=1
start = time.time()
print projectEulerProblemOneHundredFour(15)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
329468
--- 0.478230953217 seconds ---
for input of given problem.
'''
And with that, we’re done. It is very likely that for successive indices with this property, a larger amount of precision is necessary. I may come back to this problem eventually to find a more rigorous solution. Regardless, this solution did solve the problem within a second.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 