Euler Problem 104

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:

Sub Problem_104()
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

Posted in Uncategorized

6 thoughts on “Euler Problem 104

  1. 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?

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

  3. 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?

  4. Hi again,
    one other thing, what was wrong with the BigNum Code you linked to before? Did it have a size limit?
    Thanks
    Ross

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

  6. 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]

Leave a Reply

Your email address will not be published. Required fields are marked *