Waste less time on Facebook — follow Brilliant.
×

Number of Numbers with increasing digits less or equal to some number

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?

Note by Thaddeus Abiy
4 years, 6 months ago

No vote yet
6 votes

Comments

Sort by:

Top Newest

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

Log in to reply

@Zi Song Yeoh 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. Thaddeus Abiy · 4 years, 6 months ago

Log in to reply

@Thaddeus Abiy 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. 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

Log in to reply

@Marvis Narasakibma This is what I meant by bijection. Zi Song Yeoh · 4 years, 6 months ago

Log in to reply

@Marvis Narasakibma Thank you. That was a very clear answer. Thaddeus Abiy · 4 years, 6 months ago

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 0An..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 ago

Log in to reply

@Diego Roque 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 numbers Thaddeus Abiy · 4 years, 6 months ago

Log in to reply

@Thaddeus Abiy If you define DP[d][k] as the cardinality of the numbers with d digits and at least k in the first digit, in the base b, then DP[d][k] can be solved by a DP similar to the one on my code. But also, DP[d][k] is the cardinality of d-digit numbers in base b-k (subtract k from each number). Then DP[d][k] = \( \binom{d+b-k-1}{b-k-1}\). So you can calculate it by the common DP for binoms, by your method, by some cool library, etc, and the solution will be sol=DP[n+1][0]-DP[n+1][An] +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

@Thaddeus Abiy 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/b9d9ec605cf8a1650000 Diego Roque · 4 years, 6 months ago

Log in to reply

@Diego Roque 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. Thaddeus Abiy · 4 years, 6 months ago

Log in to reply

@Thaddeus Abiy SPOJ, usaco training gate, Project Euler, UVA online judge, Codeforces and TopCoder. All of these but Project Euler are more USACO/IOI-style Diego Roque · 4 years, 6 months ago

Log 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

@Silvio Sergio Each increasing number can be represented by the sequence of increments. For example,
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

@Silvio Sergio Thanks. Thaddeus Abiy · 4 years, 6 months ago

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

@Nishant Rai 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. Thaddeus Abiy · 4 years, 6 months ago

Log in to reply

@Nishant Rai He said below a given limit,not only 5 digit numbers Tan Li Xuan · 4 years, 6 months ago

Log in to reply

@Tan Li Xuan Yes. Zi Song Yeoh · 4 years, 6 months ago

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

×

Problem Loading...

Note Loading...

Set Loading...