Define a positive integer $k$ to be $n$-special if it satisfies the following properties:
- It has $n$ digits (0, 1, …, 9)
- The 1st digit is equal to the number of 0's in the decimal representation of $k$, the second digit is equal to the number of 1's, the third digit is equal to the number of 2's, etc
For instance, the number $3211000$ is $7$-special (since there are three 0's, two 1's, one 2, and one 3).
Questions:
-
How many $7$-special numbers are there? Can you prove it?
-
For what positive integer $n$ does there not exist any $n$-special numbers?
-
Is there an efficient algorithm to compute all $n$-special numbers, given any positive integer $n$?
Have fun and enjoy! 🙂
Best Answer
Just for kicks, I googled the 10-digit example (6210001000) that I mentioned in the comment, and found that these n-special numbers are apparently called self-descriptive numbers.
For your part 1), it doesn't list any other examples for 7, and judging from the OEIS list, there aren't any others. (As a heads-up, there's some base conversion going on in the list; your example is listed as 389305 (which gives 3211000 in base 7))
(Addendum: This list gives the numbers as you actually want them, though there are a few less entries)
For part 2), the article lists the three values of $n$ without any (2,3,6, though I guess 1 doesn't either if you want to count it)
For part 3), the article gives a general formula for getting more examples in higher bases, but only one per value of $n$. If I find anything about generating all (either more formulas or a proof that this is all of them), I'll update the answer. The formula itself is
$$(n-4)n^{n-1} + 2n^{n-2} + n^{n-3} + n^3$$