# Euler Problem 119

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
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/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)
End If
Next Pwr
Next Base

For i = 1 To a.Count – 1
For j = i + 1 To a.Count
If a(i) &gt; a(j) Then
Item = a(j)
Key = CStr(Item)
a.Remove j
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

Posted in Uncategorized

## 2 thoughts on “Euler Problem 119”

1. JoshG says:

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.

-Josh

2. Michael says:

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.

…mrt

Posting code? Use <pre> tags for VBA and <code> tags for inline.