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]