You are on the Home/Other Tutorials/Project Euler/Problem 104 page
Google
Web This Site

Project Euler - Problem 104

More about Project Euler.

Problem description

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.

Solution

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