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
8 years, 4 months ago
No vote yet
6 votes
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Bijection, I think.
Log in to reply
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 ∑i=110−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
Consider a D digit number with digit j∈{1,2,3,…,9} appearing aj times. Given a1,a2,…,a9 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 a1=2,a2=3,a3=1,a4=7,a5=4,a6=1,a7=1,a8=0 and a9=1, then this corresponds to the unique number with increasing digits 11222344444445555679. Similarly, given a number with increasing digits, you can get unique a1,a2,…,a9. Hence, the question boils down to how many non-negative integer solutions exists for a1+a2+a3+⋯+a9=D(♠) since there is a bijection between the set of values for a1,a2,…,a9 satisfying (♠) 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 (8D+8)
Log in to reply
Thank you. That was a very clear answer.
This is what I meant by bijection.
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.
Log in to reply
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.
He said below a given limit,not only 5 digit numbers
Log in to reply
Yes.
There are (9n+9) increasing number, where n is the number of digits.
Log in to reply
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 (8n+8). In general, there are (nn+B−1) 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.
Log in to reply
Thanks.
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.
Log in to reply
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
Log in to reply
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
Log in to reply
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
SPOJ, usaco training gate, Project Euler, UVA online judge, Codeforces and TopCoder. All of these but Project Euler are more USACO/IOI-style
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] = (b−k−1d+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.
Is there a simpler method? I don't understand bijection.