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.
Part of the 'trick' in solving problem 13 was realizing that one can get the leftmost 10 digits of a series of summations by tracking only the 15 leftmost digits. Now, in this problem, we need only 9 digits. As a safety precaution I decided to track almost as many digits as would fit in what VBA calls a decimal number. By similar reasoning, the rightmost 9 digits of a series of summations requires one to track no more than the rightmost 9 digits!
The code below does just that. In the Right9 array, we have the 9 rightmost digits of the 2 numbers of a Fibonacci series calculated last. In Left27, we have the 27 leftmost digits of the same Fibonacci numbers.
Option Explicit Public cDecMax As Variant, cDecMaxLen As Integer, cSqrDecMaxLen As Integer Public Sub Initialize() Static Initialized As Boolean If Initialized Then Exit Sub Initialized = True cDecMax = _ CDec(Replace("79,228,162,514,264,337,593,543,950,335", ",", "")) 'this is 2^96-1 cDecMaxLen = Len(cDecMax) - 1 cSqrDecMaxLen = cDecMaxLen \ 2 End Sub Function PanDigital(ByVal X As String, Optional TenDigits As Boolean = False) As Boolean Dim Digits(9) As Integer, I As Integer If Len(X) <> IIf(TenDigits, 10, 9) Then PanDigital = False: Exit Function For I = 1 To Len(X) Dim aDigit As Integer aDigit = Mid(X, I, 1) Digits(aDigit) = Digits(aDigit) + 1 If Digits(aDigit) > 1 Then PanDigital = False: Exit Function Next I For I = IIf(TenDigits, 0, 1) To 9 If Digits(I) = 0 Then PanDigital = False: Exit Function Next I PanDigital = True End Function Sub Euler104() Dim K As Long, Left27(1) As Variant, Right9(1) As Long Dim StartTime As Single: StartTime = Timer Left27(0) = CDec(1): Left27(1) = CDec(1) Right9(0) = 1: Right9(1) = 1 Initialize K = 3 Do While True Dim TempR9 As Long, TempL27 As Variant TempR9 = Right9(0) + Right9(1) TempR9 = Right(TempR9, 9) TempL27 = CDec(Left27(0) + Left27(1)) If Len(TempL27) > cDecMaxLen - 1 Then TempL27 = CDec(Left(TempL27, Len(TempL27) - 2)) Left27(1) = CDec(Left(Left27(1), Len(Left27(1)) - 2)) End If If PanDigital(TempR9) Then If PanDigital(Left(TempL27, 9)) Then Exit Do Left27(0) = Left27(1): Left27(1) = TempL27 Right9(0) = Right9(1): Right9(1) = TempR9 K = K + 1 Loop Debug.Print K; Timer - StartTime End Sub