Euler Problem 119

Euler Problem 119 asks:

The number 512 is interesting because it is equal to the Base of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define a(n) to be the nth term of this sequence and insist that a number must contain at least two digits to have a Base.

You are given that a(2) = 512 and a(10) = 614656.

Find a(30).

83 = 512 is the same as log8(512) = 3, and 284 = 614656 is the same as log28(614656) = 4. If we find numbers that have integral logs in a base equal to the sum of their digits then we have found elements of a(). We only need the first 30.

The VBA Log() function uses natural logs. For those with an engineering bent, it’s like the worksheet LN() function. To get Logs in a different base, the VBA help file reminds us that Logn(x) = Log(x) / Log(n). With the caution that if the n = 1, then log(n) = 0, and we have a division by zero to guard against.

Here is the code that does this:

Sub Problem_119()
   Dim n As Variant
   Dim TEMPlog As Single
   Dim i As Long, Base As Long, a As Long
   Dim T As Single
   T = Timer
   n = 10
      n = n + 1
      Base = 0
      For i = 1 To Len(n)
         Base = Base + Val(Mid(n, i, 1))
      Next i
      If Base != 1 Then TEMPlog = Log(n) / Log(Base) ‘ protect against div0
     If TEMPlog = Int(TEMPlog) Then
         a = a + 1
         Debug.Print a, n
      End If
   Loop Until a = 12
   Debug.Print Timer – T
End Sub

Note that I stopped at a(12). That determination takes 20 seconds, and a(n) and a(n+1) are getting farther and farther apart. The method is sound, but the approach isn’t timely.

An alternative is to find lots of numbers to powers, and check to see if they have the requisite base. Doing it that way, the a(n) elements do not arrive in n order, and a sort will be required to pull out a(30). Since I don’t know how many there are in the span of numbers, we’ll add the proper results to a collection, and then sort the collection. (Dick has an article on sorting a collection here. I shamelessly ripped him off.) This is the new code. It runs in a 1/100th of a second..

Sub Problem_119A()
   Dim n As Variant
   Dim Sum As Double
   Dim Base As Long
   Dim Pwr As Long, i As Long, j As Long
   Dim a As New Collection
   Dim Item As Double, Key As String
   Dim T As Single
   T = Timer
   For Base = 2 To 100
      For Pwr = 2 To 10
         n = Base ^ Pwr
         Sum = 0
         For i = 1 To Len(n)
            Sum = Sum + Val(Mid(n, i, 1))
         Next i
         If Sum = Base Then ‘ an element of a()
           Item = n
            Key = CStr(Item)
            a.Add Item:=Item, Key:=Key
         End If
      Next Pwr
   Next Base
   For i = 1 To a.Count – 1
      For j = i + 1 To a.Count
         If a(i) > a(j) Then
            Item = a(j)
            Key = CStr(Item)
            a.Remove j
            a.Add Item:=Item, Key:=Key, Before:=i
         End If
      Next j
   Next i
   Debug.Print a(30); ”  Time:”; Timer – T
End Sub

The usual angle bracket substitutions are in the above. When you see the answer, you’ll see how bad that first approach really was. At least the answer fits in a variant without loss of precision.

Happy Labor Day!


Posted in Uncategorized

2 thoughts on “Euler Problem 119

  1. That looks pretty much like my solution, except I cheated with the sorting by just outputting the results to a sheet and sorting there. I didn’t know the bit about sorting a collection, so that’s good to know.


  2. Hi Josh –

    Looks like everyone’s solution, I’d guess, based on the dearth of comments. Trust me to find the right way second ;-)

    It was kinda neat when a google of “VBA sort collection” pointed me right back here.


Leave a Reply

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