Euler Problem 104 asks:

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.

The title really deserves an exclamation point. As discussed in Large Number Arithmetic I’ve been trying to solve this problem since before January. This problem breaks my little AddAsStrings function, and for reasons you’ll see, overflows Tushar’s LargeAdd function. We’re looking for a * big number*, longer in length then Excel can handle as a string. And I was stuck. Doug, in Large Number Arithmetic, showed how to keep track of the back end of a variable. How to keep track of the front end had me stumped until it came to me last Sunday morning when I woke up (any one else code in their sleep?): Separate variables. Use a long to track the backend and a double to track the front end. An immediate trouble with that is that doubles only work to E+308, and one of the test cases, Fib(2749) is E+575. Solution there was to knock the Fibonacci values down by 10^2 when ever they get over 10^9, and keep track of the exponent in a separate variable. Here is my code, with a helper function Ends() that tests the ends for “pan-digitality.” It’s a little faster than most I’ve seen, since it breaks as soon as there is a failure, rather that testing on, and I only test the left side when the right side is pandigital. The code runs in six-tenths of a second:

Dim i_lng As Long, j_lng As Long, k_lng As Long

Dim i_dbl As Double, j_dbl As Double, k_dbl As Double

Dim k_str As String

Dim LeftSAT As Boolean

Dim RightSAT As Boolean

Dim Answer As Long, T As Single

Dim exp As Long

Dim Fib_ans As String

Dim PlusMark As Long

T = Timer

i_lng = 1

j_lng = 1

i_dbl = 1

j_dbl = 1

Answer = 2

Do

Answer = Answer + 1

k_lng = i_lng + j_lng

k_str = Right(k_lng, 9)

i_lng = j_lng

j_lng = CLng(k_str)

k_dbl = i_dbl + j_dbl

i_dbl = j_dbl

j_dbl = k_dbl

If k_dbl GT 1000000000 Then ‘ knock it down by 10^2

i_dbl = i_dbl / 100

j_dbl = j_dbl / 100

exp = exp + 2 ‘ tracking the exponent

End If

LeftSAT = False

RightSAT = False

RightSAT = Ends(k_str)

If RightSAT Then

LeftSAT = Ends(CStr(k_dbl))

End If

Loop Until LeftSAT = True And RightSAT = True

Fib_ans = Format(k_dbl, “0.00000000000000E+”)

PlusMark = InStr(1, Fib_ans, “+”)

Fib_ans = Left(Fib_ans, PlusMark) & (CLng(Right(Fib_ans, Len(Fib_ans) – PlusMark)) + exp)

Debug.Print Answer, Left(k_dbl, 9), k_str

Debug.Print “Fib(“ & Answer & “) = “; Fib_ans; ” Time:”; Timer – T;

End Sub

Function Ends(k_str As String) As Boolean

Dim E As Long

Dim E_str As String

E_str = Left(k_str, 9)

For E = 1 To 9

If InStr(1, E_str, CStr(E)) Then

Ends = True

Else

Ends = False

Exit For

End If

Next E

End Function

Compared to the multi-precision answer given by the Foxes Team addin mentioned in Large Number Arithemtic, this answer drifts off in the 13 decimal place. The xnumbers add-in has been helpful. It did the Euler totient problems, for instance. It’s been a useful addition to the toolbox, and since any improvement has stopped, I’d recommend grabbing before it disappears.

…mrt

I wish was smart enough to understand this!!!Numbers that are to big to hold in a variable? is there no API you could use?

Hi Ross –

The Euler problems are famous for asking for answers that require precision longer than 32 bits. Math done that way can be done on strings, and the answers are strings. For instance, AddAsStrings takes two numbers and adds them in columns, with carrys, from the right side, just as you did in elementary school. I do it one column at a time, Tushar does many at a time (his is much, much the faster), but for both of us, the result is a string representation of the number. The Foxes team addin can do math up to 250 significant digits in several hundred esoteric functions. All of it is string manipulation.

The problem here is that the Fibonacci number of the Answer is longer than Excel can handle as a string, and larger than Excel can handle as a double, and we need to be accurate at the front and the back. The middle is of no consequence to Euler ;-). If you look up the Excel limit for string size, it’s about 64K characters. The length of the answer is longer than that, and we need to look at it’s first nine digits in the doubles, and its last nine digits in the longs. If there is a LargeNumber API for us, I’ve not stumbled across it.

…mrt

Hi Michael,

Interesting stuff, I spent a little bit of time reading up on this, this PM. There is an addin which claims to work with over 2 billion digits, so there you go! (the link to the site is at the bottom of Tushar’s pages)

Is it not a relatively rival task to just use 2 string in stead of one? (looking at Tushar’s code away). Having said that I am extreamly confident that your understanding of this is much much much much^10000! better than mine, and there is a reason why this is not straight forward?

Hi again,

one other thing, what was wrong with the BigNum Code you linked to before? Did it have a size limit?

Thanks

Ross

Hi Ross –

I could never get those BigNum routines to work. They are called with 3 parameters, with the 3rd one not optional. I could never decipher why you needed three parameters to operate on two numbers (or strings). Still can’t. The author did not assign any meaningful names to his variables!

And not being able to load the form made me unable to check out anything.

Is it straight forward? I suppose somewhat. I get the additions certainly, and The Foxes website walks through a large multiplication at

http://digilander.libero.it/foxes/MultiPrecision.htm#Packet

I’d find it more straight forward for understanding the whole process if both their multiplier and their multiplicand had to be packetized.

…mrt

I started off generationg the ends of the fibonacci numbers on the spreadsheet, and checking them with a UDF. It works, but it would be very slow to find the resullt required, and would need to be done in stages when using pre-2007 versions, so I ended up writing some VBA to generate the numbers as well. I started off using strings to check for pandigitals, but converted to the routine below, which uses doubles, and strips off one digit at a time by dividing by 10. It stops if it finds a repeated digit or zero. The values for the left hand end may include a decimal point in the first nine digits, so the function multiplies any left hand value less than 1000000000 by 10^(9-k), where k is the number of digits before the decimal point. The right hand values always start with 9 digits, so a k of less than 9 indicates one or more leading zeroes.

Solution time a shade over 1 second. I thought I’d get it under 1 second by running in XL 2000, but it was almost exactly the same time (to my surprise).

[VB}

Function pandigital(ByVal val As Double, LorR As String) As Boolean

Dim DigitA(1 To 9) As Long, i As Long, j As Long, k As Long, CheckVal As Double, NCheckval As Double

k = (Log(val) / Log(10))

CheckVal = val

If k .NE. 9 Then

If LorR = “R” Then

pandigital = False

Exit Function

Else

CheckVal = val * 10 ^ (9 – k)

End If

End If

For i = 1 To 9

NCheckval = Int(CheckVal / 10)

j = CheckVal – NCheckval * 10

CheckVal = NCheckval

If j = 0 Or j .GT. 9 Then

pandigital = False

Exit Function

End If

If DigitA(j) = 1 Then

pandigital = False

Exit Function

Else

DigitA(j) = 1

End If

Next i

pandigital = True

End Function

[VB]