Speeding Up a Python While Loop

The fastest solution when you have large numbers isn't going to look at the individual numbers at all. If you want to find out how many 10 digit numbers sum to 39, first find all the unique combinations of 10 digits that sum to 39 (2630 of them).

The way you can do that is for each digit d, find all the unique combinations of 9 digit numbers summing to 39-d where no digit is less than d.

def unique_combos(digits, total, smallest=0):
    if digits*9 < total or digits*smallest > total:
        return
    if digits==1:
        yield [total]
        return

    for i in range(smallest, 10):
        for combo in unique_combos(digits-1, total-i, i):
            yield [i]+combo

Then for each unique combination of digits find out how many ways it can be arranged. That's just simple math, only you have to avoid counting any that begin with leading zeros.

import operator
from collections import Counter
from math import factorial
def npermutations(l):
    """From stackoverflow 16453188"""
    num = factorial(len(l))
    mults = Counter(l).values()
    den = reduce(operator.mul, (factorial(v) for v in mults), 1)
    return num / den

Now just add up that figure for each combination and you have your answer. Given that we're no longer worried too much about speed I just subtracted the number with fewer digits.

def answer(digits, total):
    n_or_fewer = sum(npermutations(l) for l in unique_combos(digits, total))
    fewer = sum(npermutations(l) for l in unique_combos(digits-1, total))
    print("There are {} {}-digit numbers with digits summing to {}".format(
        n_or_fewer - fewer,
        digits, total))

if __name__=='__main__':
    answer(4,18)
    answer(10,39)

Output takes less than 1 second:

C:\Temp>digitsum2.py
There are 615 4-digit numbers with digits summing to 18
There are 307100365 10-digit numbers with digits summing to 39

For completeness, Sudipta suggested optimising how you step through the numbers. Here's some code that does that: it goes directly from one number to the next, and gets the same answer for 4 digit numbers but I still got bored running it for the 307 million 10 digit values. It could probably be optimised quite a bit, but brute force is the wrong way to go here.

def smallest_sum(n, digits, first=1):
    """Find the smallest number with 'digits' digits that sum to 'n'
    Returns the value as a list of digits because that's what we need next anyway"""
    k = max(first,n + 9 - 9*digits)
    assert k <= 9, "Impossible values"
    if digits > 1:
            return [k]+smallest_sum(n-k, digits-1, 0)
    return [k]

def all_sums(digits):
    """Find the next string of digits with the same sum.
    We can do this by finding the last non-zero digit and decrementing it
    then incrementing the previous non-nine, and sorting any digits that
    follow it."""
    yield digits
    while True:
        was = list(digits)
        for i in range(len(digits)-1,-1,-1):
            if digits[i] != 0:
                decrement = i
                break
        else:
            return
        for i in range(decrement-1,-1,-1):
            if digits[i] != 9:
                increment = i
                break
        else:
            return
        digits[decrement] -= 1
        digits[increment] += 1
        if increment < len(digits)-2:
            digits[increment+1:] = digits[increment+1:][::-1]
        assert digits > was
        yield digits

def count(num_digits, total):
    try:
        digits = smallest_sum(total, num_digits)
    except AssertionError:
        return 0
    return sum(1 for _ in all_sums(digits))

if __name__=='__main__':
    print(count(4,18))
    print(count(10,39))