Happy numbers problem description.

HappyNumbers.md

Problem:

We'll say that for a positive whole number n, the squareSum of n is the sum of the squares of the digits of n. So if n is 1406, then squareSum(n) is 1^(2) + 4^(2) + 0^(2) + 6^(2) = 1 + 16 + 0 + 36 = 53.

We further say that the k^(th)-squareSum of n is squareSum(squareSum(...(squareSum(n)))), where squareSum is composed k-many times. For example, the 3rd-squareSum of 1406 is squareSum(squareSum(squareSum(1406))) = squareSum(squareSum(53)) (as we know from above) = squareSum(5^(2) + 3^(2)) = squareSum(25 + 9) = squareSum(34) = 3^(2) + 4^(2) = 9 + 16 = 25.

Definition: A number n is happy if for some positive integer m, the m^(th)-squareSum of n is equal to 1.

Aspects that made this problem interesting:

• Let the squareSum be the sum of the squares of a numbers digits. Then squareSum(number1) = squareSum(number2) if number1 is a permutation of the digits of number2.

• You should cache the results. If the k^(th)-squareSum of a number n is happy for any positive integer k, then you know n is happy as well. We should thus cache these happy numbers.

• Similarly, the number 2 has a "squareSum sequence" of 4, 16, 37, 49 + 9 = 58, 64 + 25 = 89, 64 + 81 = 145, 1 + 16 + 25 = 42, 16 + 4 = 20, 4 + 0 = 4, .... Therefore 2 cannot be happy. This also means that all numbers N which have a k^(th)-squareSum in this sequence (or in the sequence of any unhappy number) are also unhappy. We should cache these unhappy numbers.

• Each digit d is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Therefore, d * d <= 81. If we remove leading zeroes, then a number with N-many digits has a squareSum of at most 81 * N. We want to limit the size of our happy and unhappy number caches. What is a reasonable limit? What if we categorize each number from 1 to 1,000,000 as happy or unhappy? Then for any number N greater than 1,000,000, N will have at least 7 digits. Let's say that N has m-many digits. This means that 7 * 81 <= squareSum(N) <= m * 81. For m <= 10, the upper bound reduces to 810. Ooh! We could get away with caching all the results through 810 and still categorize all the numbers up to 1,000,000,000 in one step. Hence, we opt to save space.

• On the topic of finding happy numbers, note that any having any one happy number means that you have infinitely many. Since 1 is (very trivially) happy, we know that 10 = 1^(2) + 0^(2) = 1 is happy. So 1 * 10^(k) is happy for every positive integer k. In fact, any permutation of the digits of a happy number is also happy, while the same property holds for unhappy numbers. Although I did not implement any such method, one could easily take a given number, determine whether it is happy (or not), cast it to a String, and then to a charArray. Permute the charArray, and for each permutation, create a new String object and parse the number from the string. That number is also happy (or not).