function that counts...

[Bryan]

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))