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 8

^{3}= 512. Another example of a number with this property is 614656 = 28^{4}.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).

8^{3} = 512 is the same as log_{8}(512) = 3, and 28^{4} = 614656 is the same as log_{28}(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 Log_{n}(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:

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

Do

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/100^{th} of a second..

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!

*…mrt*