# A 10-digit number whose $n$th digit gives the number of $(n-1)$s in it

There is a ten-digit number $X$ such that its first (left-most) digit is equal to the number of $0$s in $X$, the second digit gives the number of $1$s in $X$, and so on. The last (right-most) digit gives the number of $9$s in $X$. Find $X$.

Aren't there a lot of possibilities for a solution?

It looks like you can solve it recursively.

1. The first number can't be 0, because then the number of zeros isn't 0
2. Can it be 9? => 9,000, 000,00? NO
3. Can it be 8? => 8,?00,000,010 NO- but there is contradiction
4. Can it be 7? => 7,?00,000,100 NO
5. Can it be 6? => 6,210,001,000 Yes
6. Can it be 5? => 5,???,???,???

And you play this way a little bit. I guess the solution is the only one

No. There is exactly one.

+1 to Amulya for an interesting question.

+1 to ipoteka for doing it the hard way :)

/*
There is a ten digit number X such that
its first (left-most) digit is equal to the number of 0s in X,
the second digit gives the number of 1s in X,
and so on.
The last (right-most) digit gives the number of 9s in X. Find X.
isn't there a lot of probabilities to the solution?
*/

#include <iostream>

int main
(
void
)
{
std::cout << "Working" << std::endl;
const int N = 10;
int digits[N] = { 0 };

for (int a = 0; a < N; a++)    {   digits[a]++;    std::cout << "progress " << a << std::endl;
for (int b = 0; b < N; b++)    {   digits[b]++;
for (int c = 0; c < N; c++)    {   digits[c]++;
for (int d = 0; d < N; d++)    {   digits[d]++;
for (int e = 0; e < N; e++)    {   digits[e]++;
for (int f = 0; f < N; f++)    {   digits[f]++;
for (int g = 0; g < N; g++)    {   digits[g]++;
for (int h = 0; h < N; h++)    {   digits[h]++;
for (int i = 0; i < N; i++)    {   digits[i]++;
for (int j = 0; j < N; j++)    {   digits[j]++;

if
(
(a == digits[0]) &&
(b == digits[1]) &&
(c == digits[2]) &&
(d == digits[3]) &&
(e == digits[4]) &&
(f == digits[5]) &&
(g == digits[6]) &&
(h == digits[7]) &&
(i == digits[8]) &&
(j == digits[9])
)
std::cout << a << b << c << d << e << f << g << h << i << j << std::endl;

digits[j]--;    }
digits[i]--;    }
digits[h]--;    }
digits[g]--;    }
digits[f]--;    }
digits[e]--;    }
digits[d]--;    }
digits[c]--;    }
digits[b]--;    }
digits[a]--;    }

std::cout << "Complete" << std::endl;

return 0;
}


Output:

Working
progress 0
progress 1
progress 2
progress 3
progress 4
progress 5
progress 6
**6210001000**
progress 7
progress 8
progress 9
Complete
Press any key to continue . . .

• It's not .... the last digit should at least be one for the nine in the start.... – JuniorCompressor Apr 18 '15 at 0:35
• To Keep for the generations to come to see the sorts of mistakes that I make, or the call of sweet oblivion.... Sigh – EvilTeach Apr 18 '15 at 0:38
• I misread the question. Thank you JC. Here is a program to atone for my sins. – EvilTeach Apr 18 '15 at 1:18
• It was a pleasant way. For a moment i felt what a lisp machine feels :3 – ipoteka Apr 18 '15 at 1:27
• Euler 5 is similar in some respects – EvilTeach Apr 18 '15 at 1:31

We can solve this mathematically for the general case, which includes n = 10.

Let's call our solution s, and p the subset of s, where s[i] > 0, that is, the set of represented numbers (any zero is a number or index that is not represented).

We can say that n = sum of all frequencies = sum p

Now let's call p' the subset of p without s[0], which are frequencies only of numbers greater than zero.

Clearly sum p' = sum p - s[0] = length p, which is simply the count of how many numbers in s are greater than zero.

Remember that length p = length p' + 1. Now if length p > 4, we know that sum p' > 4 and we are left with an m length partition (p') that must sum to m+1, where m > 3. The only way this can be done is with (m-1) 1's and one 2, e.g., [1,1,1,2] in the case of m=4 (by definition there are no zeros in p'). Such a partition could not make sense as a solution to our problem, and so we see that p, or the subset of numbers greater than zero in our solution, must have less than 5 elements.

Now we can solve for specific cases:

Every solution must have s[0] > 0 since a zero in the zero column would invalidate the solution.

length p = 1 would only be possible if s[0] could be both zero and greater than zero at the same time.

length p = 2 implies p' = [2], and so there are two zeros and two 2's, s=[2,0,2,0]

length p = 3 implies p' = [1,2]. Since we know there is only one more s[i], which is s[0] > 0, the 2 in p' must either refer to itself, in which case we have s=[2,1,2,0,0]; or to two 1's and therefore s=[1,2,1,0]

length p = 4, p' = [2,1,1]. In this case the 2 could only be referring to the two 1's and we must assume s[0] > 2, which also means sum p >= (3+2+1+1 = 7). This is the final / general case: s[1]=2, s[2]=1. The last 1 refers to s[0] and so its index equals s[0]. Remembering that sum p - s[0] = length p, we get, s[0] = n - 4, and the solution, for length p = 4, n > 6: s=[n - 4,2,1...1,0,0,0]

• I arrived at the same conclusion, but I don't really follow your line of reasoning for the n>6 case – harold Apr 18 '15 at 1:31
• @harold which part are you having trouble following? – גלעד ברקן Apr 18 '15 at 6:20
• The end, that sum p - length p deal, why does that have n-4 as solution? – harold Apr 18 '15 at 8:05
• @harold Simple arithmetic: sum p was stated equal to n early on; length p is defined as 4 for the last case I examined. So s[0] = n - 4. length p must be less than 5 was explained earlier. Are you having trouble understanding sum p' = sum p - s[0] = length p ? – גלעד ברקן Apr 18 '15 at 12:11
• Oh nevermind, I just got lost in all those definitions – harold Apr 18 '15 at 12:16

You can use constraint programming.

There is the obvious constraint, namely the definition: every element must be the number of occurrences of that number. That already gives a simple pruning rule: the sum of the items must be n (why? well there are n items, and whatever number they are they will be counted somewhere).

But we can go one step further. A number x in place i means there will be x i's (not surprising so far), this means that actually the sum of array[i] * i (over all i) will also be n, which is (mostly) a stronger pruning rule (except for zero).

Most of them (for 7 and higher) end up looking like this:

n-4 2 1 .... 1 ...


With the second 1 located at the index n-4. This pattern doesn't work for some small n's, namely 6 and below, most of which have no valid pattern. 4 and 5 are special cases:

4: 1 2 1 0
5: 2 1 2 0 0