Detailed mathematical approach

Problem Summary

For each integer \(n \ge 3\), consider binary states on a circle of length \(n\). One update step replaces every entry by the xor of its two neighbors, so the dynamics are linear over \(\mathbb F_2\). A positive integer \(t\) belongs to \(\mathcal P(n)\) if some state has least period \(t\) under this update.

The global target is

$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$

The key point is that the implementations never simulate all states. They turn the update rule into multiplication in a quotient ring, analyze each irreducible factor separately, and reconstruct the possible periods by least common multiples.

Mathematical Approach

The natural state space for a circle of size \(n\) is

$R_n=\mathbb F_2[x]/(x^n+1).$

A binary state \((a_0,\dots,a_{n-1})\) is encoded as

$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$

Multiplication by \(x\) shifts left, multiplication by \(x^{n-1}=x^{-1}\) shifts right, so the update operator is simply

$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$

Step 1: Split Off the Power of Two

Write

$n=2^k m,\qquad m\text{ odd}.$

In characteristic \(2\), the Frobenius identity gives

$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$

Because \(m\) is odd, the derivative of \(x^m+1\) is \(x^{m-1}\), so \(x^m+1\) is square-free. Hence

$x^m+1=\prod_{j=1}^{r} g_j(x)$

with pairwise distinct irreducible factors \(g_j\). Therefore

$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$

Step 2: Decompose the State Space

Since the factors \(g_j^{2^k}\) are pairwise coprime, the Chinese remainder theorem gives

$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$

This means the dynamics split into independent local components. If one local component has period \(u_j\), then the whole state has period

$\operatorname{lcm}(u_1,\dots,u_r).$

So the real job is to determine the possible local periods contributed by each irreducible factor.

Step 3: Reduce to a Finite Field Element

First reduce modulo \(g_j\), not modulo the higher power \(g_j^{2^k}\). In the field

$K_j=\mathbb F_2[x]/(g_j(x))$

we have \(x^m=1\), so \(x^{-1}=x^{m-1}\). The local multiplier becomes

$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$

There are three cases.

If \(\lambda_j=0\), the lifted operator will be nilpotent on that branch and can only contribute period \(1\).

If \(\lambda_j=1\), the semisimple part is trivial and only powers of \(2\) can appear after lifting.

If \(\lambda_j\neq 0,1\), then \(\lambda_j\in K_j^\times\) has a multiplicative order \(r_j\).

The implementations compute \(r_j\) by finding the smallest \(e_j\) such that

$\lambda_j^{2^{e_j}}=\lambda_j.$

This means \(\lambda_j\) lies in the subfield \(\mathbb F_{2^{e_j}}\), so

$r_j\mid 2^{e_j}-1.$

Starting from \(2^{e_j}-1\), they divide out prime factors whenever the corresponding power test still gives \(1\), which reduces the candidate to the true multiplicative order.

Step 4: Lift from \(g_j\) to \(g_j^{2^k}\)

Now return to the local ring \(\mathbb F_2[x]/(g_j^{2^k})\). If \(\lambda_j\neq 0\), the lifted multiplier can be written as

$\lambda_j(1+u),\qquad u^{2^k}=0,$

where \(u\) lives in the nilpotent part created by the repeated factor \(g_j^{2^k}\). In characteristic \(2\),

$ (1+u)^{2^s}=1+u^{2^s}. $

So the nilpotent correction contributes only powers of \(2\). As the state moves through the \(g_j\)-adic filtration, every exponent \(2^s\) with \(0\le s\le k\) can occur when the semisimple part is nontrivial, and every exponent \(2^s\) with \(1\le s\le k\) can occur when the semisimple part is \(1\).

Therefore the local period options are

$ \mathcal O_j=\{1\}\cup \begin{cases} \varnothing, & \lambda_j=0,\\ \{2^s:1\le s\le k\}, & \lambda_j=1,\\ \{r_j2^s:0\le s\le k\}, & \operatorname{ord}(\lambda_j)=r_j>1. \end{cases} $

The initial \(1\) accounts for choosing a local state whose periodic part is trivial.

Step 5: Reconstruct the Period Set for a Fixed \(n\)

Because the local factors are independent, the full period set for this circle size is exactly

$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$

This formula is the entire algorithm in one line: factor \(x^m+1\), compute one local option set per irreducible factor, then close under lcm.

Step 6: Worked Examples

For \(n=5\), we have \(k=0\) and

$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$

On the factor \(x+1\), we substitute \(x=1\), so \(\lambda=1+1=0\), contributing only \(1\).

On the quartic factor, let \(\alpha\) be a root. Since \(\alpha^5=1\),

$\lambda=\alpha+\alpha^4.$

Using \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\), we get

$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$

so \(\lambda\) has multiplicative order \(3\). Because \(k=0\), the second factor contributes \(\{1,3\}\), hence

$\mathcal P(5)=\{1,3\}.$

For \(n=6\), we have \(n=2\cdot 3\), so \(k=1\) and

$x^3+1=(x+1)(x^2+x+1).$

The linear factor again gives \(\lambda=0\). On the quadratic factor, \(x^2+x+1=0\) implies \(x^2=x+1\), so

$\lambda=x+x^2=1.$

Now the local periods are \(1\) and \(2\), giving

$\mathcal P(6)=\{1,2\}.$

Step 7: Union Over All Circle Sizes

After computing \(\mathcal P(n)\) for every \(3\le n\le N\), we insert every period into one global set

$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$

and the final answer is

$S(N)=\sum_{v\in\mathcal G(N)} v.$

This is why the program cares only about distinct periods, not how many states realize each one.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. They first precompute ordinary prime numbers large enough to factor the integers \(2^e-1\) that appear during order reduction.

They then implement polynomial arithmetic over \(\mathbb F_2\): degree, remainder, quotient, greatest common divisor, multiplication modulo a polynomial, and fast modular exponentiation. With that toolkit they apply Berlekamp factorization to \(x^m+1\) for each odd part \(m\).

For every irreducible factor, the implementation evaluates the local multiplier \(x+x^{m-1}\), detects the special cases \(0\) and \(1\), and otherwise computes the multiplicative order by repeated Frobenius squaring followed by divisor stripping inside \(2^e-1\).

Those local orders are converted into the option sets \(\mathcal O_j\). An iterative lcm-closure pass combines them into \(\mathcal P(n)\). The order data are cached by odd part \(m\), so the sizes \(m,2m,4m,\dots\) reuse the same field-factor analysis and differ only in the power-of-two lift range.

Finally the implementations take the union of all period sets for \(3\le n\le N\) and sum the distinct values. The checkpoints \(\mathcal P(5)=\{1,3\}\), \(\mathcal P(6)=\{1,2\}\), and \(S(30)=20381\) match the mathematical derivation above.

Complexity Analysis

Let \(U=\{m\le N:m\text{ odd}\}\). Each odd part is factored only once, so the dominant algebraic work is the sum over \(m\in U\) of factoring \(x^m+1\) over \(\mathbb F_2\). In this direct implementation, the Berlekamp linear algebra on degree-\(m\) polynomials is cubic in \(m\) up to bit-operation details, which is easily fast enough for \(N=100\).

Once the factors are known, order computation for one factor of degree \(d\) uses repeated squaring in the field together with tests on divisors of \(2^e-1\), where \(e\le d\). The period-set construction is combinatorial rather than algebraic: if the local option sets have sizes \(|\mathcal O_1|,\dots,|\mathcal O_r|\), then building \(\mathcal P(n)\) costs the iterative lcm-closure work induced by those choices.

Memory usage is modest. The program stores cached order lists for odd parts already processed, temporary polynomial data for one factorization, the current period set for a given \(n\), and the final global set of distinct periods.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=843
2. Berlekamp's algorithm: Wikipedia — Berlekamp's algorithm
3. Finite field: Wikipedia — Finite field
4. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
5. Multiplicative order: Wikipedia — Multiplicative order