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

Question

A large number can be comma formatted to read more easily into groups of three. E.g. 1050 = 1,050 and 10200 = 10,200.

The sum of each of these groups of three would be:

1050=1,050 gives: 1+50=51

10200=10,200 gives: 10+200=210

I need to search for matches in the sum of the groups of threes.

Namely, if I am searching for 1234, then I am looking for numbers whose sum of threes = 1234.

The smallest match is 235,999 since

235+999=1234. No other integer less than 235,999 gives a sum of threes equal to 1234.

The next smallest match is 236,998 since 236+998=1234.

One can add 999 each time, but this fails after reaching 999 since an extra digit of 1 is added to the number due to overflow in the 999.

More generally, I am asking for the solutions (smallest 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

Note there are infinite solutions to this for any positive integer x.

Given a solution a, how would one find out how many smaller solutions exist?

for example, for the solution:

236,998

there exists only one smaller solution as before, namely, 235,999

But for a large solution to 1234 such as the huge number:

50,100,198,302,100,220,030,134,100

it could take years to compute the number of previous solutions via computer loops from smallest numbers until one finally reaches this number.

is there some kind of mathematical formula to calculate how many smaller solutions there are for a given solution?

so for the above number:

50,100,198,302,100,220,030,134,100

exactly how many smaller solutions are there which also give a sum of threes = 1234?

Answer 1

Possible partial algorithm ideas:

• induce partitions of partitions so 235,999 represents 1,235,998 as well as 1,234,999 etc.
• add parity matched parts , and average those parts out ... ex. 237,997 and 235,999 averaging parts gives you 236,998 (now it doesn't always work out, only when parts are increasing in one part matched with same amount of decreasing in the other for starters)
• use permutations
• use addition of own parts 50,100,198,302,100,220,030,134,100 generates 150,198,302,100,220,030,134,100 for example.
• use averaging own parts( same parity matters for a whole number answer but carry halves onto other values perhaps ) 150,198,302,100,220,030,134,100 produces 174,174,302,100,220,030,134,100 as an example.
• probably many more.