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?

5 years, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Bijection, I think.

- 5 years, 10 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.

- 5 years, 10 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. This is a classic example of the Stars and bars problem. The answer is $\dbinom{D+8}{8}$

- 5 years, 10 months ago

This is what I meant by bijection.

- 5 years, 10 months ago

Thank you. That was a very clear answer.

- 5 years, 10 months ago

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.

- 5 years, 10 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 numbers

- 5 years, 10 months ago

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.

- 5 years, 10 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/b9d9ec605cf8a1650000

- 5 years, 10 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.

- 5 years, 10 months ago

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

- 5 years, 10 months ago

There are $${n+9 \choose 9}$$ increasing number, where n is the number of digits.

- 5 years, 10 months ago

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.

- 5 years, 10 months ago

Thanks.

- 5 years, 10 months ago

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.

- 5 years, 10 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.

- 5 years, 10 months ago

He said below a given limit,not only 5 digit numbers

- 5 years, 10 months ago

Yes.

- 5 years, 10 months ago

Is there a simpler method? I don't understand bijection.

- 5 years, 10 months ago