Let $S$ be the sequence of all positive integers whose decimal digits add to exactly 7, in increasing order:
$$S = \langle7, 16, 25, \ldots, 70, 106, 115, 124, \ldots 160, 205, \ldots, 10230010, \ldots\rangle$$
What is an efficient algorithm for finding the $n$th element of this sequence for a given positive integer $n$?
On
You can solve this by doing a binary search on the number of elements in the sequence below some number $M$.
To count how many numbers there are $\le M$ we must find a way to construct the numbers. The idea is the following: Go through each prefix of $M$, and assume that the next digit is less than the corresponding digit of $M$. Then the remaining digits $d_k,\dots,d_n$ can be set freely with a constraint of the form $d_k + \dots + d_n = l$, where $l$ is what is left of $7$ after subtracting the first digits. This is a standard counting problem.
On
A good point to start is to quickly determine the number of such numbers below certain "mielstone" limits. Using the usual stars and bars argument, there are $m+7\choose 7$ such numbers below $10^m$. And more generally, if $a$ is any number with digitsum $ s\le 7$, then there are $m+7-s\choose 7-s$ such numbers $x$ with $a\cdot 10^m\le x<(a+1)\cdot 10^m$. These facts allow you to find rather quickly suitable estimates that converge to the desired result.
On
Let me try answering it a fun way... base 10 will use 9x-2 to make a set like (7, 16, 24,...100000000006) Now what numbers do we need to ignore? Those that sum greater than 7...now there's a trick to only get these numbers from the set above in programming.... when you hit a number that sums over 7 using the above series you take the number, find the last digit with a number in it, subtract 1 and move it to the end, and add 1 to the digit after... So for 70 since 7 is the last digit we subtract 1 to make 6, move that to the end (06) and add a 1 to the digit after 7 (106) to get the next number in the series... 160 would jump to 205 (6-1=5, add 1 after) 250 will be 304 340 will be 403 430 will be 502 520 will be 601 610 will be 700 700 will be 1006 1,060 will be 1,105 ... 10,600,000 will be 11,000,005
so you could do something like this... input n ans=7 n=n-1 do until n=0 Ans=Ans+9 If sum(eachnuminans)>7 Ans=Ans-9 Pos=Find(first nonzero location) X=ans(pos) Ans(pos)=0 Ans(pos+1)=ans(pos+1)+1 Ans(1)=X-1 Loop n=n-1 Loop
Observation: after $7,000,000$, all subsequent numbers from this list will be formed by sequentially inserting $0$'s into the $7$ digit numbers in the list (since after $1,111,111$, there can be no "new" combinations). As such, if we can formulate the sequence up to $7,000,000$, we'll be done in general.
Aim: to efficiently calculate the sequence up to $7,000,000$, at which point all future terms depend on previous terms. In doing so, generate a list of all 7 digit combinations, which will become the "base" for all further terms.
The method:
Some more detail:
In base $10$, the trick for working out if a number is divisible by $9$ is if and only if the sum of the digits is a multiple of $9$. The proof for this is slightly enlightening:
$$a_na_{n-1}\ldots a_0 = \sum_{i=0}^na_i10^i\equiv \sum_{i=0}^na_i\mod9$$ as $10\equiv 1 \mod 9$. What's important here is that $10 = 9+1$. The same thing will work in base $8$ with multiples of $7$
When we translate the multiples of $7$ into base $8$, we get:
$$7\mapsto7\\14\mapsto16\\21\mapsto 25\\28\mapsto34\\35\mapsto43\\\vdots$$
In base $8$ the multiples of $7$ are exactly the numbers whose digits sum to a multiple of $7$ in numerical order. If we then interpret the numbers we get as if they were in base $10$, we will get an almost one-to-one correspondence with the base $10$ integers whose digit sum to $7$.
Now this will also include numbers whose digits sum to $14, 21, \ldots$.