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.
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.$$
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}.$$
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.
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.
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.
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.
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\}.$$
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.
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.
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.
Für jedes \(n \ge 3\) betrachten wir binäre Zustände auf einem Kreis der Länge \(n\). Ein Update ersetzt jeden Eintrag durch das xor seiner beiden Nachbarn; die Dynamik ist also linear über \(\mathbb F_2\). Eine positive Zahl \(t\) gehört zu \(\mathcal P(n)\), wenn es einen Zustand mit kleinster Periode \(t\) unter dieser Vorschrift gibt.
Gesucht ist
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
Die Implementierungen simulieren die Zustände nicht direkt, sondern beschreiben das Update als Multiplikation in einem Quotientenring, analysieren jeden irreduziblen Faktor getrennt und setzen die möglichen Perioden per kgV wieder zusammen.
Der natürliche Zustandsraum für einen Kreis der Größe \(n\) ist
$$R_n=\mathbb F_2[x]/(x^n+1).$$
Ein binärer Zustand \((a_0,\dots,a_{n-1})\) wird codiert durch
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
Multiplikation mit \(x\) verschiebt nach links, Multiplikation mit \(x^{n-1}=x^{-1}\) nach rechts. Deshalb lautet der Update-Operator
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$$
Schreibe
$$n=2^k m,\qquad m\text{ ungerade}.$$
In Charakteristik \(2\) liefert der Frobenius
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$$
Da \(m\) ungerade ist, hat \(x^m+1\) die Ableitung \(x^{m-1}\) und ist daher quadratfrei. Also gilt
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
mit paarweise verschiedenen irreduziblen Faktoren \(g_j\). Damit folgt
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$$
Weil die Faktoren \(g_j^{2^k}\) teilerfremd sind, liefert der chinesische Restsatz
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$$
Die Dynamik zerfällt also in unabhängige lokale Komponenten. Hat eine lokale Komponente Periode \(u_j\), dann besitzt der Gesamtzustand die Periode
$$\operatorname{lcm}(u_1,\dots,u_r).$$
Somit genügt es, für jeden irreduziblen Faktor die möglichen lokalen Perioden zu bestimmen.
Zuerst reduziert man nur modulo \(g_j\), nicht modulo der höheren Potenz \(g_j^{2^k}\). Im Körper
$$K_j=\mathbb F_2[x]/(g_j(x))$$
gilt \(x^m=1\), also \(x^{-1}=x^{m-1}\). Der lokale Multiplikator ist daher
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$$
Dabei gibt es drei Fälle.
Ist \(\lambda_j=0\), so ist der gehobene Operator auf diesem Zweig nilpotent und kann nur die Periode \(1\) liefern.
Ist \(\lambda_j=1\), dann ist der semisimple Teil trivial, und nach dem Heben können nur Zweierpotenzen auftreten.
Ist \(\lambda_j\neq 0,1\), dann liegt \(\lambda_j\) in \(K_j^\times\) und besitzt eine multiplikative Ordnung \(r_j\).
Die Implementierungen berechnen \(r_j\), indem sie das kleinste \(e_j\) suchen mit
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
Dann liegt \(\lambda_j\) im Unterkörper \(\mathbb F_{2^{e_j}}\), also
$$r_j\mid 2^{e_j}-1.$$
Ausgehend von \(2^{e_j}-1\) werden Primfaktoren entfernt, solange der entsprechende Potenztest weiterhin \(1\) ergibt. So bleibt genau die wahre Ordnung übrig.
Nun kehren wir in den lokalen Ring \(\mathbb F_2[x]/(g_j^{2^k})\) zurück. Falls \(\lambda_j\neq 0\), lässt sich der gehobene Multiplikator schreiben als
$$\lambda_j(1+u),\qquad u^{2^k}=0,$$
wobei \(u\) im nilpotenten Teil liegt, der durch den mehrfachen Faktor \(g_j^{2^k}\) entsteht. In Charakteristik \(2\) gilt
$$ (1+u)^{2^s}=1+u^{2^s}. $$
Der nilpotente Anteil trägt daher nur Zweierpotenzen bei. Je nach Lage des Zustands in der \(g_j\)-adischen Filtration kann bei nichttrivialem semisimplem Teil jede Potenz \(2^s\) mit \(0\le s\le k\) auftreten, und im Fall \(\lambda_j=1\) jede Potenz \(2^s\) mit \(1\le s\le k\).
Damit sind die lokalen Periodenoptionen
$$ \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} $$
Das anfängliche \(1\) entspricht der Wahl eines lokalen Zustands mit trivialem periodischem Anteil.
Wegen der Unabhängigkeit der lokalen Faktoren ist die vollständige Periodenmenge für diese Kreisgröße genau
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$$
In dieser Formel steckt bereits der ganze Algorithmus: \(x^m+1\) faktorisieren, pro irreduziblem Faktor eine lokale Optionsmenge berechnen und dann unter dem kgV abschließen.
Für \(n=5\) gilt \(k=0\) und
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
Beim Faktor \(x+1\) setzt man \(x=1\), also ist \(\lambda=1+1=0\); dieser Faktor liefert nur \(1\).
Beim quartischen Faktor sei \(\alpha\) eine Nullstelle. Aus \(\alpha^5=1\) folgt
$$\lambda=\alpha+\alpha^4.$$
Mit \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\) erhält man
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
also hat \(\lambda\) die Ordnung \(3\). Da \(k=0\) ist, trägt der zweite Faktor \(\{1,3\}\) bei und somit
$$\mathcal P(5)=\{1,3\}.$$
Für \(n=6\) hat man \(n=2\cdot 3\), also \(k=1\) und
$$x^3+1=(x+1)(x^2+x+1).$$
Der lineare Faktor gibt wieder \(\lambda=0\). Im quadratischen Faktor impliziert \(x^2+x+1=0\), dass \(x^2=x+1\), also
$$\lambda=x+x^2=1.$$
Dann sind die lokalen Perioden \(1\) und \(2\), also
$$\mathcal P(6)=\{1,2\}.$$
Nachdem \(\mathcal P(n)\) für jedes \(3\le n\le N\) bestimmt ist, werden alle Perioden in eine globale Menge eingefügt,
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$$
und die gesuchte Größe ist
$$S(N)=\sum_{v\in\mathcal G(N)} v.$$
Deshalb zählt das Programm nur verschiedene Periodenwerte und nicht die Anzahl der Zustände, die sie realisieren.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst erzeugen sie gewöhnliche Primzahlen bis zu einer Grenze, die ausreicht, um die Zahlen \(2^e-1\) aus dem Ordnungsschritt zu faktorisieren.
Danach implementieren sie Polynomarithmetik über \(\mathbb F_2\): Grad, Rest, Quotient, größter gemeinsamer Teiler, Multiplikation modulo eines Polynoms und schnelle modulare Potenzierung. Mit diesen Bausteinen wird \(x^m+1\) für jede ungerade Teilzahl \(m\) per Berlekamp zerlegt.
Für jeden irreduziblen Faktor wird der lokale Multiplikator \(x+x^{m-1}\) ausgewertet, die Sonderfälle \(0\) und \(1\) werden erkannt, und sonst wird die multiplikative Ordnung durch wiederholtes Frobenius-Quadratieren und anschließendes Reduzieren innerhalb von \(2^e-1\) bestimmt.
Diese lokalen Ordnungen werden in die Optionsmengen \(\mathcal O_j\) übersetzt. Ein iterativer kgV-Abschluss erzeugt daraus \(\mathcal P(n)\). Die Ordnungsdaten werden nach dem ungeraden Anteil \(m\) gecacht, sodass Größen wie \(m,2m,4m,\dots\) dieselbe Faktoranalyse wiederverwenden und sich nur im Zweierhebe-Bereich unterscheiden.
Zum Schluss vereinigen die Implementierungen alle Periodenmengen für \(3\le n\le N\) und summieren die verschiedenen Werte. Die Kontrollwerte \(\mathcal P(5)=\{1,3\}\), \(\mathcal P(6)=\{1,2\}\) und \(S(30)=20381\) stimmen exakt mit der Herleitung überein.
Sei \(U=\{m\le N:m\text{ ungerade}\}\). Jeder ungerade Anteil wird nur einmal faktorisiert; die dominante algebraische Arbeit ist also die Summe der Faktorisierungen von \(x^m+1\) über \(\mathbb F_2\) für \(m\in U\). In dieser direkten Umsetzung ist die lineare Algebra des Berlekamp-Verfahrens bei Grad \(m\) bis auf Bitdetails kubisch in \(m\), was für \(N=100\) sehr klein bleibt.
Sind die Faktoren bekannt, dann benutzt die Ordnungsberechnung für einen Faktor vom Grad \(d\) wiederholtes Quadrieren im Körper sowie Tests auf Teilern von \(2^e-1\), wobei \(e\le d\) gilt. Die Konstruktion der Periodenmengen ist eher kombinatorisch: Haben die lokalen Optionsmengen die Größen \(|\mathcal O_1|,\dots,|\mathcal O_r|\), dann wird \(\mathcal P(n)\) durch den entsprechenden iterativen kgV-Abschluss aufgebaut.
Der Speicherbedarf ist moderat. Gespeichert werden gecachte Ordnungslisten für bereits behandelte ungerade Teile, temporäre Polynomdaten für jeweils eine Faktorisierung, die aktuelle Periodenmenge für ein festes \(n\) und am Ende die globale Menge aller verschiedenen Perioden.
Her \(n \ge 3\) için, uzunluğu \(n\) olan ikili bir çember düşünülür. Bir güncellemede her hücre, iki komşusunun xor değeriyle değiştirilir; dolayısıyla dinamik \(\mathbb F_2\) üzerinde lineerdir. Pozitif bir \(t\) sayısı, bu kural altında en küçük periyodu \(t\) olan en az bir durum varsa \(\mathcal P(n)\) kümesine girer.
Aranan küresel büyüklük
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
Uygulamalar tüm durumları brute force denemek yerine, güncelleme kuralını bir bölüm halkasında çarpma olarak yazar, her indirgenemez çarpanı ayrı inceler ve olası periyotları EKOK ile tekrar birleştirir.
Boyutu \(n\) olan çember için doğal durum uzayı
$$R_n=\mathbb F_2[x]/(x^n+1)$$
halkasıdır. Bir ikili durum \((a_0,\dots,a_{n-1})\) şu polinomla temsil edilir:
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
\(x\) ile çarpmak sola kaydırma, \(x^{n-1}=x^{-1}\) ile çarpmak sağa kaydırma olduğundan güncelleme operatörü
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A$$
şeklindedir.
Şöyle yazalım:
$$n=2^k m,\qquad m\text{ tek}.$$
Karakteristik \(2\)'de Frobenius özdeşliği
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}$$
verir. \(m\) tek olduğu için \(x^m+1\)'in türevi \(x^{m-1}\) olur; dolayısıyla bu polinom kareden arınmıştır. O halde
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
şeklinde, birbirinden farklı indirgenemez çarpanlara ayrılır ve buradan
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}$$
elde edilir.
\(g_j^{2^k}\) çarpanları aralarında asal olduğundan Çin kalan teoremi
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right)$$
sonucunu verir. Böylece dinamik bağımsız yerel bileşenlere ayrılır. Bir yerel bileşenin periyodu \(u_j\) ise, tüm durumun periyodu
$$\operatorname{lcm}(u_1,\dots,u_r)$$
olur. Demek ki asıl yapılması gereken, her indirgenemez çarpanın katkı verebileceği yerel periyotları bulmaktır.
Önce yalnızca \(g_j\)'ye göre mod alalım; \(g_j^{2^k}\)'ye göre değil. Şu sonlu alanda
$$K_j=\mathbb F_2[x]/(g_j(x))$$
\(x^m=1\) olduğundan \(x^{-1}=x^{m-1}\) yazabiliriz. Yerel çarpan böylece
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}$$
olur. Burada üç ayrı durum vardır.
\(\lambda_j=0\) ise, yukarı kaldırılmış operatör bu dalda nilpotent olur ve yalnızca \(1\) periyodunu verebilir.
\(\lambda_j=1\) ise, yarıbasit kısım önemsizdir ve yukarı kaldırmadan sonra yalnızca \(2\)'nin kuvvetleri ortaya çıkar.
\(\lambda_j\neq 0,1\) ise, \(\lambda_j\) elemanı \(K_j^\times\) içinde bir çarpımsal mertebeye sahiptir; buna \(r_j\) diyelim.
Uygulamalar \(r_j\)'yi bulmak için önce şu eşitliği sağlayan en küçük \(e_j\) değerini saptar:
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
Bu, \(\lambda_j\)'nin \(\mathbb F_{2^{e_j}}\) alt alanında yaşadığını gösterir; dolayısıyla
$$r_j\mid 2^{e_j}-1.$$
Daha sonra \(2^{e_j}-1\)'in asal bölenleri tek tek çıkarılır; ilgili üs denemesi hâlâ \(1\) veriyorsa bölen silinir. Sonunda gerçek çarpımsal mertebe kalır.
Şimdi yerel halka \(\mathbb F_2[x]/(g_j^{2^k})\)'ye dönelim. \(\lambda_j\neq 0\) ise yukarı kaldırılmış çarpan
$$\lambda_j(1+u),\qquad u^{2^k}=0$$
biçiminde yazılabilir. Buradaki \(u\), tekrarlı çarpan \(g_j^{2^k}\)'nin oluşturduğu nilpotent kısımdadır. Karakteristik \(2\)'de
$$ (1+u)^{2^s}=1+u^{2^s} $$
olduğu için nilpotent düzeltme yalnızca \(2\)'nin kuvvetlerini ekler. Durumun \(g_j\)-adik filtrasyondaki derinliğine göre, yarıbasit kısım önemsiz değilse \(0\le s\le k\) için her \(2^s\), yarıbasit kısım \(1\) ise \(1\le s\le k\) için her \(2^s\) gerçekleşebilir.
Böylece yerel periyot seçenekleri
$$ \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} $$
şeklini alır. Baştaki \(1\), yerel periyodik kısmı önemsiz olan bir durum seçimini temsil eder.
Yerel çarpanlar bağımsız olduğundan, bu çember boyutu için tam periyot kümesi
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}$$
olur. Yani algoritmanın özü şudur: \(x^m+1\)'i çarpanlara ayır, her indirgenemez çarpan için bir yerel seçenek kümesi üret ve ardından EKOK kapanışını al.
\(n=5\) için \(k=0\) ve
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
\(x+1\) çarpanında \(x=1\) yazılır, dolayısıyla \(\lambda=1+1=0\); bu dal yalnızca \(1\) katkısı yapar.
Dördüncü dereceden çarpanda bir köke \(\alpha\) dersek ve \(\alpha^5=1\) kullanırsak
$$\lambda=\alpha+\alpha^4$$
olur. Ayrıca \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\) olduğundan
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
yani \(\lambda\)'nin mertebesi \(3\)'tür. \(k=0\) olduğundan ikinci çarpan \(\{1,3\}\) verir ve
$$\mathcal P(5)=\{1,3\}$$
elde edilir.
\(n=6\) için \(n=2\cdot 3\), yani \(k=1\), ve
$$x^3+1=(x+1)(x^2+x+1).$$
Lineer çarpan yine \(\lambda=0\) verir. Kuadratik çarpanda \(x^2+x+1=0\) olduğundan \(x^2=x+1\) ve
$$\lambda=x+x^2=1$$
olur. Bu durumda yerel periyotlar \(1\) ve \(2\)'dir; dolayısıyla
$$\mathcal P(6)=\{1,2\}.$$
Her \(3\le n\le N\) için \(\mathcal P(n)\) hesaplandıktan sonra bütün periyotlar tek bir kümede toplanır:
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n).$$
Son cevap da
$$S(N)=\sum_{v\in\mathcal G(N)} v$$
olur. Bu yüzden program, her periyodun kaç farklı durumdan geldiğini değil yalnızca hangi periyotların ortaya çıktığını önemser.
C++, Python ve Java uygulamaları aynı hattı izler. Önce, mertebe azaltma aşamasında ortaya çıkan \(2^e-1\) sayıları çarpanlara ayırmaya yetecek kadar asal sayı önceden üretilir.
Daha sonra \(\mathbb F_2\) üzerinde polinom aritmetiği kurulur: derece, kalan, bölüm, EBOB, bir polinoma göre modlu çarpma ve hızlı modüler üs alma. Bu araçlarla her tek kısım \(m\) için \(x^m+1\) Berlekamp yöntemiyle çarpanlara ayrılır.
Her indirgenemez çarpan için yerel çarpan \(x+x^{m-1}\) hesaplanır, \(0\) ve \(1\) özel durumları ayrılır; diğer durumlarda çarpımsal mertebe, ardışık Frobenius karesine alma ve ardından \(2^e-1\) içindeki bölenleri temizleme ile bulunur.
Bu yerel mertebeler \(\mathcal O_j\) seçenek kümelerine dönüştürülür. İteratif EKOK kapanışı ile \(\mathcal P(n)\) elde edilir. Tek kısım \(m\) bazında önbellek kullanıldığı için \(m,2m,4m,\dots\) gibi boyutlar aynı alan-çarpan analizini tekrar kullanır; yalnızca ikinin kuvveti kadar yükseltme aralığı değişir.
Son olarak bütün \(3\le n\le N\) için bulunan periyot kümeleri birleşime eklenir ve farklı değerler toplanır. \(\mathcal P(5)=\{1,3\}\), \(\mathcal P(6)=\{1,2\}\) ve \(S(30)=20381\) denetimleri bu türetimle tam uyumludur.
\(U=\{m\le N:m\text{ tek}\}\) olsun. Her tek kısım yalnızca bir kez çarpanlara ayrılır; bu nedenle baskın cebirsel iş, \(m\in U\) için \(x^m+1\)'in \(\mathbb F_2\) üzerinde ayrıştırılmasının toplamıdır. Bu doğrudan uygulamada, Berlekamp doğrusal cebiri bit düzeyi ayrıntıları saklı tutulursa derece \(m\) için kübik davranır; \(N=100\) için bu maliyet çok küçüktür.
Çarpanlar bilindikten sonra, derece \(d\) olan bir çarpan için mertebe hesabı sonlu alanda ardışık karesini alma ve \(e\le d\) olmak üzere \(2^e-1\)'in bölenleri üzerinde test yapma maliyeti taşır. Periyot kümesi inşası ise daha çok kombinatoriktir: yerel seçenek kümelerinin boyutları \(|\mathcal O_1|,\dots,|\mathcal O_r|\) ise, \(\mathcal P(n)\) bu seçimlerin EKOK kapanışıyla oluşturulur.
Bellek kullanımı düşüktür. Program daha önce işlenmiş tek kısımlar için önbelleğe alınmış mertebe listelerini, tek bir faktorizasyon için geçici polinom verilerini, sabit bir \(n\) için geçerli periyot kümesini ve sonunda da tüm farklı periyotların küresel kümesini tutar.
Para cada \(n \ge 3\), se consideran estados binarios sobre un círculo de longitud \(n\). En una actualización, cada entrada se sustituye por el xor de sus dos vecinas, así que toda la dinámica es lineal sobre \(\mathbb F_2\). Un entero positivo \(t\) pertenece a \(\mathcal P(n)\) si existe algún estado cuya menor periodo bajo esta regla es exactamente \(t\).
La cantidad global buscada es
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
Las implementaciones no simulan todos los estados. En su lugar, convierten la regla de actualización en una multiplicación dentro de un anillo cociente, estudian cada factor irreducible por separado y reconstruyen los periodos posibles mediante m.c.m.
El espacio natural de estados para un círculo de tamaño \(n\) es
$$R_n=\mathbb F_2[x]/(x^n+1).$$
Un estado binario \((a_0,\dots,a_{n-1})\) se codifica como
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
Multiplicar por \(x\) desplaza a la izquierda y multiplicar por \(x^{n-1}=x^{-1}\) desplaza a la derecha. Por tanto, el operador de evolución es
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$$
Escribimos
$$n=2^k m,\qquad m\text{ impar}.$$
En característica \(2\), la identidad de Frobenius da
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$$
Como \(m\) es impar, la derivada de \(x^m+1\) es \(x^{m-1}\), de modo que \(x^m+1\) es libre de cuadrados. Entonces
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
con factores irreducibles distintos \(g_j\), y por consiguiente
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$$
Como los factores \(g_j^{2^k}\) son coprimos entre sí, el teorema chino del resto implica
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$$
Así, la dinámica se descompone en componentes locales independientes. Si una componente local tiene periodo \(u_j\), el estado completo tiene periodo
$$\operatorname{lcm}(u_1,\dots,u_r).$$
Por eso el problema real es describir qué periodos locales puede aportar cada factor irreducible.
Primero se reduce módulo \(g_j\), no módulo \(g_j^{2^k}\). En el cuerpo
$$K_j=\mathbb F_2[x]/(g_j(x))$$
se cumple \(x^m=1\), luego \(x^{-1}=x^{m-1}\). El multiplicador local pasa a ser
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$$
Hay tres casos.
Si \(\lambda_j=0\), la elevación al factor repetido será nilpotente y solo podrá contribuir con periodo \(1\).
Si \(\lambda_j=1\), la parte semisimple es trivial y, al elevar, solo aparecen potencias de \(2\).
Si \(\lambda_j\neq 0,1\), entonces \(\lambda_j\in K_j^\times\) tiene un orden multiplicativo \(r_j\).
Las implementaciones calculan \(r_j\) buscando primero el menor \(e_j\) tal que
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
Eso significa que \(\lambda_j\) vive en el subcuerpo \(\mathbb F_{2^{e_j}}\), así que
$$r_j\mid 2^{e_j}-1.$$
A partir de \(2^{e_j}-1\), se eliminan factores primos siempre que la prueba de potencia correspondiente siga dando \(1\), hasta quedarse con el orden exacto.
Volvamos ahora al anillo local \(\mathbb F_2[x]/(g_j^{2^k})\). Si \(\lambda_j\neq 0\), el multiplicador elevado puede escribirse como
$$\lambda_j(1+u),\qquad u^{2^k}=0,$$
donde \(u\) pertenece a la parte nilpotente creada por el factor repetido \(g_j^{2^k}\). En característica \(2\),
$$ (1+u)^{2^s}=1+u^{2^s}. $$
Por tanto, la corrección nilpotente solo añade potencias de \(2\). Al variar la profundidad del estado en la filtración \(g_j\)-ádica, puede aparecer cualquier \(2^s\) con \(0\le s\le k\) si la parte semisimple es no trivial, y cualquier \(2^s\) con \(1\le s\le k\) cuando la parte semisimple vale \(1\).
En consecuencia, las opciones locales de periodo son
$$ \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} $$
El \(1\) inicial corresponde a escoger una componente local con parte periódica trivial.
Como los factores locales son independientes, el conjunto completo de periodos para ese tamaño de círculo es
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$$
Esta fórmula resume todo el algoritmo: factorizar \(x^m+1\), calcular un conjunto local para cada factor irreducible y cerrar después bajo m.c.m.
Para \(n=5\), tenemos \(k=0\) y
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
En el factor \(x+1\), al sustituir \(x=1\) se obtiene \(\lambda=1+1=0\), así que solo aporta \(1\).
En el factor cuártico, sea \(\alpha\) una raíz. Como \(\alpha^5=1\),
$$\lambda=\alpha+\alpha^4.$$
Usando \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\), se obtiene
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
de donde \(\lambda\) tiene orden \(3\). Como \(k=0\), el segundo factor aporta \(\{1,3\}\), y por tanto
$$\mathcal P(5)=\{1,3\}.$$
Para \(n=6\), se tiene \(n=2\cdot 3\), así que \(k=1\), y
$$x^3+1=(x+1)(x^2+x+1).$$
El factor lineal vuelve a dar \(\lambda=0\). En el factor cuadrático, \(x^2+x+1=0\) implica \(x^2=x+1\), luego
$$\lambda=x+x^2=1.$$
Así, los periodos locales son \(1\) y \(2\), y entonces
$$\mathcal P(6)=\{1,2\}.$$
Después de calcular \(\mathcal P(n)\) para cada \(3\le n\le N\), se insertan todos los periodos en un único conjunto global
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$$
y la respuesta final es
$$S(N)=\sum_{v\in\mathcal G(N)} v.$$
Por eso el programa solo necesita saber qué periodos aparecen, no cuántos estados distintos producen cada uno.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero generan suficientes primos ordinarios para factorizar los enteros \(2^e-1\) que surgen en la reducción de órdenes.
Luego implementan aritmética de polinomios sobre \(\mathbb F_2\): grado, resto, cociente, máximo común divisor, multiplicación módulo un polinomio y exponenciación modular rápida. Con esas herramientas aplican la factorización de Berlekamp a \(x^m+1\) para cada parte impar \(m\).
Para cada factor irreducible, la implementación evalúa el multiplicador local \(x+x^{m-1}\), separa los casos especiales \(0\) y \(1\), y en el resto calcula el orden multiplicativo combinando cuadrados de Frobenius con la eliminación de divisores dentro de \(2^e-1\).
Esos órdenes locales se convierten en los conjuntos de opciones \(\mathcal O_j\). Un cierre iterativo por m.c.m. produce \(\mathcal P(n)\). Los datos de órdenes se guardan en caché por la parte impar \(m\), así que tamaños como \(m,2m,4m,\dots\) reutilizan la misma descomposición en cuerpos finitos y solo cambian en el rango de elevación por potencias de \(2\).
Por último, las implementaciones unen todos los conjuntos de periodos para \(3\le n\le N\) y suman los valores distintos. Los puntos de control \(\mathcal P(5)=\{1,3\}\), \(\mathcal P(6)=\{1,2\}\) y \(S(30)=20381\) concuerdan exactamente con la derivación matemática.
Sea \(U=\{m\le N:m\text{ impar}\}\). Cada parte impar se factoriza una sola vez, así que el trabajo algebraico dominante es la suma, sobre \(m\in U\), de factorizar \(x^m+1\) en \(\mathbb F_2\). En esta implementación directa, el álgebra lineal del método de Berlekamp es cúbica en \(m\), salvo detalles de operaciones a nivel de bits, y resulta sobradamente pequeña para \(N=100\).
Una vez conocidos los factores, el cálculo del orden para un factor de grado \(d\) usa cuadrados repetidos en el cuerpo y pruebas sobre divisores de \(2^e-1\), con \(e\le d\). La construcción del conjunto de periodos es más combinatoria: si los conjuntos locales tienen tamaños \(|\mathcal O_1|,\dots,|\mathcal O_r|\), entonces \(\mathcal P(n)\) se obtiene mediante el trabajo del cierre iterativo por m.c.m. inducido por esas elecciones.
El consumo de memoria es moderado. El programa guarda listas de órdenes en caché para las partes impares ya procesadas, datos temporales de polinomios para una factorización concreta, el conjunto de periodos del \(n\) actual y el conjunto global final de periodos distintos.
对每个 \(n \ge 3\)，题目考虑长度为 \(n\) 的二元圆环状态。一次更新把每个位置替换成它左右两个邻居的 xor，因此整个演化在 \(\mathbb F_2\) 上是线性的。如果存在某个状态在这条更新规则下的最小正周期恰好为 \(t\)，那么 \(t\) 就属于 \(\mathcal P(n)\)。
最终要求的是
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
实现并不暴力枚举所有状态，而是把更新写成一个商环中的乘法，分别分析每个不可约因子，然后用最小公倍数把局部周期重新拼成全局周期。
大小为 \(n\) 的圆环，其自然状态空间是
$$R_n=\mathbb F_2[x]/(x^n+1).$$
一个二元状态 \((a_0,\dots,a_{n-1})\) 可以编码成
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
乘以 \(x\) 对应向左平移，乘以 \(x^{n-1}=x^{-1}\) 对应向右平移，所以更新算子就是
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$$
写成
$$n=2^k m,\qquad m\text{ 为奇数}.$$
在特征 \(2\) 下，Frobenius 恒等式给出
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$$
由于 \(m\) 为奇数，\(x^m+1\) 的导数是 \(x^{m-1}\)，因此它是平方自由的。于是
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
其中 \(g_j\) 两两不同且都不可约，从而
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$$
因为这些 \(g_j^{2^k}\) 彼此互素，中国剩余定理给出
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$$
这意味着整体动力学分解成若干彼此独立的局部分支。如果某个局部分支的周期是 \(u_j\)，那么整个状态的周期就是
$$\operatorname{lcm}(u_1,\dots,u_r).$$
因此真正需要解决的是：每个不可约因子到底能贡献哪些局部周期。
先只模掉 \(g_j\)，而不是更高次的 \(g_j^{2^k}\)。在有限域
$$K_j=\mathbb F_2[x]/(g_j(x))$$
中有 \(x^m=1\)，所以 \(x^{-1}=x^{m-1}\)。于是局部乘子变成
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$$
这里会出现三种情况。
如果 \(\lambda_j=0\)，那么提升到重复因子之后，这一支上的算子是幂零的，因此只能贡献周期 \(1\)。
如果 \(\lambda_j=1\)，那么半单部分是平凡的，提升之后只会产生 \(2\) 的幂。
如果 \(\lambda_j\neq 0,1\)，那么 \(\lambda_j\in K_j^\times\) 有一个乘法阶 \(r_j\)。
实现求 \(r_j\) 的办法是，先找最小的 \(e_j\) 使得
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
这说明 \(\lambda_j\) 实际上落在子域 \(\mathbb F_{2^{e_j}}\) 中，因此
$$r_j\mid 2^{e_j}-1.$$
接着从 \(2^{e_j}-1\) 出发，只要除掉某个素因子以后对应的幂测试仍然得到 \(1\)，就继续约掉它；最后剩下的就是精确的乘法阶。
现在回到局部环 \(\mathbb F_2[x]/(g_j^{2^k})\)。若 \(\lambda_j\neq 0\)，提升后的乘子可以写成
$$\lambda_j(1+u),\qquad u^{2^k}=0,$$
其中 \(u\) 位于由重复因子 \(g_j^{2^k}\) 带来的幂零部分。因为特征是 \(2\)，有
$$ (1+u)^{2^s}=1+u^{2^s}. $$
所以幂零修正只能额外引入 \(2\) 的幂次。随着状态在 \(g_j\)-adic 过滤中的深度变化，当半单部分非平凡时，\(0\le s\le k\) 的每个 \(2^s\) 都可能出现；当半单部分等于 \(1\) 时，可能出现的是 \(1\le s\le k\) 的各个 \(2^s\)。
因此局部可选周期集合为
$$ \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} $$
最前面的 \(1\) 对应于选择一个局部周期部分为平凡的状态。
由于各个局部分支彼此独立，这个 \(n\) 的完整周期集合正是
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$$
这条公式就是整个算法的核心：分解 \(x^m+1\)，为每个不可约因子得到一个局部选项集合，再对这些选项做最小公倍数闭包。
当 \(n=5\) 时，\(k=0\)，并且
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
在线性因子 \(x+1\) 上代入 \(x=1\)，得到 \(\lambda=1+1=0\)，所以这一支只能贡献 \(1\)。
在四次因子上，设 \(\alpha\) 是它的一个根。由 \(\alpha^5=1\) 可得
$$\lambda=\alpha+\alpha^4.$$
再利用 \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\)，可算出
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
因此 \(\lambda\) 的乘法阶为 \(3\)。因为 \(k=0\)，第二个因子贡献 \(\{1,3\}\)，所以
$$\mathcal P(5)=\{1,3\}.$$
当 \(n=6\) 时，\(n=2\cdot 3\)，因此 \(k=1\)，而且
$$x^3+1=(x+1)(x^2+x+1).$$
线性因子仍然给出 \(\lambda=0\)。在二次因子里，\(x^2+x+1=0\) 推出 \(x^2=x+1\)，于是
$$\lambda=x+x^2=1.$$
这时局部周期就是 \(1\) 和 \(2\)，因此
$$\mathcal P(6)=\{1,2\}.$$
对每个 \(3\le n\le N\) 算出 \(\mathcal P(n)\) 之后，把所有周期都放入一个全局集合
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$$
最后所求就是
$$S(N)=\sum_{v\in\mathcal G(N)} v.$$
因此程序只关心哪些周期出现过，而不关心每个周期由多少个状态实现。
C++、Python 和 Java 实现走的是同一条路线。首先，它们预先生成足够多的普通素数，以便分解在求阶过程中出现的 \(2^e-1\) 这类整数。
然后它们实现 \(\mathbb F_2\) 上的多项式运算：次数、取模、商、多项式 gcd、模多项式乘法以及快速模幂。有了这些工具，就可以对每个奇数部分 \(m\) 的 \(x^m+1\) 执行 Berlekamp 分解。
对于每个不可约因子，程序计算局部乘子 \(x+x^{m-1}\)，识别 \(0\) 和 \(1\) 这两个特殊情况；若不是特殊值，就通过反复 Frobenius 平方并结合 \(2^e-1\) 的因子剥离，得到精确的乘法阶。
这些局部阶被转成 \(\mathcal O_j\) 选项集合，再通过迭代的最小公倍数闭包生成 \(\mathcal P(n)\)。局部阶数据会按奇数部分 \(m\) 做缓存，所以 \(m,2m,4m,\dots\) 这样的长度共享同一份有限域分解结果，只是在 \(2\) 的幂提升范围上不同。
最后，程序把所有 \(3\le n\le N\) 的周期集合取并集，并对不同的周期值求和。校验点 \(\mathcal P(5)=\{1,3\}\)、\(\mathcal P(6)=\{1,2\}\) 和 \(S(30)=20381\) 与上面的数学推导完全一致。
设 \(U=\{m\le N:m\text{ 为奇数}\}\)。每个奇数部分只会被分解一次，因此主导的代数开销，是对所有 \(m\in U\) 的 \(x^m+1\) 在 \(\mathbb F_2\) 上做因式分解之和。在这种直接实现中，Berlekamp 方法里的线性代数对次数 \(m\) 来说可以看作立方级别，忽略位运算细节后，对 \(N=100\) 仍然非常轻量。
一旦因子已知，次数为 \(d\) 的某个因子的求阶过程需要在有限域中做重复平方，并测试 \(2^e-1\) 的各个候选除数，其中 \(e\le d\)。周期集合的构造则更偏组合型：如果局部选项集合大小为 \(|\mathcal O_1|,\dots,|\mathcal O_r|\)，那么 \(\mathcal P(n)\) 的生成成本就是这些选择所诱导的最小公倍数闭包工作量。
内存占用并不高。程序保存已经处理过的奇数部分对应的局部阶缓存、一次分解所需的临时多项式数据、当前某个 \(n\) 的周期集合，以及最终所有不同周期组成的全局集合。
Для каждого \(n \ge 3\) рассматриваются двоичные состояния на окружности длины \(n\). За один шаг каждое значение заменяется xor двух соседей, поэтому вся динамика линейна над \(\mathbb F_2\). Положительное число \(t\) входит в \(\mathcal P(n)\), если существует состояние, чей наименьший период при этом обновлении равен \(t\).
Искомая глобальная величина равна
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
Реализации не перебирают все состояния напрямую. Вместо этого правило обновления записывается как умножение в фактор-кольце, каждый неприводимый множитель анализируется отдельно, а затем возможные периоды собираются обратно через НОК.
Естественное пространство состояний для окружности размера \(n\) имеет вид
$$R_n=\mathbb F_2[x]/(x^n+1).$$
Двоичное состояние \((a_0,\dots,a_{n-1})\) кодируется полиномом
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
Умножение на \(x\) сдвигает влево, а умножение на \(x^{n-1}=x^{-1}\) сдвигает вправо, поэтому оператор эволюции равен
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$$
Запишем
$$n=2^k m,\qquad m\text{ нечётно}.$$
В характеристике \(2\) тождество Фробениуса даёт
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$$
Так как \(m\) нечётно, производная \(x^m+1\) равна \(x^{m-1}\), значит этот многочлен свободен от квадратов. Поэтому
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
с попарно различными неприводимыми множителями \(g_j\), и отсюда
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$$
Поскольку множители \(g_j^{2^k}\) взаимно просты, китайская теорема об остатках даёт
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$$
Следовательно, динамика раскладывается на независимые локальные ветви. Если локальная ветвь имеет период \(u_j\), то весь глобальный период равен
$$\operatorname{lcm}(u_1,\dots,u_r).$$
Значит, основная задача сводится к описанию локальных периодов, которые может дать каждый неприводимый фактор.
Сначала редуцируем только по модулю \(g_j\), а не по модулю \(g_j^{2^k}\). В поле
$$K_j=\mathbb F_2[x]/(g_j(x))$$
выполняется \(x^m=1\), поэтому \(x^{-1}=x^{m-1}\). Локальный множитель принимает вид
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$$
Здесь возможны три случая.
Если \(\lambda_j=0\), то после подъёма на повторённый множитель оператор становится нильпотентным и может дать только период \(1\).
Если \(\lambda_j=1\), то полупростая часть тривиальна, и после подъёма появляются только степени двойки.
Если \(\lambda_j\neq 0,1\), то \(\lambda_j\in K_j^\times\) имеет мультипликативный порядок \(r_j\).
Реализации находят \(r_j\), сначала определяя наименьшее \(e_j\), для которого
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
Это означает, что \(\lambda_j\) лежит в подполе \(\mathbb F_{2^{e_j}}\), и потому
$$r_j\mid 2^{e_j}-1.$$
Далее из числа \(2^{e_j}-1\) по одному удаляются простые делители, пока соответствующий тест степени по-прежнему даёт \(1\). Оставшееся значение и есть точный порядок.
Теперь вернёмся в локальное кольцо \(\mathbb F_2[x]/(g_j^{2^k})\). Если \(\lambda_j\neq 0\), поднятый множитель можно записать как
$$\lambda_j(1+u),\qquad u^{2^k}=0,$$
где \(u\) лежит в нильпотентной части, создаваемой повторённым множителем \(g_j^{2^k}\). В характеристике \(2\) верно
$$ (1+u)^{2^s}=1+u^{2^s}. $$
Значит, нильпотентная поправка вносит только степени двойки. При изменении глубины состояния в \(g_j\)-адической фильтрации возникают все множители \(2^s\) с \(0\le s\le k\) в случае нетривиальной полупростой части и все \(2^s\) с \(1\le s\le k\) в случае \(\lambda_j=1\).
Следовательно, локальные варианты периодов имеют вид
$$ \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} $$
Начальная единица соответствует выбору локального состояния с тривиальной периодической частью.
Так как локальные ветви независимы, полное множество периодов для данного размера окружности равно
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$$
Именно в этой формуле сосредоточен весь алгоритм: разложить \(x^m+1\), построить по одному локальному множеству для каждого неприводимого множителя и затем замкнуть всё относительно НОК.
Для \(n=5\) имеем \(k=0\) и
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
На множителе \(x+1\) подставляем \(x=1\), получаем \(\lambda=1+1=0\), так что эта ветвь даёт только \(1\).
Для четвёртой степени пусть \(\alpha\) — корень. Так как \(\alpha^5=1\), имеем
$$\lambda=\alpha+\alpha^4.$$
Используя \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\), получаем
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
значит, порядок \(\lambda\) равен \(3\). Поскольку \(k=0\), второй множитель даёт \(\{1,3\}\), и потому
$$\mathcal P(5)=\{1,3\}.$$
Для \(n=6\) имеем \(n=2\cdot 3\), следовательно \(k=1\), и
$$x^3+1=(x+1)(x^2+x+1).$$
Линейный множитель снова даёт \(\lambda=0\). В квадратичном множителе из \(x^2+x+1=0\) следует \(x^2=x+1\), поэтому
$$\lambda=x+x^2=1.$$
Значит, локальные периоды равны \(1\) и \(2\), и потому
$$\mathcal P(6)=\{1,2\}.$$
После вычисления \(\mathcal P(n)\) для всех \(3\le n\le N\) все периоды заносятся в одно глобальное множество
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$$
а окончательный ответ равен
$$S(N)=\sum_{v\in\mathcal G(N)} v.$$
Именно поэтому программе нужно знать только то, какие периоды встречаются, а не число состояний, реализующих каждый из них.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они заранее строят обычные простые числа, достаточные для факторизации целых чисел вида \(2^e-1\), возникающих при сокращении порядков.
Затем реализуется арифметика многочленов над \(\mathbb F_2\): степень, остаток, частное, gcd, умножение по модулю многочлена и быстрое возведение в степень по модулю. С помощью этих операций для каждой нечётной части \(m\) выполняется разложение \(x^m+1\) методом Берлекэмпа.
Для каждого неприводимого множителя вычисляется локальный множитель \(x+x^{m-1}\), отделяются особые случаи \(0\) и \(1\), а в остальных случаях мультипликативный порядок находится комбинацией повторного квадрирования Фробениуса и удаления делителей из \(2^e-1\).
Полученные локальные порядки переводятся в множества вариантов \(\mathcal O_j\). Затем итеративное замыкание по НОК строит \(\mathcal P(n)\). Данные о локальных порядках кэшируются по нечётной части \(m\), поэтому размеры \(m,2m,4m,\dots\) повторно используют тот же анализ факторизации в конечных полях и отличаются только диапазоном степеней двойки.
В конце реализации объединяют все множества периодов для \(3\le n\le N\) и суммируют различные значения. Контрольные результаты \(\mathcal P(5)=\{1,3\}\), \(\mathcal P(6)=\{1,2\}\) и \(S(30)=20381\) полностью согласуются с приведённым выводом.
Пусть \(U=\{m\le N:m\text{ нечётно}\}\). Каждая нечётная часть факторизуется только один раз, поэтому основная алгебраическая стоимость — это сумма по \(m\in U\) факторизаций \(x^m+1\) над \(\mathbb F_2\). В этой прямой реализации линейная алгебра алгоритма Берлекэмпа имеет кубическую зависимость от степени \(m\), если не учитывать детали битовых операций; для \(N=100\) это совсем небольшой объём работы.
Когда факторы уже известны, вычисление порядка для одного множителя степени \(d\) использует повторное возведение в квадрат в поле и проверки делителей числа \(2^e-1\), где \(e\le d\). Построение множества периодов носит скорее комбинаторный характер: если локальные множества имеют размеры \(|\mathcal O_1|,\dots,|\mathcal O_r|\), то \(\mathcal P(n)\) строится через индуцированное ими итеративное замыкание по НОК.
Память расходуется умеренно. Хранятся кэшированные списки порядков для уже обработанных нечётных частей, временные полиномиальные данные для одной факторизации, текущее множество периодов для фиксированного \(n\) и итоговое глобальное множество различных периодов.
لكل \(n \ge 3\)، ننظر إلى حالات ثنائية على دائرة طولها \(n\). في كل تحديث تُستبدل كل خانة بقيمة xor لجاريها، ولذلك تكون الحركة كلها خطية فوق \(\mathbb F_2\). وينتمي العدد الموجب \(t\) إلى \(\mathcal P(n)\) إذا وُجدت حالة يكون أصغر دور لها تحت هذه القاعدة مساويًا لـ \(t\).
والكمية العالمية المطلوبة هي
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),\qquad S(N)=\sum_{v\in\mathcal G(N)} v.$$
التنفيذ لا يحاكي جميع الحالات مباشرة، بل يكتب قاعدة التحديث على هيئة ضرب في حلقة خارج قسمة، ثم يحلل كل عامل أولي غير قابل للاختزال على حدة، وبعد ذلك يعيد تركيب الفترات الممكنة باستخدام المضاعف المشترك الأصغر.
فضاء الحالات الطبيعي لدائرة طولها \(n\) هو
$$R_n=\mathbb F_2[x]/(x^n+1).$$
والحالة الثنائية \((a_0,\dots,a_{n-1})\) تُمثل بالمتعدد
$$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\in R_n.$$
الضرب في \(x\) يعني إزاحة إلى اليسار، والضرب في \(x^{n-1}=x^{-1}\) يعني إزاحة إلى اليمين، ولذا يصبح مؤثر التحديث
$$T_n(A)=(x+x^{-1})A=(x+x^{n-1})A.$$
نكتب
$$n=2^k m,\qquad m\text{ odd}. $$
في الخاصية \(2\)، تعطي هوية فروبينيوس
$$x^n+1=x^{2^k m}+1=\left(x^m+1\right)^{2^k}.$$
وبما أن \(m\) فردي، فإن مشتقة \(x^m+1\) هي \(x^{m-1}\)، ولذلك يكون هذا المتعدد خاليًا من المربعات. ومن ثم
$$x^m+1=\prod_{j=1}^{r} g_j(x)$$
حيث \(g_j\) عوامل غير قابلة للاختزال ومتميزة عن بعضها، وبالتالي
$$x^n+1=\prod_{j=1}^{r} g_j(x)^{2^k}.$$
لأن العوامل \(g_j^{2^k}\) متباينة أوليًا، فإن مبرهنة البواقي الصينية تعطي
$$R_n\cong \bigoplus_{j=1}^{r}\mathbb F_2[x]/\left(g_j(x)^{2^k}\right).$$
وهذا يعني أن الحركة تتفكك إلى مكونات محلية مستقلة. فإذا كانت الفترة المحلية لإحدى المكونات هي \(u_j\)، فإن فترة الحالة الكاملة تكون
$$\operatorname{lcm}(u_1,\dots,u_r).$$
إذن المهمة الجوهرية هي تحديد الفترات المحلية الممكنة التي يأتي بها كل عامل غير قابل للاختزال.
نختزل أولًا بترديد \(g_j\) فقط، لا بترديد \(g_j^{2^k}\). في الحقل
$$K_j=\mathbb F_2[x]/(g_j(x))$$
لدينا \(x^m=1\)، ومن ثم \(x^{-1}=x^{m-1}\). لذلك يصبح المضروب المحلي
$$\lambda_j=x+x^{-1}=x+x^{m-1}\pmod{g_j}.$$
وهنا تظهر ثلاث حالات.
إذا كان \(\lambda_j=0\)، فإن الرفع إلى العامل المكرر يجعل المؤثر nilpotent، ولذلك لا يساهم إلا بالفترة \(1\).
إذا كان \(\lambda_j=1\)، فإن الجزء شبه البسيط يكون تافهًا، ولا تظهر بعد الرفع إلا قوى العدد \(2\).
أما إذا كان \(\lambda_j\neq 0,1\)، فإن \(\lambda_j\) عنصر في \(K_j^\times\) وله رتبة ضربية \(r_j\).
وتحسب التطبيقات \(r_j\) بالبحث أولًا عن أصغر \(e_j\) يحقق
$$\lambda_j^{2^{e_j}}=\lambda_j.$$
وهذا يعني أن \(\lambda_j\) يقع داخل الحقل الجزئي \(\mathbb F_{2^{e_j}}\)، وبالتالي
$$r_j\mid 2^{e_j}-1.$$
ثم يبدأ التنفيذ من العدد \(2^{e_j}-1\)، ويزيل عوامله الأولية واحدًا بعد آخر متى بقي اختبار القوة يعطي \(1\). وما يتبقى في النهاية هو الرتبة الضربية الحقيقية.
نرجع الآن إلى الحلقة المحلية \(\mathbb F_2[x]/(g_j^{2^k})\). إذا كان \(\lambda_j\neq 0\)، فيمكن كتابة المضروب المرفوع على الصورة
$$\lambda_j(1+u),\qquad u^{2^k}=0,$$
حيث ينتمي \(u\) إلى الجزء nilpotent الناتج من العامل المكرر \(g_j^{2^k}\). وبسبب أن الخاصية هي \(2\)، فإن
$$ (1+u)^{2^s}=1+u^{2^s}. $$
إذًا لا يضيف الجزء nilpotent إلا قوى للعدد \(2\). ومع تغيّر عمق الحالة داخل الترشيح \(g_j\)-adic، يمكن أن يظهر كل عامل \(2^s\) مع \(0\le s\le k\) إذا كان الجزء شبه البسيط غير تافه، وكل \(2^s\) مع \(1\le s\le k\) إذا كان الجزء شبه البسيط مساويًا لـ \(1\).
ومن ثم تكون الخيارات المحلية للفترات
$$ \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} $$
أما الـ \(1\) في البداية فهو يعبّر عن اختيار حالة محلية ذات جزء دوري تافه.
بما أن العوامل المحلية مستقلة، فإن مجموعة الفترات الكاملة لهذا الحجم من الدائرة هي
$$\mathcal P(n)=\left\{\operatorname{lcm}(u_1,\dots,u_r):u_j\in\mathcal O_j\right\}.$$
وهذه الصيغة تختصر الخوارزمية كلها: حلّل \(x^m+1\)، واحسب مجموعة خيارات محلية لكل عامل غير قابل للاختزال، ثم خذ الإغلاق تحت المضاعف المشترك الأصغر.
عندما \(n=5\)، يكون \(k=0\)، ولدينا
$$x^5+1=(x+1)(x^4+x^3+x^2+x+1).$$
على العامل \(x+1\) نضع \(x=1\)، فنحصل على \(\lambda=1+1=0\)، ولذلك لا يساهم هذا الفرع إلا بـ \(1\).
أما على العامل من الدرجة الرابعة، فلتكن \(\alpha\) جذرًا له. بما أن \(\alpha^5=1\)، فإن
$$\lambda=\alpha+\alpha^4.$$
وباستخدام \(1+\alpha+\alpha^2+\alpha^3+\alpha^4=0\) نحصل على
$$\lambda^2+\lambda+1=\alpha^2+\alpha^3+\alpha+\alpha^4+1=0,$$
ومن ثم تكون رتبة \(\lambda\) مساوية لـ \(3\). ولأن \(k=0\)، فإن العامل الثاني يساهم بـ \(\{1,3\}\)، وبالتالي
$$\mathcal P(5)=\{1,3\}.$$
وعندما \(n=6\)، يكون \(n=2\cdot 3\)، أي \(k=1\)، و
$$x^3+1=(x+1)(x^2+x+1).$$
العامل الخطي يعطي مرة أخرى \(\lambda=0\). وفي العامل التربيعي، من \(x^2+x+1=0\) نستنتج \(x^2=x+1\)، ومن ثم
$$\lambda=x+x^2=1.$$
فتكون الفترات المحلية هي \(1\) و\(2\)، وبالتالي
$$\mathcal P(6)=\{1,2\}.$$
بعد حساب \(\mathcal P(n)\) لكل \(3\le n\le N\)، تُضاف جميع الفترات إلى مجموعة عالمية واحدة
$$\mathcal G(N)=\bigcup_{n=3}^{N}\mathcal P(n),$$
ثم يكون الجواب النهائي
$$S(N)=\sum_{v\in\mathcal G(N)} v.$$
ولهذا يهتم البرنامج فقط بالفترات المختلفة التي تظهر، لا بعدد الحالات التي تحقق كل فترة.
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تبدأ بتوليد أعداد أولية عادية تكفي لتحليل الأعداد من الشكل \(2^e-1\) التي تظهر في خطوة اختزال الرتب.
بعد ذلك تُنفذ حسابات كثيرات الحدود فوق \(\mathbb F_2\): الدرجة، والباقي، والقسمة، والقاسم المشترك الأكبر، والضرب modulo كثير حدود، والرفع السريع للأس. وباستخدام هذه الأدوات يطبَّق تحليل Berlekamp على \(x^m+1\) لكل جزء فردي \(m\).
ولكل عامل غير قابل للاختزال، يحسب التنفيذ المضروب المحلي \(x+x^{m-1}\)، ويفصل حالتي \(0\) و\(1\)، وفي غير ذلك يحسب الرتبة الضربية باستعمال مربعات فروبينيوس المتتالية ثم اختزال القواسم داخل \(2^e-1\).
ثم تُحوَّل هذه الرتب المحلية إلى مجموعات الخيارات \(\mathcal O_j\)، ويُبنى منها \(\mathcal P(n)\) بتمرير تكراري يأخذ الإغلاق تحت المضاعف المشترك الأصغر. كما تُخزَّن بيانات الرتب بحسب الجزء الفردي \(m\)، بحيث تعيد الأحجام \(m,2m,4m,\dots\) استعمال التحليل الحقلي نفسه، ولا يختلف بينها إلا مدى الرفع بقوى \(2\).
وفي النهاية تأخذ التطبيقات اتحاد جميع مجموعات الفترات من \(3\le n\le N\) ثم تجمع القيم المختلفة. والقيم المرجعية \(\mathcal P(5)=\{1,3\}\)، و\(\mathcal P(6)=\{1,2\}\)، و\(S(30)=20381\) تتوافق تمامًا مع الاشتقاق الرياضي السابق.
لتكن \(U=\{m\le N:m\text{ odd}\}\). كل جزء فردي يُحلل مرة واحدة فقط، لذلك فإن العمل الجبري المسيطر هو مجموع تحليل \(x^m+1\) فوق \(\mathbb F_2\) لكل \(m\in U\). وفي هذا التنفيذ المباشر تكون الجبر الخطي في خوارزمية Berlekamp من رتبة تكعيبية في \(m\) إذا تجاهلنا تفاصيل عمليات البت، وهو أمر صغير جدًا عندما \(N=100\).
وبعد معرفة العوامل، فإن حساب الرتبة لعامل درجته \(d\) يستخدم التربيع المتكرر داخل الحقل واختبارات على قواسم \(2^e-1\) حيث \(e\le d\). أما بناء مجموعة الفترات فهو أقرب إلى عمل تركيبي: فإذا كانت أحجام المجموعات المحلية \(|\mathcal O_1|,\dots,|\mathcal O_r|\)، فإن تكلفة تكوين \(\mathcal P(n)\) تأتي من الإغلاق التكراري تحت المضاعف المشترك الأصغر الناتج عن هذه الاختيارات.
استهلاك الذاكرة محدود. فالبرنامج يحتفظ بقوائم الرتب المخزنة للأجزاء الفردية التي عولجت من قبل، وبيانات متعددة حدود مؤقتة لتحليل واحد، ومجموعة الفترات الحالية لقيمة \(n\) معينة، ثم المجموعة العالمية النهائية للفترات المختلفة.