This weekend my 9 year old son was given the following homework:
Choose a two-digit number (eg. 23), square each digit and add them together. Keep repeating this until you reach 1 or the cycle carries on in a continuous loop. If you reach 1 then the number you started with is a “happy number”.
Can you find all the happy numbers between 1 and 100?
For example, 31 is happy because
31 => 32 + 12 => 10 => 12 + 02 => 1
But 4 is not happy because
4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4
and we have a cycle.
I thought this might make an interesting code kata, so while he beavered away with pencil and paper I set to writing a little program to do the job. Why not give it a try yourself?
- What tests, if any, did you write? How many times did your stack overflow? What data structure(s) do you need?
- Did you use recursion? Or loops? Or filters? Or something else?
- Did you manage to eliminate all of the duplication? Can you eliminate all of the conditionals? Is any of this altered by your choice of programming language?
- How long does it take to run? At what range size (eg. 1-100, 1-1000, 1-10000) does it take more than, say, 5 seconds to run? Does it run in linear time? Polynomial time? What mathematical tricks can you find to speed it up?
- What will you do differently next time?
First time through, I wrote no tests. My stack overflowed three times. I used a dictionary to hold the results, with a simple array for cycle detection and a recursive algorithm. I made no attempt to eliminate either duplication or conditionals, and I used none of the arithmetic tricks that my son found while doing the exercise by hand.
Next time, however, will be different…
Supplementary (for the mathematicians among you):
Are there any numbers for which the series neither terminates at 1 nor eventually repeats forever?