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