the biggest self refrential number

[BMAD]

For rules on self refrential numbers see:

As per a special request, what is the largest sellf refrential number? And yes there actually is such a number.

Edited July 28, 2013 by BMAD

[Rainman]

6210001000. A self-referential number can't have more than 10 digits, since there are only 10 digits to refer to in the decimal system. The sum of the digits in a self-referential number is always equal to the number of digits, which is 10 in this case. If the first digit is >5, there can be no other digit of that value, so the digit refering to that value must be 1. Then the digit refering to 1 must be >1, and the digit refering to that value must be >0. So we have at least six 0s, at least two 1s, one digit refering to the number of 0s, and one digit refering to the number of 1s. This is at least 10 digits, with equality only if we have exactly six 0s and exactly two 1s. This leads to 6210001000. Any other 10 digit self-referential number, if they exist (which I doubt), must have a first digit <6.

[Rainman]

There are seven self-referential numbers in total (in the decimal system). They are 1210, 2020, 21200, 3211000, 42101000, 521001000, and 6210001000. (On a side note we could relax the definition to allow numbers with more than 10 digits if we defined exactly what the 11th and onward digits would represent.) Now for proving that these are the only self-referential numbers.

Notation: A self-referential number with N digits is written d₀d₁...d_N-1. Let S_k be the number of instances of the digit k. By definition, a self-referential number satisfies d_k=S_k for all k.

Observation 1: The first digit can never be 0. If d₀=0, then the number contains at least one 0, meaning S₀>0. But 0=d₀=S₀>0 is a contradiction.

Observation 2: Some digit must be 0. Otherwise S₀=0, which means d₀=0, which is impossible.

Observation 3: All digits can not be equal. Follows directly from observations 1 and 2.

Lemma A: A self-referential number d₀d₁...d_N-1 has no digit larger than N-1.

Proof: Suppose d_k>N-1 for some k. Then S_k=d_k>N-1, which means there are at least N digits k. But there are only N digits total, so all digits are k. This contradicts observation 3.

Lemma B: The digit sum of a self-referential number equals the number of digits.

Proof: d₀+d₁...+d_N-1 = S₀+S₁...+S_N-1 = (number of digits)-(number of digits larger than N-1) = (number of digits) by Lemma A.

Observation 4: The maximal digit sum is 10. Follows from Lemma B and the fact that the maximal number of digits is 10.

Lemma C: No digit except d₀ can be larger than 2. My proof for this is very long and ugly.*

Observation 5: Only one digit can be larger than 2. Follows directly from Lemma C.

Lemma D: After the third digit, there can be at most one non-zero digit.

Proof: Suppose d_p and d_q are both non-zero, where p and q are both larger than 2. Then S_p and S_q are both non-zero, meaning we have both a digit p and a digit q. This contradicts observation 5.

Corollary to Lemma D: If there is a non-zero digit after the third digit, that digit must be 1.

Proof: Suppose d_p>1 where p>2. Then S_p>1, meaning there is more than one instance of the digit p. Again, this contradicts observation 5.

Observation 6: There are at most four non-zero digits. The first three digits can be non-zero, and at most one digit after that.

Lemma E: Either d₁ or d₂ is <2.

Proof: We know that neither is >2 by Lemma C. So we only need to prove that both aren't equal to 2. Suppose they were. Then S₁=d₁=2, meaning we have two 1s. Only one of them can appear after the third digit by Lemma D. The second and third digit are occupied by 2s. So the first digit must be 1. Now look at the other 1. It represents a single instance of another non-zero digit m>2. This makes five non-zero digits (two 1s, two 2s, and one m), which contradicts observation 6.

Now it's time to break it down:

1. The case where d₀=1. This makes d₁=S₁>0. Also, d₁ can't be 1 since that makes S₁>1 which contradicts d₁=1. And d₁ can't be >2 by Lemma C. So d₁=2. We can't have d₂=0, and we must have d₂<2 by Lemma E. So d₂=1. Since we already have the two 1s and the one 2, there can be no more non-zero digits. We only need to put one 0 at the end and we get 1210.
2. The case where d₀=2. This makes d₂>0. If d₂=1, we can't find a value for d₁. It can't be 0 because we already have a digit 1, it can't be 1 because then we would have two digits 1, it can't be two because that would make two digits 2, and it can't be >2 by Lemma C. So d₂=2. Now d₁ could be either 0 or 1, bringing the solutions 2020 and 21200.
3. The case where d₀>2. Because d₀=m for some m>2, we have d_m=S_m>0. But by the corollary to Lemma D, such a digit can't be >1. So d_m=1. Now d₁ can't be 0 or 1, so it must be 2. Now d₂ can't be 0 or 2, so it must be 1. This makes four non-zero digits (d₀=m, d₁=2, d₂=1, and d_m=1), all other digits must be 0 by observation 6. For m=3 we get 3211000, for m=4 we get 42101000, for m=5 we get 521001000, and for m=6 we get 6210001000.

We have now studied all cases and found seven possible self-referential numbers. Now I must present my proof for Lemma C to complete the solution.

*Proof of Lemma C: Assume d_k=m for some m>2. We need to prove that k can only be 0.

• if k>3, we have S_k=d_k=m, that is m digits k, where m is at least 3 and k is at least 4. The sum of these digits is k*m, which is at least 4*3=12, higher than allowed maximum of 10.
• if k=3, we have S₃=m, that is m digits 3, where m is at least 3. The sum of these digits is 3m, which forces m=3 since the maximal digit sum is 10. Now we have d₃=S₃=3. But since S₃=3, we have d_p=3=S_p for some other non-zero number p. This yields another 3p towards the digit sum which was already 9, exceeding the maximum.
• if k=2, we have d₂=S₂=m. So we have at least three digits 2, and the digit d₂ which is at least 3. This already makes a digit sum of at least 9. Now look at the digit d_m. It can't be 0 since then S_m would be 0, which contradicts d₂=m. It can't be >1 because we can't afford another digit m. So d_m=1, which makes S₁>0, which means we need a digit 1 as well. This brings our digit sum up to the maximum of 10. Problem is there can't be another 1. Since we must have exactly one 1, and exactly one m, we have d₁=1 and d_m=1, which makes S₁>1, contradicting that d₁=1.
• finally if k=1, we have d₁=S₁=m. Now look at m. We know it is at least 3. What if it were larger? Then we would have at least four digits 1, and the digit d₁ which is at least 4, bringing the digit sum to at least 8. But each digit 1 refers to a single instance of some other digit. Besides a single 0 and a single m, we need at least two more single digits, the smallest being 2 and 3 which would bring our digit sum to at least 13. So m can only be 3. So d₁=s₁=3. The three 1s and the 3 representing them make a digit sum of 6, but we need more digits. Each 1 represents a single instance of some other digit. Look at d₃. It can't be 0 because S₃ is not 0. It can't be 2 because another digit 3 brings the digit sum to 9, and the digit 2 representing the two digits 3 brings it to 11. It can't be greater than 2 because another two digits 3 brings the digit sum from 6 to 12. Thus we have d₃=1. We need two more 1s. Let d_p=1 and d_q=1, where neither p or q can be 1 or 3. This raises the digit sum by p+q, so either p or q must be 0. Otherwise they would be at least 2 and 4, raising the digit sum from 6 to at least 12. So d₀=1. To recap this mess, we have d₀=1, d₁=3, d₃=1. Current digit sum 6 since we have another 1 to place. d_p=1 for some p other than 0,1, or 3. This represents a single instance of the digit p, which raises the digit sum by p, and also that digit p represents p instances of some other digit, raising the digit sum through the ceiling once again.

AND FINALLY IT IS DONE... this was A LOT easier to do in my head than to put down in text, and looking at all this text I wonder if an extensive breakdown of every number from 1 to 999999999 wouldn't have been just as fast. At least I can laugh evilly knowing that anyone who wants to proof-read my solution is in for a major headache, MUAHAHAHAHA *brain meltdown*

[gavinksong]

There are seven self-referential numbers in total (in the decimal system). They are 1210, 2020, 21200, 3211000, 42101000, 521001000, and 6210001000. (On a side note we could relax the definition to allow numbers with more than 10 digits if we defined exactly what the 11th and onward digits would represent.) Now for proving that these are the only self-referential numbers.

Notation: A self-referential number with N digits is written d₀d₁...d_N-1. Let S_k be the number of instances of the digit k. By definition, a self-referential number satisfies d_k=S_k for all k.

Observation 1: The first digit can never be 0. If d₀=0, then the number contains at least one 0, meaning S₀>0. But 0=d₀=S₀>0 is a contradiction.

Observation 2: Some digit must be 0. Otherwise S₀=0, which means d₀=0, which is impossible.

Observation 3: All digits can not be equal. Follows directly from observations 1 and 2.

Lemma A: A self-referential number d₀d₁...d_N-1 has no digit larger than N-1.

Proof: Suppose d_k>N-1 for some k. Then S_k=d_k>N-1, which means there are at least N digits k. But there are only N digits total, so all digits are k. This contradicts observation 3.

Lemma B: The digit sum of a self-referential number equals the number of digits.

Proof: d₀+d₁...+d_N-1 = S₀+S₁...+S_N-1 = (number of digits)-(number of digits larger than N-1) = (number of digits) by Lemma A.

Observation 4: The maximal digit sum is 10. Follows from Lemma B and the fact that the maximal number of digits is 10.

Lemma C: No digit except d₀ can be larger than 2. My proof for this is very long and ugly.*

Observation 5: Only one digit can be larger than 2. Follows directly from Lemma C.

Lemma D: After the third digit, there can be at most one non-zero digit.

Proof: Suppose d_p and d_q are both non-zero, where p and q are both larger than 2. Then S_p and S_q are both non-zero, meaning we have both a digit p and a digit q. This contradicts observation 5.

Corollary to Lemma D: If there is a non-zero digit after the third digit, that digit must be 1.

Proof: Suppose d_p>1 where p>2. Then S_p>1, meaning there is more than one instance of the digit p. Again, this contradicts observation 5.

Observation 6: There are at most four non-zero digits. The first three digits can be non-zero, and at most one digit after that.

Lemma E: Either d₁ or d₂ is <2.

Proof: We know that neither is >2 by Lemma C. So we only need to prove that both aren't equal to 2. Suppose they were. Then S₁=d₁=2, meaning we have two 1s. Only one of them can appear after the third digit by Lemma D. The second and third digit are occupied by 2s. So the first digit must be 1. Now look at the other 1. It represents a single instance of another non-zero digit m>2. This makes five non-zero digits (two 1s, two 2s, and one m), which contradicts observation 6.

Now it's time to break it down:

1. The case where d₀=1. This makes d₁=S₁>0. Also, d₁ can't be 1 since that makes S₁>1 which contradicts d₁=1. And d₁ can't be >2 by Lemma C. So d₁=2. We can't have d₂=0, and we must have d₂<2 by Lemma E. So d₂=1. Since we already have the two 1s and the one 2, there can be no more non-zero digits. We only need to put one 0 at the end and we get 1210.
2. The case where d₀=2. This makes d₂>0. If d₂=1, we can't find a value for d₁. It can't be 0 because we already have a digit 1, it can't be 1 because then we would have two digits 1, it can't be two because that would make two digits 2, and it can't be >2 by Lemma C. So d₂=2. Now d₁ could be either 0 or 1, bringing the solutions 2020 and 21200.
3. The case where d₀>2. Because d₀=m for some m>2, we have d_m=S_m>0. But by the corollary to Lemma D, such a digit can't be >1. So d_m=1. Now d₁ can't be 0 or 1, so it must be 2. Now d₂ can't be 0 or 2, so it must be 1. This makes four non-zero digits (d₀=m, d₁=2, d₂=1, and d_m=1), all other digits must be 0 by observation 6. For m=3 we get 3211000, for m=4 we get 42101000, for m=5 we get 521001000, and for m=6 we get 6210001000.

We have now studied all cases and found seven possible self-referential numbers. Now I must present my proof for Lemma C to complete the solution.

*Proof of Lemma C: Assume d_k=m for some m>2. We need to prove that k can only be 0.

• if k>3, we have S_k=d_k=m, that is m digits k, where m is at least 3 and k is at least 4. The sum of these digits is k*m, which is at least 4*3=12, higher than allowed maximum of 10.
• if k=3, we have S₃=m, that is m digits 3, where m is at least 3. The sum of these digits is 3m, which forces m=3 since the maximal digit sum is 10. Now we have d₃=S₃=3. But since S₃=3, we have d_p=3=S_p for some other non-zero number p. This yields another 3p towards the digit sum which was already 9, exceeding the maximum.
• if k=2, we have d₂=S₂=m. So we have at least three digits 2, and the digit d₂ which is at least 3. This already makes a digit sum of at least 9. Now look at the digit d_m. It can't be 0 since then S_m would be 0, which contradicts d₂=m. It can't be >1 because we can't afford another digit m. So d_m=1, which makes S₁>0, which means we need a digit 1 as well. This brings our digit sum up to the maximum of 10. Problem is there can't be another 1. Since we must have exactly one 1, and exactly one m, we have d₁=1 and d_m=1, which makes S₁>1, contradicting that d₁=1.
• finally if k=1, we have d₁=S₁=m. Now look at m. We know it is at least 3. What if it were larger? Then we would have at least four digits 1, and the digit d₁ which is at least 4, bringing the digit sum to at least 8. But each digit 1 refers to a single instance of some other digit. Besides a single 0 and a single m, we need at least two more single digits, the smallest being 2 and 3 which would bring our digit sum to at least 13. So m can only be 3. So d₁=s₁=3. The three 1s and the 3 representing them make a digit sum of 6, but we need more digits. Each 1 represents a single instance of some other digit. Look at d₃. It can't be 0 because S₃ is not 0. It can't be 2 because another digit 3 brings the digit sum to 9, and the digit 2 representing the two digits 3 brings it to 11. It can't be greater than 2 because another two digits 3 brings the digit sum from 6 to 12. Thus we have d₃=1. We need two more 1s. Let d_p=1 and d_q=1, where neither p or q can be 1 or 3. This raises the digit sum by p+q, so either p or q must be 0. Otherwise they would be at least 2 and 4, raising the digit sum from 6 to at least 12. So d₀=1. To recap this mess, we have d₀=1, d₁=3, d₃=1. Current digit sum 6 since we have another 1 to place. d_p=1 for some p other than 0,1, or 3. This represents a single instance of the digit p, which raises the digit sum by p, and also that digit p represents p instances of some other digit, raising the digit sum through the ceiling once again.

AND FINALLY IT IS DONE... this was A LOT easier to do in my head than to put down in text, and looking at all this text I wonder if an extensive breakdown of every number from 1 to 999999999 wouldn't have been just as fast. At least I can laugh evilly knowing that anyone who wants to proof-read my solution is in for a major headache, MUAHAHAHAHA *brain meltdown*

Damn, Rainman.

Well done.