Add-ins:
Excel
PowerPoint

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*.

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