In [124]:
from collections import Counter
Checking all possible numbers is roughly equivalent to a grouping problem (by a multi-set) $$ \binom{39+10-1}{10-1} \approx 10^{9} $$ which is definitely doable by a computer. If we have ~1000 operations per number, and we have a constant, 1GHz processor, then the total time lies at around $\sim 10^3$ seconds.
In [125]:
def getPossibleCollections(N, k):
S = []
D = Counter()
_getPossibleCollections(N, k, 0, S, D)
return S
def _getPossibleCollections(N, k, i, S, curr):
if k < 0:
raise(IndexError("A negative value was passed"))
if i > N:
S.append(curr.copy())
return
if i == N:
curr[str(i)] = k
_getPossibleCollections(N, 0, i+1, S, curr)
return
for L in range(k+1):
curr[str(i)] = L
_getPossibleCollections(N, k-L, i+1, S, curr)
In [126]:
def getArmstrongNumbers(K):
# Gets the digit exponentiation (so it doesn't have to be recomputed every time)
digits = [i**K for i in range(10)]
# Gets all of the possible multisets of 9 digits with 5 total elements.
N = getPossibleCollections(9, K)
MATCHES = []
A = Counter()
for S in N:
T = 0
for i in S:
l = int(i)
T += S[i]*digits[l]
if Counter(str(T))-S == A:
MATCHES.append(T)
return [k for k in MATCHES if len(str(k))==K]
In [127]:
for i in range(21):
MATCHES = getArmstrongNumbers(i)
print('{}: {}'.format(i, str(sorted(MATCHES))))
In [ ]: