The ruler sequence is undoubtly my favourite integer sequence. It starts like this:
The Nth term of the sequence (henceforth called R(N)) is determined by the position of the rightmost digit “1” in the binary representation of N, as shown in the following image:
Plotting this sequence gives us a fractal-ish picture. High peaks correspond to either the powers of two or small multiples of the powers of two.
Instead of focusing on boring properties of this sequence, I will show you…
A triple of exotic ways to generate it
If you are familiar with fractal-generating software, try exploring this L-system:
Rule X -> X-FY++YF-FX
Rule Y -> FY
Rather than outputting the numerical values, the L-system makes a plot similar to the one above. Irrespective of your familiarity with fractals, have a look at this Life pattern:
x = 169, y = 116, rule = B3/S23
It really computes the terms of the sequence, not just makes a graph. All values are given in unary, but it doesn’t cause much inconvenience because the numbers are quite small. Here is a screenshot of this pattern after 4096 generations (the output is on the left):
And finally, we can take a leap of faith and switch to a more complex cellular automaton:
x = 71, y = 82, rule = 34568/2/10
Again, I decided to upload a screenshot:
Actually, I have not tried proving that aforementioned CA patterns really produce the ruler sequence forever. Your proof is welcome in the comments section. Anyway, I will now move to applications of the ruler sequence.
Solving the Tower of Hanoi puzzle
Suppose you have three identical poles and N holed disks of different sizes. Put them on pole 1 in descending order – the largest at the bottom, the smallest at the top. The objective of this puzzle is to move all disks to pole 3. You can move one disk at a time and are not allowed to put larger disks on smaller disks. The puzzle cannot be solved in less than 2^N – 1 moves, and, surprisingly, the optimal sequence of moves is encoded within the ruler sequence. Here is a complete guide to solving the puzzle:
- Number the disks in ascending order.
- At move X, take the disk numbered R(X). If it is covered by other disks, then you have made a mistake somewhere. Where should you put that disk? Well, if it’s not the smallest disk, you have got only one option. If it is the smallest disk (which happens at every second move!), things are a bit trickier and depend on the parity of N. For odd N, move it according to the scheme (1->3->2->1). For even N, use the scheme (1->2->3->1).
- Enjoy yourself.
I could now prove by induction that the method always works and is always optimal, but I am far too lazy, so I’ll leave this as an exercise to the reader.
Wandering around a hypercube
Problem. Given number N, find the shortest path along the edges of an N-dimensional unit hypercube that visits each vertex at least once. At the first glance, this problem has nothing to do with the Tower of Hanoi puzzle, but they are actually subtly connected. Firstly, N-dimensional hypercube has 2^N vertices, so path cannot be shorter than 2^N – 1, which is equal to the number of moves in an optimal Hanoi game with N disks. Secondly, the lower limit of 2^N – 1 can be realised using the ruler sequence! At step number X, go in such a way that your coordinate number R(X) changes. I haven’t been able to make a comprehensible image for N>3, and you are encouraged to try doing it yourself.
A perfect leap year system
One of the least convenient things in our Solar System is the fact that our year contains a fractional number of days. As a result, we have to introduce leap years. The first leap year system used worldwide (well, almost worldwide) was the Julian calendar. This calendar shifts by one day per approximately 128 years. As centuries passed by, the error grew and eventually became inconvenient. That’s why a new system, namely the Gregorian calendar, was introduced. It is much better, and it is possible that the humanity will be wiped out by some catastrophe long before the error reaches one day. Adam P. Goucher has recently designed a system which is even better, shifting by one day every 500000 years. But it’s still not perfect, so I decided to make my own calendar.
I don’t see any reason why the number of days in a year should be rational, so using periodic sequences of leap and ordinary years is not a good idea. But… haven’t we just been talking about an amazing aperiodic sequence? Why not use it? Let’s go. First of all, go to an article about leap years and find a more or less precise length of a year:
1 year = 365.2421897 days
We don’t really need the integer part of that number, so let’s throw it away:
Convert to binary:
Take the ruler sequence and replace all 1’s with the first digit after the binary point (which is 0), replace all 2’s with the second digit after the binary point (which is also 0) and so on. We get:
00010001000100010001000100010001 00010001000100010001000100010001 00010001000100010001000100010001 00010001000100010001000100010000 0001…
Now, let 0 be an ordinary year and 1 be a leap year. That’s all! You see that for more than a century, my calendar agrees with the Julian one. But the 128th year is ordinary, which adjusts the calendar a bit. Actually, almost all years divisible by 128 will not be leap, similarly to the Goucher’s system. You will have to wait for many millenia to see the difference between Goucher’s almost perfect calendar and my perfect one. It confirms that Adam is only a bit less smart than the ruler sequence, which is a model of intelligence ;).
Anyway, I think this joke is a perfect ending for my article. More stuff coming soon!
P. S. I created the leap year system entirely by myself, but I believe somebody must have found it before. Could you confirm? All other things on this page are definitely not my findings.