[Math] The number 3211000 is 7-special

algorithmscontest-mathelementary-number-theorynumber theorypuzzle

Define a positive integer $k$ to be $n$-special if it satisfies the following properties:

  1. It has $n$ digits (0, 1, …, 9)
  2. 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:

  1. How many $7$-special numbers are there? Can you prove it?

  2. For what positive integer $n$ does there not exist any $n$-special numbers?

  3. 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$$

Related Question