math - How do I make 100 = 1? (explanation within)

Question

Right now I have a code that can find the number of combinations of a sum of a value using numbers greater than zero and less than the value. I need to alter the value in order to expand the combinations so that they include more than just the value.

For example: The number 10 yields the results: [1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [1, 9], [2, 3, 5], [2, 8], [3, 7], [4, 6] But I need to expand this to including any number that collapses to 1 as well. Because in essence, I need 100 = n in that the sum of the individual numbers within the digits = n. So in this case 100 = 1 because 100 --> 1+0+0 = 1 Therefore the number 1999 will also be a valid combination to list for value = 100 because 1999 = 1+9+9+9 = 28, and 28 = 2+8 = 10, and 10 = 1+0 = 1

Now I realize that this will yield an infinite series of combinations, so I will need to set limits to the range I want to acquire data for. This is the current code I am using to find my combinations.

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)

for val in range(100,101):
    s = range(1, val)
    solutions = a(s, val)
    print(solutions)
    print('Value:', val, "Combinations", len(solutions))

Answer 1

You seem to have multiple issues.

To repeatedly add the decimal digits of an integer until you end with a single digit, you could use this code.

d = val
while d > 9:
    d = sum(int(c) for c in str(d))

This acts in just the way you describe. However, there is an easier way. Repeatedly adding the decimal digits of a number is called casting out nines and results in the digital root of the number. This almost equals the remainder of the number when divided by nine, except that you want to get a result of 9 rather than 1. So easier and faster code is

d = val % 9
if d == 0:
    d == 9

or perhaps the shorter but trickier

d = (val - 1) % 9 + 1

or the even-more-tricky

d = val % 9 or 9

To find all numbers that end up at 7 (for example, or any digit from 1 to 9) you just want all numbers with the remainder 7 when divided by 9. So start at 7 and keep adding 9 and you get all such values.

The approach you are using to find all partitions of 7 then arranging them into numbers is much more complicated and slower than necessary.

To find all numbers that end up at 16 (for example, or any integer greater than 9) your current approach may be best. It is difficult otherwise to avoid the numbers that directly add to 7 or to 25 without going through 16. If this is really what you mean, say so in your question and we can look at this situation further.