The Exceptional Powers of Two
Lessons 03 and 04 needed "half" on the dial, which only exists when the number of marks is odd. Now try dials with 2, 4, 8, 16, … marks. Something surprising happens: the first block of rotations misses exactly one mark, always the one halfway round, and the second block fills it in straight away. You will find out why, using the simplest clock from Lesson 01.
Where this lesson is headed
In words: the first block hits every mark once, except that 0 is hit twice and the halfway mark is skipped. The second block (k = m to 2m − 1) is the first block turned half a dial, so the skipped mark appears at once, at k = m and m + 1. Same setup as Lessons 03 and 04: a clock starting at circumference m, growing 1 cm per rotation, on an m-mark dial, so the reading is T(k) mod m.
m: number of dial marks, a power of two (2, 4, 8, …)
k: rotations completed
T(k) = k(k − 1)/2: the growth part
U(j) = j(j + 1)/2 = 0, 1, 3, 6, 10, …: the totals of the simplest clock (N = 1, g = 1) from Lesson 01
1st block: k = 0 to m − 1 · 2nd block: k = m to 2m − 1
01. Find the mark that is skipped
Start with the 4-mark dial. Turn through the 1st block (k = 0 to 3) and see which mark is never reached. Then keep going into the 2nd block. Lesson 02 predicts something here: on an even dial with odd growth, M rotations move the reading by half the dial. (Shortcut: Space turns one rotation, ← undoes one.)
The m-mark dial
Predict before you finish the 1st block
Settings
Dial size m (powers of two)
For comparison, other dials
| k | T(k) | Reading | Block | New or repeat |
|---|
Guided experiments
Do these in order. "Set this up" chooses the dial and turns the clock for you.
02. Why exactly one mark is skipped
The idea: compare T with the simplest clock of Lesson 01. Its totals U(j) = j(j + 1)/2 are just T shifted by one rotation. On a power-of-two dial, U hits every mark exactly once, and shifting by one swaps out one mark for a second 0. Each step has the general idea on the left and your numbers on the right.
Meet U, the simplest clock
In Lesson 01, the simplest clock (N = 1, g = 1) had totals 0, 1, 3, 6, 10, 15, …, which is
Compare with the growth part T(k) = k(k − 1)/2. Replacing k by j + 1 turns one into the other:
So the list T(0), T(1), T(2), … is 0 followed by the list U(0), U(1), U(2), ….
On a power-of-two dial, U hits every mark once
Look at U(0) to U(m − 1) on the m-mark dial. The claim is that no two of them share a mark. Since there are m of them and m marks, that means every mark is hit exactly once.
Steps 3 and 4 prove the claim.
Turn a shared mark into a product
Suppose U(a) and U(b) share a mark, with a and b between 0 and m − 1. Multiply by 2 to clear the fraction. We cannot undo multiplying by 2 on an even dial (Lesson 02, step 4), so instead we double the modulus as well, which keeps the statement exact:
(Expand: a² + a − b² − b = (a − b)(a + b) + (a − b).)
Parity and size rule it out
The two factors differ by (a + b + 1) − (a − b) = 2b + 1, an odd number, so one factor is even and the other is odd. Since 2m is a power of two, all its factors of 2 must come from the even factor, so the even factor must be a multiple of 2m. But:
If a − b is even: it lies between −(m − 1) and m − 1, and the only multiple of 2m there is 0, so a = b.
If a + b + 1 is even: it lies between 1 and 2m − 1, which contains no multiple of 2m at all.
So two different values of U never share a mark.
This is where "power of two" is used. On a 6-mark dial, 2m = 12 = 4 × 3, and the odd factor could supply the 3 (Stage 03).
Shift by one rotation
The 1st block of T is T(0), T(1), …, T(m − 1) = 0, U(0), U(1), …, U(m − 2).
So the 1st block of T reaches every mark except the one U(m − 1) was on, and 0 is hit twice (by k = 0 and k = 1).
| j | U(j) reads | k = j + 1 | T(k) reads |
|---|
Which mark was dropped?
m · (m/2) is whole trips around the dial, and −m/2 + m = m/2. So
The skipped mark is always the halfway mark.
Quick check · count
On a 32-mark dial, how many different marks does the 1st block reach?
Quick check · the dropped value
On a 16-mark dial, what does U(15) read? Use step 6 instead of listing.
03. Prove it, and watch the gap close
We now put the argument together, add the 2nd block using Lesson 02's half-dial jump, and see exactly which assumption made it all work.
Theorem · dials with m = 2, 4, 8, 16, … marks
Proof workshop
Complete proof
U hits every mark once. Let 0 ≤ a, b ≤ m − 1 and suppose U(a) ≡ U(b) (mod m). Then 2m divides (a − b)(a + b + 1). The factors differ by 2b + 1, so exactly one is even. Since 2m is a power of two, it divides the even factor. If a − b is even, |a − b| < m forces a = b. If a + b + 1 is even, 1 ≤ a + b + 1 ≤ 2m − 1 rules out a multiple of 2m. So U(0), …, U(m − 1) are all different, and being m values on m marks, they hit each mark once.
The 1st block. For k = 1 to m − 1, T(k) = U(k − 1), giving U(0), …, U(m − 2), all different. T(0) = 0 repeats T(1) = U(0) = 0. The mark left out is that of U(m − 1) = m(m − 1)/2 ≡ m/2 (mod m). So m − 1 marks are reached, and only m/2 is missing.
The 2nd block. T(k + m) − T(k) = mk + m(m − 1)/2 ≡ m/2 (mod m), since m is even. So T(k + m) reads m/2 exactly when T(k) reads 0, which in the 1st block happens only for k = 0, 1. Hence m/2 appears in the 2nd block at exactly k = m and m + 1. ∎
The 2nd block is the 1st block turned half a dial
Pick a rotation k in the 1st block. Rotation k + m reads exactly m/2 further round.
Try k = 0 and k = 1: they read 0, so k + m reads m/2, the skipped mark.
Why not every even dial?
Step 4 needed 2m to be a pure power of two, so that the odd factor could not help. On a 6-mark dial that fails.
⇔ (a − b)(a + b + 1) ≡ 0 (mod 2m)
Think before revealing
Why does the argument break for m = 6?
Reveal explanation
2m = 12 = 4 × 3. The product can be a multiple of 12 with the 4 coming from the even factor and the 3 from the odd factor, so the even factor itself need not be a multiple of 12. For example U(0) = 0 and U(3) = 6 both read 0 on a 6-mark dial: (0 − 3)(0 + 3 + 1) = −3 × 4 = −12. The even factor 4 is not a multiple of 12; the odd factor supplied the 3.
Computer check
For every power of two from 2 to 1,024: checks the 1st block (m/2 missing, 0 twice, everything else once), the half-dial jump for every k, that the two blocks together hit every mark exactly twice, and that m/2 appears only at k = m and m + 1. Many matches are strong evidence, but only the proof covers every power of two.
Exit challenge · explain it in your own words
Explain, without listing readings, why a 2r-mark dial skips exactly one mark in the 1st block. Use the simplest clock U, the shift by one rotation, the dropped value, and why 0 is the only repeat.
What a complete answer includes
Show U(a) ≡ U(b) gives 2m | (a − b)(a + b + 1); use parity and size to show U hits every mark once; note T(k) = U(k − 1) for k ≥ 1 with T(0) = 0 extra; compute U(m − 1) ≡ m/2. Extension: use the half-dial jump to show m/2 appears at exactly k = m and m + 1.