Parity of d(n)
The other day Tom was talking about a problem they did in his math class. Here’s a slightly modified version.
Consider an infinite list of bits.
- The first bit represents the number 1;
- The second one represents the number 2.
- etc …
Initially all of the bits are set to 0. Now perform the following steps.
- Starting with the first bit, toggle every bit.
- Starting with the second bit, toggle every second bit.
- Starting with the third bit, toggle every third bit.
- Starting with the fourth bit, toggle every fourth bit.
- Repeat forever …
When you’re done, which bits are set?
Before I could figure it out, he said that the answer is all of the bits which represent the perfect squares. I found this very surprising.
Working out the first several steps and typing the numbers into my favorite website, I was quickly led to d(n) (the number of divisors of n). That page contains the following note:
If d(n) is odd, n is a perfect square. …. – Donald Sampson (Marsquo(AT)hotmail.com), Dec 10 2003
That certainly explained Tom’s result, but there weren’t any details about why it’s true. So I was left still puzzling over it.
I finally realized what was going on when I found this picture down in the links section of that page. That picture only does the first couple of values though. Lets look at two larger values to make it even clearer.
Here are the factors of 32 drawn as rectangular arrangements of squares. They range from a 1×32 rectangle to a 32×1 rectangle. There are a total of six rectangles and d(32) is 6.
Here’s the same picture for the factors of 36. There are 9 rectangles and d(36) is 9.
Notice that in the first picture, each rectangle has a matching one which is its transpose. That obviously means that there are an even number of rectangles. In the second picture, there’s that lonely 6×6 rectangle in the center. It doesn’t have a match because it is its own transpose! Every number which is a perfect square will create one rectangle which is its own transpose. That’s because it’s a square!
That’s why d(n) is odd if and only if n is a perfect squares! Pretty cool, isn’t it?
