Consider the following theorem:
There is no 2-digits number that is the sum of the squares of its digits.One crude measure of elegance is to minimize the number of numbers that you need to check directly are not the sum of the squares of their digits. With this in mind. With this in mind, here are several proof sketches.
- One could proof this by enumerating all possible 2-digit numbers. If you wrote a program for this then you could use it on similar problems. Even so, I suspect most of us would call this proof NOT ELEGANT. This requires 89 CHECKS.
- There is a proof that first easily eliminates 10, 20, 30, 40, 50, 60, 70, 80, 90 and then looks at every interval [11,19], [21,29], ..., [91,99]. More elegant than enumeration and certainly shorter. This required 8 CHECKS.
- There is a proof that looks at the equation 10a + b = a2 + b2. We look at it mod 2, mod 4, and mod 10. This gives what I thought was the most elegant proof; however, after writing it down carefully it was about the same length as the interval proof. This required 2 CHECKS.
There is no x ≥ 2 that is the sum of the squares of its digits.The cases of 2 ≤ x ≤ 9 and x ≥ 100 can be done with zero checks, so using the best proof of the last theorem, we can do this theorem with 2 checks.
Consider the following theorem.
The only 3-digits number that is the sum of the cubes of its digits is 153. (NOTE ADDED LATER: This is INCORRECT. A commenter pointed out that 370, 371, 407 also work. I will fix the proof and statement later and see if these are the only ones. Score a point for the `do it by a computer enumeration' argument!)I have a proof of this which is... not quite elegant but not brute force. I get it down to only 21 CHECKS. If you have a better proof in terms of NUMBER OF CHECKS that is not contrived to reduce NUMBER OF CHECKS I would be very interested to see it. Of course, I cannot define contrived rigorously or elegantly.