Find nth occurence of groups of thousands which sum to a given number in lexical order

Question

A previous question asked for the solutions in lexical order (lowest to highest) to

a+b+c+d… = x

where a,b,c,d… is an arbitrary number of integers between 0-999 and x is a fixed integer

An answer was given which fully computes this efficiently using python.

However, for very large numbers, the loop could take years to complete.

For example, the huge number:

304,153,525,784,175,759

is a solution for x=2700 since the groups of threes add up to 2700

304+153+525+784+175+759 = 2700

However, to loop through the algorithm to get the n^th solution which equals this number would take months or years.

Is there a way to calculate the n^th solution directly? I.e. for a known solution, to calculate how many solutions are less than this one.

Answer 1

Here is a way to find the index of a solution (or: how many smaller solutions there are). The code has two parts:

• Find how many solutions there are for some fixed number n of groups for a given sum x. This is a recursive function. Basically, for n groups and sum x, for all k from 0 to 999, sum up how many solutions there are with n-1 groups and sum x-k. As the recursive function often is called with the same values, the results are stored in a memoization dictionary to be used immediately the next time.

• Use this function to calculate how many smaller solutions there exist. This is a similar way of summing. E.g. for 6 groups and starting with 304, calculate how many 5-groups there are which start after 303 and sum to x-303, add the number of 5-groups which start with 302 and sum to x-302, etc. Then, taking 304,153 as start, find how many 4-groups start after 304,152 and sum to x-304-152, etc.

Here is the complete code, tested for quite some inputs (test generated by the previous program). It just takes a few seconds for the given 18-digit number.

grouping = 3
max_in_group = 10 ** grouping - 1
number_to_test = 304153525784175759  # number_to_test = '304,153,525,784,175,759'
d = {}  # dictionary for memoization

# count how many solutions there are for n groups summing to x, and each group being a number from 0 to max_in_group;
# when counting simple digit sums, n is the number of digits, and max_in_group should be 9;
# when counting in groups of thousands, n is the number of groups (digits / 3), and max_in_group should be 999
def count_digitsums(x, n, max_in_group=9):
    if not(0 <= x <= n * max_in_group):
        return 0
    elif n == 1:
        return 1
    else:
        if (x,n) in d:
            return d[(x,n)]
        s = 0
        for i in range(max_in_group+1):
            s += count_digitsums(x-i, n-1, max_in_group)
        d[(x, n)] = s
        return s


def find_index_of_number(number_to_test):
    global max_in_group
    a = []
    while number_to_test != 0:
        a.append(number_to_test % (max_in_group + 1))
        number_to_test //= max_in_group + 1
    print("number to test:", ",".join(f'{i:03d}' for i in a[::-1]))
    print("numbers should sum to:", sum(a))

    x = sum(a)  # all the solutions need this sum
    leftx = 0  # the sum of the numbers to the left of the group being processed
    s = 0
    for k in range(len(a) - 1, -1, -1):
        for l in range(a[k]):
            # e.g. when 6 groups and a[5] = 304, first take 303, count number in 5 groups which sum to x-303
            s += count_digitsums(x - leftx - l, k, max_in_group)
        leftx += a[k]
    print("number of smaller solutions:", s)
    print("index of this solution:", s + 1)
    return s + 1


d = {}
find_index_of_number(number_to_test)

Output:

number to test: 304,153,525,784,175,759
numbers should sum to: 2700
number of smaller solutions: 180232548167366
index of this solution: 180232548167367

Answer 2

Edit: this post only addresses how to find the next solution, given a particular solution.

OP asks additionally:

• Given an index n find the n^th solution without the need to generate all the earlier ones.
• Given a solution a, find out how many smaller solutions there exist.

As the algorithm efficiently finds the next solution, you just need to fill in your current solution.

Here is a way to fill in the current solution either as a large integer or as a string:

start = 304153525784175759  # start = '304,153,525,784,175,759'
x = 2700
grouping = 3
max_in_group = 10**grouping - 1

if start is not None:
    if isinstance(start, str):
        a = [int(s) for s in start.split(',')[::-1]]
    else: # suppose start is a large integer
        a = []
        while start != 0:
            a.append(start % (max_in_group+1))
            start //= max_in_group+1
else: # no start value given, start with the smallest
    a = [x]

If you prepend this to the rest of the other answer, you'll get the output:

304,153,525,784,175,759
304,153,525,784,176,758
304,153,525,784,177,757
304,153,525,784,178,756
304,153,525,784,179,755
304,153,525,784,180,754
304,153,525,784,181,753
304,153,525,784,182,752
304,153,525,784,183,751
304,153,525,784,184,750
304,153,525,784,185,749
304,153,525,784,186,748
...