Waves on the Shore

It started with mathematical doodling while waiting on the telephone...

I was thinking about square numbers (that is, integers that are squares, such as 4, 25, 169) and noted that there was a pattern to the last decimal digit of the series of squares. The list starts with 1, 4 and 9, then the square of 4 is 16, which ends in 6. From there is goes on 5, 6, 9. It suddenly hit me that the square of the next number (8) ends in 4. The emerging pattern was like a wave: 1,4,9,6,5,6,9,4,1,0 and then the whole is repeated.

Would the pattern work with other bases? I had just the week before written a few functions in Just BASIC to translate between bases, so I crafted a tiny program to convert squares to hexadecimal. Would the result be a wave? Perhaps even a larger wave, reflecting the larger base (16 instead of ten). If you have the programming skills, why not take a few minutes to find out for yourself? I’ll be here when you come back...

Well, there is a wave pattern again, but this time the wave is 1,4,9,0,9,4,1,0 – down from ten numbers to seven in length. The functions I created were for conversion from decimal to hexadecimal (base 16), octal (base 8) and binary (base 2): these are all useful to programmers for various reasons.

In case you are not familiar with number bases, you should be told that hexadecimal is just a more convenient way of representing binary, the base of digital computers. It gets confusing for a mere human to deal with long strings of ones and zeros, so we group them in bundles of four. These bundles are each assigned a tag: sixteen tags are needed, for which we use the digits 0 to 9, and then A,B,C,D,E and F.

Because the hexadecimal list of last numbers “waves”, we can expect the corresponding binary list to “wave” as well. It does, but it is rather uninteresting: 1,0,1,0,1,0 and so on. What about the last TWO binary digits? That’s 01,00,01,00,01,00... wait! That’s a little more interesting: it seems the penultimate binary digit of a square is zero – all the time. I wondered why.

I had in fact stumbled on one of those little gems that promote doodling into full time distraction: I was suddenly much more interested in thinking through this puzzle than in waiting “in a queue” on the telephone. It is easy to see the truth of the statement, but the question is WHY is the next-to-last binary digit of every square a zero? Is it just divine will? Does the wave break down or peter out if I continue at length?

Let’s go back to the last binary digit for a moment: the sequence goes 1,0 and repeats. This is so not just for squares, but for the ordinary numbers themselves: 1 ends in 1, 2 ends in 0, and so on. The last binary digit really tells you nothing more than whether the number it represents is odd or even. It’s also pretty clear that squares of numbers go in the same pattern: odd, even, then odd again. Instantly you can be sure that 37 squared ends in binary 1, because 37 is odd, and so is its square: the square of every odd number is odd, and the square of every even number is even.

Why should this be so? The simplest way I know to explain it is like this: every even number is a multiple of two. If N is an even number, it is equal to 2P (where P is some other whole number). If N is an odd number, it is equal to 2P + 1. Let’s look at the squares of simple numbers. If N is even, N squared is equal to 2P x 2P, which is 4 P squared. If N is odd, N squared is equal to (2P + 1) x (2P + 1) which is (4 P-squared + 4P + 1). In the first case 4 and P are both even, so 4P is even. In the second case we have 4 x (P-squared + 1) + 1. Four times anything is even, so adding the one makes it odd. This demonstrates not only that the square of an even number is even, while the square of an odd number is odd: it further demonstrates that the square of an even number is a multiple of four, while the square of an odd number is one more than a multiple of four. That is what I saw in the last two bits (binary digits) of the squares: a number ending in 00 is a multiple of four, and a number ending in 01 is one more than a multiple of four. While simply doodling I had plucked some interesting fruit.

Returning to the theme, I invested some time in a few more thoughts: Surely there are deeper patterns: what about other number bases – not just powers of two? What about other digits than just the last one or two? In programming terms, this would need a new function. I had dealt with bases 2, 8 and 16 because they are useful to me – a programmer. But for my investigations I could see I needed a universal base converter: at least, between decimal and any particular base.

At this point it may be helpful for you to know the algorithm for converting bases: let’s start with binary. Say you wanted to convert decimal 227 to binary. These are the steps:

1. Write down the number
2. Half it, ignoring any fraction, and write that beneath
3. repeat until you get to zero: you WILL get there, and sooner that you think
4. put a hyphen to the right of each odd number in your list, and a small circle to the right of each even number

If you are following this, you should now have on your page:

5. Now turn your page ninety degrees to the right, and under the sideways list of numbers you will see the binary equivalent of the number at the top of the list. In this case it’s 11100011.

Congratulations! You have done your first conversion of a number from decimal to binary. If you want to convert to some other base you do the same process, but with slight changes: to get hexadecimal, instead of halving your number you divide by sixteen. The remainder will be in the range zero to fifteen, and it is this remainder that you put to the right of the number in the descending list. (use A for ten, B for eleven, and so on up to F). As an illustration, let’s convert 227 to hexadecimal (almost always called “hex” amongst programmers):

So 227 in decimal is E3 in hexadecimal. We can check that out with binary, grouping the bits into bundles of four starting at the right: We end up with two bundles, 1110 and 0011, and sure enough, 1110 is E in shorthand hex, and 0011 is 3.

By the way, it’s confusing to say aloud, ay, bee, see, dee, ee and eff: can you imagine frustrated programmers calling out in the middle of the night, “did he say see-three or ee-three?”. Myself, I get around this by coining new words for the symbols: A is Ann, B is Bet, C is Chris, D Dot, E Ernest, and F Frost. Hexadecimal digits are almost always spoken of in pairs (mainly because a “byte” – the molecule of modern computer memory – holds eight bits: a hexadecimal pair nicely represents the value in a byte of memory). I take advantage of the English formation of number-related words, so A4 is “Annty-Four” (just as 64 is “sixty-four”), and 1C is “Christeen”.

I invested a little time adjusting my program so that it could convert a number to any base from 2 up to 36 (after F, I used G for seventeen, and so on). The next course was to throw a series of squares, growing ever larger, and looking at the last digits for a pattern. Was there a pattern in each number base, or only in some? Was it always a wave? What about its cycle length, relative to the base? Intrigued with the results, I tried the same processes with cubes. See what you can find.

For bases 2 to 36, the rightmost digit of squares do indeed produce nice, symmetrical waves, with certain notable exceptions. The length of the wave for each base is the same as the number of the base: for base seven, for example, the waveform is 01422410. Of course we do not count the zero twice, as it marks the first digit of the next cycle. Again there are a few exceptions, seemingly. You can see in the diagram some examples of the waves that are produced. Note that the waveforms are symmetrical in the sense that they are palindromic: they go the same whether forward or in reverse.

The waveform of the last digit of squares rendered in different number bases shows unexpected symmetry

I said there are a few exceptions: no telling how many there are in higher bases, but between 2 and 36 the only exceptions are bases 4, 8, 9, 16 and 18.

Base 4 has a cycle length of two (010), but if you view it as (01010) then it seems four long, as normal. Similarly base 8’s waveform can be seen as four long (01410) or eight long (0141014100, and base 16’s identical waveform can be seen as four long or sixteen long (01410141014101410). Base 9 gives us a different problem: its repeated waveform (0770410140) is the expected length, but asymmetrical. That is, its symmetry only appears when you picture it. If you start the wave at a different place, it suddenly becomes (0140770410), symmetrical like the others, but with internal minimum points (the embedded zeros). Similarly base 18’s wave is not (07G9410149G70DA9A0) but the more picturesque (0149G70DA9A07G9410).

If you investigate the waveforms generated by a list of CUBES rendered in different number bases, the palindromic form goes out the window (except for base 2) but you still get some very interesting forms. For example the waveform in base 8 is (010305070). Again, in some bases the waveform is shorter than you would expect, but always a factor in length: base 9’s wave is three long, base 18’s is six long, base 27’s is nine long, base 36’s form is twelve long. It would seem that base 9xN has a cubic wave of period 3xN, but that is just a conjecture, based on available evidence rather than proof.

I do not have the hubris to suggest that I am in the company of Da Vinci, but I note that he also profited from doodles, working on them until they yielded interesting (and sometimes earth-shaking) insights. Can you likewise turn your idle moments to things that will at the very least exercise your grey cells?

December 2005