Peter Pearson wrote:
> If it's important for the function to execute quickly for large n,
> you might get a useful speedup by testing only every ninth integer,
Our standards for "quickly" and "large" seem kind of thin.
> I suspect that further applications of number theory would
> provide additional, substantial speedups, but this wanders
> away from the subject of Python.
I was thinking combinatorics more than number theory. I didn't find a
neat formula, but I came up with a recursive memo-izing algorithm that
handles 100-digit n's. I tested this against the initial algorithm
plus Peter Pearson's optimization for numbers up to several thousand,
and it agrees... well, after I fixed stuff that is.
-Bryan Olson
# -----------
_nds = {}
def ndsums(m, d):
""" How many d-digit ints' digits sum to m?
"""
assert m >= 0 and d >= 0
if m > d * 9:
return 0
if m == 0 or d == 1:
return 1
if (m, d) not in _nds:
_nds[(m, d)] = sum(ndsums(m - i, d - 1)
for i in range(min(10, m + 1)))
return _nds[(m, d)]
def prttn(m, n):
assert m > 0 and n > 0
def inner(m, dls):
if not dls:
return 1 if m == 0 else 0
count = 0
msd, rest = dls[0], dls[1:]
for d in range(msd):
if m >= d:
count += ndsums(m - d, len(dls) - 1)
count += inner(m - msd, dls[1:])
return count
return inner(m, [int(c) for c in str(n - 1)])
pi100 =
3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
print(prttn(500, pi100))
--
http://mail.python.org/mailman/listinfo/python-list
