﻿ Project Euler Problem 104
You are on the Home/Other Tutorials/Project Euler/Problem 104 page

Web This Site

# Project Euler - Problem 104

## 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)
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```