Multiplicative persistence
I saw a story this morning in Gizmodo about hard logic puzzles, and one of them caught my attention for some brute force computational processing.
Martin Gardner was a famous mathematician, and in one of his books, he talks about the persistence of a number as the number of times it iteratively takes to multiply the individual digits of an integer together until you end up with a single digit number. As an example, if you consider the number 25, the persistence is 2 because 2×5 equals 10 (step 1), and then 1×0 equals 0 (step 2).
So here is a quick algorithm I threw together in VB.NET to find the smallest number that has a particular persistence:
Module Module1
Function Persistence(num As Integer) As Integer
Dim n As Integer = Math.Abs(num)
Dim p As Integer = 0
While n >= 10
Dim nString = n.ToString()
n = 1
For i = 0 To nString.Length - 1
n *= Convert.ToInt16(nString.Substring(i, 1))
Next
p = p + 1
End While
Return p
End Function
Sub Main()
Dim persistenceList As List(Of Integer) = New List(Of Integer)()
Dim p As Integer
For i = 1 To 10000000
p = Persistence(i)
If persistenceList.Count < p Then
Console.WriteLine("Just found a persistence of " + p.ToString() + " for " + i.ToString())
persistenceList.Add(i)
End If
Next
Console.WriteLine("Press any key to exit...")
Console.ReadKey()
End Sub
End Module |
When you run this, you see something like this in the console:
Just found a persistence of 1 for 10 Just found a persistence of 2 for 25 Just found a persistence of 3 for 39 Just found a persistence of 4 for 77 Just found a persistence of 5 for 679 Just found a persistence of 6 for 6788 Just found a persistence of 7 for 68889 Just found a persistence of 8 for 2677889 Press any key to exit... |
Above a persistence of 8, it can take a very very long time to brute force a solution.
BTW, Happy Birthday to Anton Fig, a fantastic drummer who has worked with one of my favorite artists, Joe Bonamassa.