Editing Decimal range decomposition
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
==Informal idea== | ==Informal idea== | ||
− | Consider the following problem: given natural number <math>N</math>, how many of the natural numbers between 1 and <math>N</math>, inclusive, have a non- | + | Consider the following problem: given natural number <math>N</math>, how many of the natural numbers between 1 and <math>N</math>, inclusive, have a (non-strictly) descending sequence of digits? That is, each digit is less than or equal to the digit on its left, if any. For example, 100 and 321 qualify, but 101 and 123 do not. Assume that the [[naive algorithm]] is not efficient enough as <math>N</math> can have up to, say, 15 digits, so performing <math>N</math> loop iterations is out of the question. |
It is hard to find an explicit formula for this quantity, but notice that there are some ranges of natural numbers for which we ''can'' write down a closed form. For example, if the range, instead of being from 1 to <math>N</math>, were to be from 35000 to 35999, we know at a glance that the answer is 0, since any number starting with the prefix "35" does not have a descending digit sequence. If instead the range were 53000 to 53999, the question becomes: in how many ways can we fill in the digits <math>xyz</math> so that <math>53xyz</math> has a descending digit sequence? Well, clearly, each of the digits <math>xyz</math> can only be 0, 1, 2, or 3. How many ways are there to fill in three slots, each with one of four possible digits, so that the resulting sequence is descending? This can easily be calculated as the binomial coefficient <math>\binom{3 + 4 - 1}{4 - 1} = 20</math>. | It is hard to find an explicit formula for this quantity, but notice that there are some ranges of natural numbers for which we ''can'' write down a closed form. For example, if the range, instead of being from 1 to <math>N</math>, were to be from 35000 to 35999, we know at a glance that the answer is 0, since any number starting with the prefix "35" does not have a descending digit sequence. If instead the range were 53000 to 53999, the question becomes: in how many ways can we fill in the digits <math>xyz</math> so that <math>53xyz</math> has a descending digit sequence? Well, clearly, each of the digits <math>xyz</math> can only be 0, 1, 2, or 3. How many ways are there to fill in three slots, each with one of four possible digits, so that the resulting sequence is descending? This can easily be calculated as the binomial coefficient <math>\binom{3 + 4 - 1}{4 - 1} = 20</math>. |