Find all variations of a digit sum

Question

Can anyone please direct me to an algorithm/formulae that says how to calculate all variations of a digit sum with a certain upper limit

So for example, if my digit sum is 6 and the upper limit is 123, then all variations for that digit sum would be: 6, 15, 24, 33, 42, 51, 60, 105, 114 and 123.

The upper limit can be up to 10**18 and program needs to work in under 1 second(in C/CPP), so brute force is not an option.

Assuming there does exist a formula, it might be useful to brute force a few and then to try to derive a formula from them. Good luck and let us know when you have something? — Bernhard Barker, Nov 10 '13 at 22:48
This is a standard problem known as integer partitioning. [Elegant python code for Integer Partitioning](http://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning) — Raymond Chen, Nov 10 '13 at 22:52
Do you need to print all the variations or just to calculate a number of the variations? — stuhlo, Nov 10 '13 at 22:52
I actually need to calculate just the number of variations. Thanks for the fast responses. I will study your initial answers in depth tomorrow. Also, at first glance, it seems that Integer partitioning is not the same thing, since it partitions a certain integer into smaller parts, it doesnt deal with digit sums. — user1047833, Nov 10 '13 at 22:58
Your "digit sums" are just partitions, though. You're looking for collections of numbers that add up to a given number. The only differences are that usually zero is excluded and you want permutations too (arrangements). — DSM, Nov 10 '13 at 23:13
@alko: so it's a restricted partition. The same algorithmic approaches still apply. — DSM, Nov 10 '13 at 23:57
You are correct. I actually dreamed about your offer and figured out that it was the right one. Thanks! — user1047833, Nov 11 '13 at 07:01
@DSM. Yep, you're totally correct about restricted. What I meant that algorithmic approach can be drastically simplified, as evaluation of number of partitions with summands `<=9` can be easily reduced to evaluation of partitions of maximum of 9 summands, and bound (`123` in example) entails max value resitriction on those summands (i.e. for each to be `<=3`). I'm pretty sure, sadly don't have time to check, that latter can be effectively evaluated recursively. — alko, Nov 11 '13 at 20:59

score 1 · Accepted Answer · answered Nov 11 '13 at 00:24

I think there is a recursive approach to solve this problem: consider a procedure int f(bool limit, int bit_count, int bit_sum), which calculates the number of variations that are no longer than bit_count bits that have a bit sum of bit_sum. The bool parameter limit denotes whether the limit (in your example, 123) takes effect.

Suppose Limit[i] denotes the i-th bit of the limit.

int f(bool limit, int bit_count, int bit_sum){
    if(bit_sum < 0)
        return 0;
    if(bit_count == -1)
        if(bit_sum == 0)
            return 1;
        else
            return 0;

    int ans = 0;
    for(int i = 0; i <= limit ? Limit[bit_count] : 9; i++){
        ans += f(limit && i == Limit[bit_count], bit_count - 1, bit_sum - i);
    }
    return ans;
}

In your example of bit sum as 6 and upper limit as 123, Limit[2] = 1, Limit[1] = 2, Limit[0] = 3. The answer is f(true, 2, 6).

For the sake of quick, you can convert this recursive approach into a dynamic programming approach by a record table. The time complexity of the corresponding DP approach is O(bit_sum * log(upper_limit)). I think this speed can meet your 1 second requirement.

score 1 · Answer 2 · answered Nov 11 '13 at 06:17

Create a DP based solution to calculate sum of at most k digits that sum to n.

F(k,n) = sum_i F(k-1, n-i)

Assume your max has k digits and the most significant digit is sig(max) and dropsig(max) is the number without the most significant digit.

G(k,max,n) = F(k-1, n)+ G(k-1, dropsig(max), n-sig(max) ) + sum_i (k-1, n-i) for i = 1 to sig(max) -1 .

Obviously, you have to take care of corner cases. But here is the summary.

The first component corresponds to cases where the length of the numbers are less than the length of maximum number.

The second component corresponds to cases where the most significant digit of solution is same as the maximum significant digit of the max.

The third component corresponds to cases where most significant digit of the solution is less than significant digit of the max, but greater than or equal to 1.

Find all variations of a digit sum

2 Answers2