INumbers with increasing digits are numbers like 12345 , 11111 , 12489 ,78999(no digit is exceeded by the digit to its left). For the past few days I have been looking for an algorithm to count the number of increasing numbers below a given limit. Does anyone have any Ideas?

## Comments

Sort by:

TopNewestBijection, I think. – Zi Song Yeoh · 4 years, 6 months ago

Log in to reply

– Thaddeus Abiy · 4 years, 6 months ago

By bijection do you mean a function of some sort that map the value of the first digit to the number of possible increasing numbers that begin with that digit? I have tried that and I have found that the number of two digit increasing numbers that begin with the digit D are given by 10 - D. For three digit increasing numbers it becomes the \( \sum_{i=1}^{10-D})\). I was unable to generalise further but it seems for four digit increasing numbers it seems we can count them by summing the sum of the previous result and this continues resulting in some kind of recursive summation sequence. I was unable to find any function that models these results.Log in to reply

This is a classic example of the Stars and bars problem. The answer is \[\dbinom{D+8}{8}\] – Marvis Narasakibma · 4 years, 6 months ago

Consider a \(D\) digit number with digit \(j \in \{1,2,3,\ldots,9\}\) appearing \(a_j\) times. Given \(a_1,a_2,\ldots,a_9\) there is only one unique way to form a number with the digits in increasing order i.e. if we are given \(D=20\) and \(a_1 = 2, a_2 = 3, a_3 =1, a_4 = 7, a_5 =4, a_6 = 1, a_7 = 1,a_8 =0\) and \(a_9 = 1\), then this corresponds to the unique number with increasing digits \(11222344444445555679\). Similarly, given a number with increasing digits, you can get unique \(a_1,a_2,\ldots,a_9\). Hence, the question boils down to how many non-negative integer solutions exists for \[a_1 + a_2 + a_3 + \cdots + a_9 = D \,\,\,\, (\spadesuit)\] since there is a bijection between the set of values for \(a_1,a_2,\ldots,a_9\) satisfying \((\spadesuit)\) and the set of numbers with digits increasing as discussed above.Log in to reply

. – Zi Song Yeoh · 4 years, 6 months agobijectionLog in to reply

– Thaddeus Abiy · 4 years, 6 months ago

Thank you. That was a very clear answer.Log in to reply

For an algorithm, as in "A computer will do this", you can use Dynamic programming, like this. (I will use a base b) Count DP[d][k] = the cardinality of such numbers that begin with the digit at most k, with dynamic programming. DP[d][k]=DP[d][k-1]+(DP[d-1][b]-DP[d-1][k-1]), that is, how many start with at most k-1 plus the ones that begin with k and as such, the next digit is less or equal to 9 and more than k-1. (Although you can probably express DP[d][k] as a combination of the sorts of d+9 in k or so, but it would still be calculated in almost the same time asymptotically). Begin with DP[d][0]=0 and DP[1][k]=k. Then, if your number is 0A

n..A0 (Ai is a digit), the answer is DP[n+1][An-1]-DP[n+1][0]+(if An<=A(n-1)) (DP[n][A(n-1)]-DP[n][An-1] +(A(n-1)<=A(n-2) ( DP[n-1][A(n-2)-1]-DP[n][A(n-1)-1]+(...)) ) , checking if the first number is less than An, then if it is An and if there is any valid, and then assuring the next digit is less or equal than A(n-1) but more than An, etcetera, until A1 and A0. It would run in O(nb), with n digits in base b. – Diego Roque · 4 years, 6 months agoLog in to reply

– Thaddeus Abiy · 4 years, 6 months ago

I had something similar in recursion in the beginning.I think understand your DP algo but would you mind posting the code in any language of your choosing(preferably pseudocode or python)? Would it not be simpler to do a direct implementation from the ideas above? The only setback I see when it comes to using the direct approach is that it makes use of binomial coefficients which are dependent on the computation of large factorials which slows down the code. But that can be easily remedied with a simple memoization of the factorials for reference when computing them in the future..So basically how faster would the DP algorithm be??p.s Im working only with decimal numbersLog in to reply

n] +if(An<=A(n-1)) (DP[n][An]-DP[n][A(n-1)]+if(A(n-1)<=A_(n-2))(...) ). Also, Haskell rocks, so here is a Haskell solution.let digitToInteger = toInteger . (Data.Char.digitToInt) let comb n m | m==0 = 1 | otherwise= div (product [(n-m+1)..n]) (product [1..m]) let dp b d k = comb (d+b-k-1) (b-k-1) let sol b n (x:y:xs) | n==1 = (dp b n $ digitToInteger x)-(dp b n $ digitToInteger y) | otherwise = (dp b n $ digitToInteger x)-(dp b n $ digitToInteger y)+if ((digitToInteger y)<=(digitToInteger $ head xs)) then sol b (n-1) (y:xs) else 0 let incDigit b n = (sol b (toInteger $ length num) ('0':num) where num=show n) -1

(this is in the GHCi) So if you call incDigit b n it gives you the cardinality of such numbers ones strictly less than n in base b, taking in consideration the -1 because of "0". This works with bigInts, so there is no upperbound (other than the machine's one). But even if it didn't use upper bounds, incDigit 10 (10^100) is about 2^41, so both codes give the same result (4263421511271 in case you are wondering), in less than a second. – Diego Roque · 4 years, 6 months ago

Log in to reply

– Diego Roque · 4 years, 6 months ago

This C++ code reads a base B, a number num, and calculates how many are strictly below num. I changed it a little, instead of DP[d][0]=0, it is DP[d][0]=DP[d][base-1]. The reason I did it like this is that C++ does not have native support for bignums (Boost library can help here). This solution runs in time O(bn) where b is the base (say, 10) and n is the number of digits. (I don't know how to format a code here, so I will use github) This code should run in under a (half a?) second easily. https://gist.github.com/diego9627/b9d9ec605cf8a1650000Log in to reply

– Thaddeus Abiy · 4 years, 6 months ago

Thanks bro.. Ive never worked with dynamic programming before, I ve just heard of how it works. Its really cool . Do you know a site, with practice problems I could use.Log in to reply

– Diego Roque · 4 years, 6 months ago

SPOJ, usaco training gate, Project Euler, UVA online judge, Codeforces and TopCoder. All of these but Project Euler are more USACO/IOI-styleLog in to reply

There are \( {n+9 \choose 9} \) increasing number, where n is the number of digits. – Silvio Sergio · 4 years, 6 months ago

Log in to reply

0,0,0,0,0,0,0, = ,,,,,,,

+++++++++0,0,0,0,0,0,1, = ,,,,,,+,

++++++++0,1,1,3,4,4,7, = ,+, ,++,+, ,+++,

++2,2,2,2,5,5,9, = ++, , , ,+++, ,++++,

9,9,9,9,9,9,9, = +++++++++,,,,,,,

I added as last term the unused

+.Each sequence is a combination of n "," and 9 "+" !

If leading zeros are not permitted (it means no 0 at all!), the increasing numbers are \({n+8 \choose 8}\). In general, there are \({n+B-1 \choose n}\) increasing n-digit number with B digit (base B!). For example, there are 136 3-digits increasing hex numbers, or 9 increasing 8-bit numbers. – Silvio Sergio · 4 years, 6 months ago

Log in to reply

– Thaddeus Abiy · 4 years, 6 months ago

Thanks.Log in to reply

Just select any five numbers(For distinct digits) , they can obviously be arranged in only one such order. Do the same for two same digits and other cases. – Nishant Rai · 4 years, 6 months ago

Log in to reply

– Thaddeus Abiy · 4 years, 6 months ago

Are you saying I should compute all the possible ways to select D digits from the nine possible digits to count the number of all the possible D digit increasing numbers?If so, that wouldn't work if the increasing number has more than nine digits, and also if it has repeats within it.Log in to reply

– Tan Li Xuan · 4 years, 6 months ago

He said below a given limit,not only 5 digit numbersLog in to reply

– Zi Song Yeoh · 4 years, 6 months ago

Yes.Log in to reply

Is there a simpler method? I don't understand bijection. – Tan Li Xuan · 4 years, 6 months ago

Log in to reply