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