3
$\begingroup$

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! :)

$\endgroup$
  • $\begingroup$ So by this definition, 6210001000 is 10-special? $\endgroup$ – Dennis Meng Nov 15 '13 at 18:04
  • $\begingroup$ Yes, it is ! ;) $\endgroup$ – Christmas Bunny Nov 15 '13 at 18:44
  • $\begingroup$ BTW if I'm not mistaken, there's no $1$-special number, no $2$-special number and no $3$-special number. There is however at least one $4$-special number: $1210$. $\endgroup$ – celtschk Aug 17 '16 at 20:10
  • $\begingroup$ @celtschk The second OEIS list I gave agrees with you, and provides one more 4-special number: 2020. $\endgroup$ – Dennis Meng Aug 18 '16 at 3:46
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

Here's a proof there are no other $7$-special numbers.

In a $7$-special number $a_0a_1a_2a_3a_4a_5a_6$, each $a_k$ counts the number of numerals that appear $k$ times among the digits. Since there are $7$ digits in all, we have

$$0a_0+1a_1+2a_2+3a_3+4a_4+5a_5+6a_6=7$$

This immediately implies $a_4+a_5+a_6\le1$, so at least two of those digits are $0$'s and at most one is a $1$. Now if any of them are equal to $1$, then one of the other digits is at least $4$. To satisfy the displayed equation, that digit can only be the $a_0$. We also have $a_1\ge1$. But we can't have $a_1=1$, since we already have at least one $1$, so we must have $a_1\ge2$. This means there are at least two $1$'s among the digits, the next one being either $a_2$ or $a_3$. But this leaves at most three digits that can possibly be $0$'s, which contradicts the conclusion $a_0\ge4$.

So we now know that $a_4=a_5=a_6=0$. This means there are at least three $0$'s among the digits, hence $a_0\ge3$. On the other hand, it also means that there are no $4$'s, $5$'s, or $6$'s among the digits, so $a_0$ cannot be any of those numerals. Hence we must have $a_0=3$. This implies that $a_1$, $a_2$, and $a_3$ are all at least $1$. Writing them as $a_k=1+b_k$ and plugging into the displayed equation (along with the established values $a_0=3$ and $a_4=a_5=a_6=0$), we find

$$b_1+2b_2+3b_3=1$$

This is clearly enough to conclude that $3211000$ is the only $7$-special number.

There are plenty of other ways to let the logic of this argument run. I'd be quite happy to see something shorter and more to the point.

$\endgroup$
0
$\begingroup$

The general problem of an $n$-special sequence, i.e., a sequence $b_0$, ..., $b_{n-1}$ with the property that each number $i\,$ in the range $[0:n-1]$ occurs exactly $b_i$ times in the sequence, can also easily be solved. The easiest way known to me to get all $n$-special sequences with proof is the following.

Let $b_0$, ..., $b_{n-1}$ be an $n$-special sequence. Each $b_i$ is in the range $[0,n]$, because it refers to a count out of $n$ elements. $b_i=n$ is impossible; all elements would be $i$, also $b_i$ , but we know $i<n$.

Hence each element $b_i$ contributes $1$ to the sum $\sum_{i=0}^{n-1}{b_i}$, i.e., this sum is $n$. More strictly, the sum of the positive $b_i$ is $n$. There are $n-b_0$ positive $b_i$.

$b_0=0$ is also impossible (this also means no element is $0$, a contradiction). Thus there are $n-b_0-1$ positive $b_i$ with $i>0$, and their sum is $n-b_0$. Hence one is $2$ and the others (if existing) are $1$. We obtain

a) If $b_0\le 2$, then $b_i=0$ for $i\ge 3$, $n=b_0+b_1+b_2$.
b) If $b_0\ge 3$, then $b_{b_0}=1$, $b_i=0$ for $i\ge 3$ and $i\ne b_0$, $n=b_0+b_1+b_2+b_{b_0}$ .
c) If $b_0=2$, then $b_2=2$.
d) If $b_0\ne 2$, then $b_2=1$.

We now make a case distinction by $b_0$.

$b_0=1$: We have $b_2=1$, $b_i=0$ for $i\ge 3$, $b_1=2$, $n=1+2+1=4$, and $b_3=0$.
$\quad$ $\quad$ $\ $ This is the solution 1 2 1 0.

$b_0=2$: We have $b_2=2$, $b_i=0$ for $i\ge 3$, thus $b_1\lt2$.
$\quad$ $\quad$ $\ $ If $b_1=0$, then $n=2+0+2=4$, $b_3=0$. This is the solution 2 0 2 0.
$\quad$ $\quad$ $\ $ If $b_1=1$, then $n=2+1+2=5$, $b_3=b_4=0$. This is the solution 2 1 2 0 0.

$b_0\ge 3$: We have $b_2=1$, $b_{b_0}=1$, $b_i=0$ for $i\ge 3$ and $i\ne b_0$, and $b_1=2$.
$\quad$ $\quad$ $\ $ Thus $n=b_0+b_1+b_2+b_{b_0}=b_0+2+1+1=b_0+4$, i. e., $n\ge 7$ and $b_0=n-4$.
$\quad$ $\quad$ $\ $ This is the solution (n-4) 2 1 (n-7 times 0) 1 0 0 0 for each $n\ge 7$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.