193 lines
7.2 KiB
VB.net
193 lines
7.2 KiB
VB.net
Option Strict On
|
|
Option Explicit On
|
|
|
|
Imports System.IO
|
|
|
|
''' <summary>
|
|
''' Finds n digit numbers N such that the sum of the nth powers of
|
|
''' their digits = N
|
|
''' </summary>
|
|
Module OwnDigitsPowerSum
|
|
|
|
Public Sub Main
|
|
|
|
' counts of used digits, check is a copy used to check the number is an own digit power sum
|
|
Dim used(9) As Integer
|
|
Dim check(9) As Integer
|
|
Dim power(9, 9) As Long
|
|
For i As Integer = 0 To 9
|
|
check(i) = 0
|
|
Next i
|
|
For i As Integer = 1 To 9
|
|
power(1, i) = i
|
|
Next i
|
|
For j As Integer = 2 To 9
|
|
For i As Integer = 1 To 9
|
|
power(j, i) = power(j - 1, i) * i
|
|
Next i
|
|
Next j
|
|
' find the lowest possible first digit for each digit combination
|
|
' this is the roughly the low3est n where P*n^p > 10^p
|
|
Dim lowestDigit(9) As Integer
|
|
lowestDigit(1) = -1
|
|
lowestDigit(2) = -1
|
|
Dim p10 As Long = 100
|
|
For i As Integer = 3 To 9
|
|
For p As Integer = 2 To 9
|
|
Dim np As Long = power(i, p) * i
|
|
If Not ( np < p10) Then Exit For
|
|
lowestDigit(i) = p
|
|
Next p
|
|
p10 *= 10
|
|
Next i
|
|
' find the maximum number of zeros possible for each width and max digit
|
|
Dim maxZeros(9, 9) As Integer
|
|
For i As Integer = 1 To 9
|
|
For j As Integer = 1 To 9
|
|
maxZeros(i, j) = 0
|
|
Next j
|
|
Next i
|
|
p10 = 1000
|
|
For w As Integer = 3 To 9
|
|
For d As Integer = lowestDigit(w) To 9
|
|
Dim nz As Integer = 9
|
|
Do
|
|
If nz < 0 Then
|
|
Exit Do
|
|
Else
|
|
Dim np As Long = power(w, d) * nz
|
|
IF Not ( np > p10) Then Exit Do
|
|
End If
|
|
nz -= 1
|
|
Loop
|
|
maxZeros(w, d) = If(nz > w, 0, w - nz)
|
|
Next d
|
|
p10 *= 10
|
|
Next w
|
|
' find the numbers, works backeards through the possible combinations of
|
|
' digits, starting from all 9s
|
|
Dim numbers(100) As Long ' will hold the own digit power sum numbers
|
|
Dim nCount As Integer = 0 ' count of the own digit power sums
|
|
Dim tryCount As Integer = 0 ' count of digit combinations tried
|
|
Dim digits(9) As Integer ' the latest digit combination to try
|
|
For d As Integer = 1 To 9
|
|
digits(d) = 9
|
|
Next d
|
|
For d As Integer = 0 To 8
|
|
used(d) = 0
|
|
Next d
|
|
used(9) = 9
|
|
Dim width As Integer = 9 ' number of digits
|
|
Dim last As Integer = width ' final digit position
|
|
p10 = 100000000 ' min value for a width digit power sum
|
|
Do While width > 2
|
|
tryCount += 1
|
|
Dim dps As Long = 0 ' construct the digit power sum
|
|
check(0) = used(0)
|
|
For i As Integer = 1 To 9
|
|
check(i) = used(i)
|
|
If used(i) <> 0 Then
|
|
dps += used(i) * power(width, i)
|
|
End If
|
|
Next i
|
|
' reduce the count of each digit by the number of times it appear in the digit power sum
|
|
Dim n As Long = dps
|
|
Do
|
|
check(CInt(n Mod 10)) -= 1 ' reduce the count of this digit
|
|
n \= 10
|
|
Loop Until n <= 0
|
|
Dim reduceWidth As Boolean = dps <= p10
|
|
If Not reduceWidth Then
|
|
' dps is not less than the minimum possible width number
|
|
' check there are no non-zero check counts left and so result is
|
|
' equal to its digit power sum
|
|
Dim zCount As Integer = 0
|
|
For i As Integer = 0 To 9
|
|
If check(i) <> 0 Then Exit For
|
|
zCount+= 1
|
|
Next i
|
|
If zCount = 10 Then
|
|
nCount += 1
|
|
numbers(nCount) = dps
|
|
End If
|
|
' prepare the next digit combination: reduce the last digit
|
|
used(digits(last)) -= 1
|
|
digits(last) -= 1
|
|
If digits(last) = 0 Then
|
|
' the last digit is now zero - check this number of zeros is possible
|
|
If used(0) >= maxZeros(width, digits(1)) Then
|
|
' have exceeded the maximum number of zeros for the first digit in this width
|
|
digits(last) = -1
|
|
End If
|
|
End If
|
|
If digits(last) >= 0 Then
|
|
' still processing the last digit
|
|
used(digits(last)) += 1
|
|
Else
|
|
' last digit is now -1, start processing the previous digit
|
|
Dim prev As Integer = last
|
|
Do
|
|
prev -= 1
|
|
If prev < 1 Then
|
|
Exit Do
|
|
Else
|
|
used(digits(prev)) -= 1
|
|
digits(prev) -= 1
|
|
IF digits(prev) >= 0 Then Exit Do
|
|
End If
|
|
Loop
|
|
If prev > 0 Then
|
|
' still some digits to process
|
|
If prev = 1 Then
|
|
If digits(1) <= lowestDigit(width) Then
|
|
' just finished the lowest possible maximum digit for this width
|
|
prev = 0
|
|
End If
|
|
End If
|
|
If prev <> 0 Then
|
|
' OK to try a lower digit
|
|
used(digits(prev)) += 1
|
|
For i As Integer = prev + 1 To width
|
|
digits(i) = digits(prev)
|
|
used(digits(prev)) += 1
|
|
Next i
|
|
End If
|
|
End If
|
|
If prev <= 0 Then
|
|
' processed all the digits for this width
|
|
reduceWidth = True
|
|
End If
|
|
End If
|
|
End If
|
|
If reduceWidth Then
|
|
' reduce the number of digits
|
|
last -= 1
|
|
width = last
|
|
If last > 0 Then
|
|
' iniialise for fewer digits
|
|
For d As Integer = 1 To last
|
|
digits(d) = 9
|
|
Next d
|
|
For d As Integer = last + 1 To 9
|
|
digits(d) = -1
|
|
Next d
|
|
For d As Integer = 0 To 8
|
|
used(d) = 0
|
|
Next d
|
|
used(9) = last
|
|
p10 \= 10
|
|
End If
|
|
End If
|
|
Loop
|
|
' show the own digit power sums
|
|
Console.Out.WriteLine("Own digits power sums for N = 3 to 9 inclusive:")
|
|
For i As Integer = nCount To 1 Step -1
|
|
Console.Out.WriteLine(numbers(i))
|
|
Next i
|
|
Console.Out.WriteLine("Considered " & tryCount & " digit combinations")
|
|
|
|
End Sub
|
|
|
|
|
|
End Module
|