The Ruler Sequence and Calendars

The ruler sequence is undoubtly my favourite integer sequence. It starts like this:

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6…

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:


Axiom FX
Rule X -> X-FY++YF-FX
Rule Y -> FY
Angle Pi/2

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
25bo$23b2ob2o2$23b2o$23bo$8b2o15bo$8bo16bo3$27bo$24b3o3$2o22b3o$o23b3o
$22b2ob2o$22bo$22b3o6$31b3o$31b3o$32bo$30b2o23bo$30bo23bobo2b2o7b2o$
31bo21bo3b4o6b3o$56bo7bobob2o$51b2obo10b2o$52bobo$43b2o8bo$43bo3$63bob
o$63bo2bo2bo7bobo$63bob2obobo5b2ob2o$69bo6b2obo$39bo21b3o11bo$38b2o21b
2o13bo$37bob2o21b2o12bo$36b3o2bo$38bobobo87b4o$39bobobo85b6o$40bo2b3o
83b4ob2o$41b2obo88b2o$42b2o$42bo3bo97b2o$45bobo95b4o$46b2o95b2ob2o$42b
2o88bo3bo2bo5b2o$41bobo87b2o3bo3bo$41bo5b2o24b2o56b2o2bo4b2o$40b2o5b2o
24bo62bo3bo$136bo2bo5b2o$143b2ob2o$143b4o$144b2o$67b2o60b6o$67bo52b4o
4bo5bo$120bo3bo9bo$120bo12bo$121bo2$151b4o$51b2o3bo3b2o31b2o3bo3b2o46b
6o$51bo2b5o2bo31bo2b5o2bo46b4ob2o$52b2o5b2o33b2o5b2o51b2o$54b5o37b5o
37bo$50b3obobobob3o29b3obobobob3o32b2o26b4o$49bo2b3o3b3o2bo27bo2b3o3b
3o2bo31bobo24bo3bo$49b2o11b2o27b2o11b2o25bo22bo4b2o7bo$51b4o3b4o31b4o
3b4o28bo21bo3b4o2bo2bo$51bo2bo3bo2bo19b2o10bo2bo3bo2bo24bo3bo24bo3b2o$
81bo47b4o20b2o3b4o2bo2bo$52bob2ob2obo33bob2ob2obo49bobo4b2o7bo$50bobo
7bobo29bobo7bobo59bo3bo$49bo3bo5bo3bo27bo3bo5bo3bo59b4o$52bo7bo33bo7bo
40b2o$49bo13bo27bo13bo20b2o13b2ob2o9bo$49bob2ob2ob2ob2obo27bob2ob2ob2o
b2obo21b2o8bo3b4o11bo$50b2o4bo4b2o29b2o4bo4b2o21bo11bo3b2o6bo5bo$53bo
5bo35bo5bo34bo2bo11b6o$40b2ob2o65b2ob2o23bo3b2o$41bobobo11bo19b2o30bob
obo23bo3b4o$41bo2b4o2b3o24bo24b3o2b4o2bo27b2ob2o$39b2ob2o3bo2b3o3b3o
37b3o3b3o2bo3b2ob2o27b2o$40bobo4bo2b2o51b2o2bo4bobo$40bobo3bo2bo55bo2b
o3bobo20bo$37b2obo5bob3obo49bob3obo5bob2o18bo$38bobobo2bo6bo49bo6bo2bo
bobo13bo5bo$38bobobobo4b2o2bo13b2o17b2o13bo2b2o4bobobobo14b6o$37b2obo
2bo6bo3bo12bo19bo12bo3bo6bo2bob2o$38bob2obobo7bo11bobo19bobo6bo4bo7bob
ob2obo6b4o$38bo4bob3o17b2o21b2o5b2o10b3obo4bo5bo3bo$39b5o4bo46bobo8bo
4b5o10bo$45b2obo3bobo45bobo3bob2o15bo$39b2o2b2obob2obo2bo45bo2bob2obob
2o2b2o$39bo2bo3bo2bobo8bo33bo8bobo2bo3bo2bo$40b2o4b2o6bo4b3o32bo5bo6b
2o4b2o$41bo5bo3bobo5b3o32bo6bobo3bo5bo$40bo2bobo2bob2o51b2obo2bobo2bo$
40b2obo2bobobo9b3o29b3o9bobobo2bob2o$41bob2obobobo4b2ob7ob2o19b2ob7ob
2o4bobobob2obo$41bobo2bo2bo5bo3bobobo3bo19bo3bobobo3bo5bo2bo2bobo$42bo
2b2o9b4o3b4o21b4o3b4o9b2o2bo$58bo5bo25bo5bo$51b2o5bo5bo5b2o11b2o5bo5bo
5b2o$51bo2b2ob2o5b2ob2o2bo11bo2b2ob2o5b2ob2o2bo$52bobob4obob4obobo13bo
bob4obob4obobo$51b2o2bo4b3o4bo2b2o11b2o2bo4b3o4bo2b2o$53bobo11bobo15bo
bo11bobo$53bo2bo9bo2bo15bo2bo9bo2bo$54b2o11b2o17b2o11b2o!

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
29.IHGFEDCBA$29.IHGFEDCBA$28.2A$28.2BA$28.2CB$28.2DCA$28.2EDBA$28.2FE
CBA$28.2GFDCB$28.2HGEDCA$28.2IHFEDB$IHGFEDCBA21.IGFECA$2.IHGFEDCBA20.
HGFDB$3.IHGFEDCBA19.IHGEC$4.IHGFEDCBA19.IHFD$6.IHGFEDCBA18.IGE$7.IHGF
EDCBA18.HF$7.IHGFEDCBA18.IG$5.AB.2A25.H8.A2.A$6.A.2AH24.I.I6.4BA$5.B
4AFGFEDCBA26.4CB$4.A3.B2AGFEDCBA2.I.IHG19.4DCA$5.B2A2B.H10.I.IH18.4ED
BA$4.A.A2B2AB11.I.I18.4FECBA$4.EBEABIAI32.4GFDCB$3.DFDF3AFH32.4HGEDCA
$3.CECEAB.C11.H.H.I17.4IHFEDB$4.D.D3AE11.IHIH22.IGFECA$6.B.2A.D9.GFGF
D21.H.HGFDB$5.G.G3A10.DAD2AB11.A2.A5.IHIHGEC$4.FEFEABIAI8.B2A2B.A9.5A
6.I.IHFD$5.G.G3A.H10.AB2A11.5A6.I.IGE$5.IBI2A.I9.CACBA11.5A8.H.HF$6.
4AE11.4AI11.AB2AD7.IGIG$5.FBFA.G11.A.A.A10.EBEAFEC7.H.2HIH3.A2.A$5.HA
H.A.FA8.B.A.A3.D7.FGFGA.D8.G.GFDGFE2B2A$.HGCB.I5A.BDEDBFGFDCE3AFEFEIH
FEH.HGIH2A.I.ICBEDEDBECEBEGFDC2A$2.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A$69A$2A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A$2.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.IHIFGDEBC4A$2.A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.IHIFGDEBC4A$2A.A.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A$69A$2.A.A.A.A.A.A.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A$.HGCB.I5A.BDEDBFGFDCE3AF
EFEIHFEH.HGIH2A.I.ICBEDEDBECEBEGFDC2A$5.HAH.A.FA8.B.A.A3.D7.FGFGA.D8.
G.GFDGFE2B2A$5.FBFA.G11.A.A.A10.EBEAFEC7.H.2HIH3.A2.A$6.4AE11.4AI11.A
B2AD7.IGIG$5.IBI2A.I9.CACBA11.5A8.H.HF$5.G.G3A.H10.AB2A11.5A6.I.IGE$
4.FEFEABIAI8.B2A2B.A9.5A6.I.IHFD$5.G.G3A10.DAD2AB11.A2.A5.IHIHGEC$6.B
.2A.D9.GFGFD21.H.HGFDB$4.D.D3AE11.IHIH22.IGFECA$3.CECEAB.C11.H.H.I17.
4IHFEDB$3.DFDF3AFH32.4HGEDCA$4.EBEABIAI32.4GFDCB$4.A.A2B2AB11.I.I18.
4FECBA$5.B2A2B.H10.I.IH18.4EDBA$4.A3.B2AGFEDCBA2.I.IHG19.4DCA$5.B4AFG
FEDCBA26.4CB$6.A.2AH24.I.I6.4BA$8.B28.H6.A2.A$9.IHGFEDCBA18.IG$9.IHGF
EDCBA18.HF$8.IHGFEDCBA18.IGE$6.IHGFEDCBA19.IHFD$5.IHGFEDCBA19.IHGEC$
4.IHGFEDCBA20.HGFDB$2.IHGFEDCBA21.IGFECA$30.2IHFEDB$30.2HGEDCA$30.2GF
DCB$30.2FECBA$30.2EDBA$30.2DCA$30.2CB$30.2BA$30.2A$31.IHGFEDCBA$31.IH
GFEDCBA!

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:

  1. Number the disks in ascending order.
  2. 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).
  3. 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:

0.2421897

Convert to binary:

0.0011111000000000001001…

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.

Advertisements
This entry was posted in Cellular automata, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s