This morning I got up at eight minutes past six. So what, you ask? Well, that means I got out of bed at 06:08 10/12/14*, which is a very nice arithmetic progression. That is, today’s date is a series of numbers with a constant difference (in this case, the constant difference is 2).
Question: Which dates (and times, if you wish) next year will form arithmetic progressions? And which, if any, will form a geometric progression (in which each term after the first is found by multiplying its predecessor by a fixed constant)?
*Unless you live in the US — in which case, pretend today is October 12th.
If you’ve tried the Happy numbers kata you may have noticed a couple of things about the algorithm. Firstly,
13 => 32 + 12 => 10 => 1
is the same as
31 => 12 + 32 => 10 => 1.
That is, happiness and unhappiness are preserved under all permutations of the digits. So if you have calculated the status of 134, you also know the status of 143, 314, 341, 413 and 431!
And secondly, zeroes have no effect on the outcome. So 103 is just as happy as 13; and similarly 1300, 1000300000 and 30010 are all happy.
In a sense, that means it is not meaningful to ask how many numbers can be examined in 5 seconds, say — because the answer is always infinite! So let’s redefine the kata:
Write a program to report the number of happy numbers in the range [1, n]. What is the largest n you can deal with in 5 seconds?
Some interesting questions now come to mind:
- Where does the time go? Is it faster to calculate the happiness of a number than it is to create all permutations of its digits?
- What is the best data structure for holding the results? Can a recursive or functional algorithm compete with a procedural approach?
- What is the best way to deal with numbers containing zeroes?
- Are the answers to these questions dependent on programming language?
- Is this really an algorithm on the integers, or is it an algorithm on lists of digits?
Finally, something quite bizarre. The observations above regarding zeroes and digit permutations mean that we can acquire the answer to the challenge while examining fewer integers. How many fewer?
My rough calculations suggest that we only need to examine 54 of the integers below 100 in order to have complete information about every number in the range 1-100. Thats 54%. But we only need to examine 229 of the first 1000, which is 22.9%. To cover 1-10000 we only need to examine 714 numbers, and for 1-100000 we only need to examine 2002 numbers — ie. 2% of them! It would appear that this algorithm gets significantly faster as we move to larger and larger data sets. How much difference does this make to what your implementation can achieve?
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?
My son was given this challenge for his school homework tonight:
Pick a number in the range 2-100. Next, pick a number that is a factor or a multiple of the first, again using only the numbers 2-100. Continue like this, building a chain of numbers in the range 2-100 in which each number is either a factor or a multiple of its predecessor in the chain. What is the longest non-repeating chain you can build?
I feel some gentle programming about to occur…
Whatever happened to hexahexaflexagons? During my teenage years in the Seventies they seemed to be omnipresent – probably due to Martin Gardner’s column in Scientific American.
This morning – for a reason that escapes me now – I remembered a story about a mathematician who caught his tie in a hexahexaflexagon. He tried to ‘flex’ it free, but the tie only disappeared further. As he continued flexing his tie, and eventually himself, became more and more deeply entwined. Eventually he disappeared completely, never to be seen again.
I don’t recall seeing one for maybe twentyfive years now. Whatever happened to hexahexaflexagons?
A brief history of hexahexaflexagons, together with folding instructions, can be found here and here.