BMAD 62 Report post Posted July 28, 2013 (edited) 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 Share this post Link to post Share on other sites

0 Rainman 14 Report post Posted July 28, 2013 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. Share this post Link to post Share on other sites

0 Rainman 14 Report post Posted July 29, 2013 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_{0}d_{1}...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}=0, then the number contains at least one 0, meaning S_{0}>0. But 0=d_{0}=S_{0}>0 is a contradiction. Observation 2: Some digit must be 0. Otherwise S_{0}=0, which means d_{0}=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_{0}d_{1}...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_{0}+d_{1}...+d_{N-1} = S_{0}+S_{1}...+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_{0} 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_{1} or d_{2} 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_{1}=d_{1}=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: The case where d_{0}=1. This makes d_{1}=S_{1}>0. Also, d_{1} can't be 1 since that makes S_{1}>1 which contradicts d_{1}=1. And d_{1} can't be >2 by Lemma C. So d_{1}=2. We can't have d_{2}=0, and we must have d_{2}<2 by Lemma E. So d_{2}=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. The case where d_{0}=2. This makes d_{2}>0. If d_{2}=1, we can't find a value for d_{1}. 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}=2. Now d_{1} could be either 0 or 1, bringing the solutions 2020 and 21200. The case where d_{0}>2. Because d_{0}=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_{1} can't be 0 or 1, so it must be 2. Now d_{2} can't be 0 or 2, so it must be 1. This makes four non-zero digits (d_{0}=m, d_{1}=2, d_{2}=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_{3}=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_{3}=S_{3}=3. But since S_{3}=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_{2}=S_{2}=m. So we have at least three digits 2, and the digit d_{2} 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_{2}=m. It can't be >1 because we can't afford another digit m. So d_{m}=1, which makes S_{1}>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}=1 and d_{m}=1, which makes S_{1}>1, contradicting that d_{1}=1. finally if k=1, we have d_{1}=S_{1}=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_{1} 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_{1}=s_{1}=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_{3}. It can't be 0 because S_{3} 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_{3}=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_{0}=1. To recap this mess, we have d_{0}=1, d_{1}=3, d_{3}=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* Share this post Link to post Share on other sites

0 gavinksong 11 Report post Posted July 29, 2013 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_{0}d_{1}...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}=0, then the number contains at least one 0, meaning S_{0}>0. But 0=d_{0}=S_{0}>0 is a contradiction. Observation 2: Some digit must be 0. Otherwise S_{0}=0, which means d_{0}=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_{0}d_{1}...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_{0}+d_{1}...+d_{N-1} = S_{0}+S_{1}...+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_{0} 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_{1} or d_{2} 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_{1}=d_{1}=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: The case where d_{0}=1. This makes d_{1}=S_{1}>0. Also, d_{1} can't be 1 since that makes S_{1}>1 which contradicts d_{1}=1. And d_{1} can't be >2 by Lemma C. So d_{1}=2. We can't have d_{2}=0, and we must have d_{2}<2 by Lemma E. So d_{2}=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. The case where d_{0}=2. This makes d_{2}>0. If d_{2}=1, we can't find a value for d_{1}. 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}=2. Now d_{1} could be either 0 or 1, bringing the solutions 2020 and 21200. The case where d_{0}>2. Because d_{0}=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_{1} can't be 0 or 1, so it must be 2. Now d_{2} can't be 0 or 2, so it must be 1. This makes four non-zero digits (d_{0}=m, d_{1}=2, d_{2}=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_{3}=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_{3}=S_{3}=3. But since S_{3}=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_{2}=S_{2}=m. So we have at least three digits 2, and the digit d_{2} 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_{2}=m. It can't be >1 because we can't afford another digit m. So d_{m}=1, which makes S_{1}>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}=1 and d_{m}=1, which makes S_{1}>1, contradicting that d_{1}=1. finally if k=1, we have d_{1}=S_{1}=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_{1} 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_{1}=s_{1}=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_{3}. It can't be 0 because S_{3} 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_{3}=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_{0}=1. To recap this mess, we have d_{0}=1, d_{1}=3, d_{3}=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. Share this post Link to post Share on other sites

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 by BMAD## Share this post

## Link to post

## Share on other sites