For every pair of distinct positive squares \(a^2 \lt b^2\), Peter toggles door \(n=a^2+b^2\), provided \(n\le N\). After all actions, door \(n\) remains open exactly when the number of strict representations
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
is odd. Therefore
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
The real input is \(N=10^{12}\), so enumerating all square pairs is far too slow. The implementation instead turns the problem into a classification of prime exponents.
The central object is the classical sum-of-two-squares counting function over all signs and orders.
Let
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
Every strict positive representation \(a \lt b\) generates eight ordered signed solutions: \((\pm a,\pm b)\) and \((\pm b,\pm a)\). Two degenerate situations contribute only four solutions:
$$n=c^2 \quad \text{gives} \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \text{gives} \quad (\pm c,\pm c).$$
So if we define
$$s(n)= \begin{cases} 1,&\text{if } n \text{ is a square or twice a square},\\ 0,&\text{otherwise}, \end{cases}$$
then
$$r_2(n)=8u(n)+4s(n),$$
hence
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
This identity is the bridge from door toggling to arithmetic parity.
Write the factorization of \(n\) as
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
If any prime \(q\equiv 3 \pmod 4\) has odd exponent, then \(n\) is not representable as a sum of two squares at all, so \(r_2(n)=0\) and \(u(n)\) is even. The only interesting numbers are therefore
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$$
For such \(n\), the standard formula becomes
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Define
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Then the parity condition is simply
$$R(n)=2u(n)+s(n).$$
So the question becomes: for which exponent patterns is \((R(n)-s(n))/2\) odd?
First assume \(s(n)=0\), meaning \(n\) is neither a square nor twice a square. Then \(u(n)\) is odd exactly when
$$R(n)\equiv 2 \pmod 4.$$
Because each factor \(\alpha_p+1\) is odd when \(\alpha_p\) is even and even when \(\alpha_p\) is odd, the product can be \(2 \pmod 4\) only when exactly one factor contributes a single power of \(2\) and every other factor remains odd. So there must be exactly one prime \(p\equiv 1 \pmod 4\) with odd exponent, and that exponent must satisfy
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$$
Therefore the non-degenerate doors that remain open are exactly those of the form
$$n=p^{4t+1}m^2 \quad \text{or} \quad n=2p^{4t+1}m^2,$$
where \(p\equiv 1 \pmod 4\) and \(p\nmid m\). This is the first family counted by the implementation.
Now assume \(s(n)=1\). That means every exponent \(\alpha_p\) is even, so \(n\) is either a square or twice a square. We can write it uniquely as
$$n=2^a m^2,\qquad m \text{ odd}.$$
Since \(u(n)\) is odd exactly when
$$R(n)\equiv 3 \pmod 4,$$
we inspect each factor with \(\alpha_p=2\delta_p\). Then
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ even},\\ 3 \pmod 4,&\delta_p \text{ odd}. \end{cases}$$
So \(R(n)\equiv 3 \pmod 4\) exactly when an odd number of primes \(p\equiv 1 \pmod 4\) occur to odd exponent in the odd square root \(m\). That produces the second family:
$$n=2^a m^2,\qquad m \text{ odd},$$
with the parity filter “the number of primes \(p\equiv 1 \pmod 4\) occurring to odd exponent in \(m\) is odd.”
Let \(\pi_1(x)\) denote the number of primes \(p\le x\) with \(p\equiv 1 \pmod 4\). For the even-\(2\)-adic half of family A, we count numbers
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
For the first exponent layer \(p^1\), the contribution of one prime is
$$\#\{m : p m^2\le N,\ p\nmid m\}=\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$$
The first term is grouped by equal square-root quotients:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
The subtraction by \(\left\lfloor\sqrt{N/p^3}\right\rfloor\) removes the forbidden choices where the square part already contains \(p\). Higher valid exponents \(p^5,p^9,\dots\) are sparse, so they are added directly through
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$$
If \(v_2(n)\) is odd, then \(n\) belongs to the second variant \(2p^{4t+1}m^2\). Multiplying by \(2\) gives a bijection with the even-\(v_2\) case at bound \(N/2\), so the same routine can be reused with \(N\) replaced by \(N/2\).
For family B, every valid odd \(m\le \sqrt{N}\) contributes all numbers
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$$
The number of admissible powers of \(2\) is
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
So the remaining work is to know, for each odd \(m\), whether the count of primes \(p\equiv 1 \pmod 4\) appearing to odd exponent is odd or even.
The checkpoint \(F(100)=27\) follows cleanly from the classification.
Family A with even \(v_2\) gives
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
so there are \(16\) such doors.
Family A with odd \(v_2\) is obtained by doubling the even-\(v_2\) doors up to \(50\), namely
$$10,26,34,40,58,74,82,90,$$
which contributes \(8\) more doors.
For family B, the odd candidates \(m\le 10\) are \(1,3,5,7,9\). Only \(m=5\) has an odd number of \(1 \pmod 4\) primes occurring to odd exponent, so it contributes
$$25,\ 50,\ 100,$$
hence \(3\) more doors. Therefore
$$F(100)=16+8+3=27.$$
The C++, Python, and Java implementations all follow the same arithmetic decomposition. The Python entry point is only a thin wrapper around that same numerical strategy, so the mathematics is identical across languages.
The implementation first builds a prime-counting structure over the quotient values \(\lfloor N/i\rfloor\). It stores both the ordinary prime count \(\pi(x)\) and a weighted prime sum using the Dirichlet character
$$\chi_4(n)= \begin{cases} 0,&n \text{ even},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
From these two tables it recovers
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$$
which is exactly the count of primes \(p\le x\) with \(p\equiv 1 \pmod 4\).
With that tool in place, the implementation counts family A in three pieces: the grouped \(p^1\) layer, the correction that subtracts roots already divisible by the chosen prime, and the direct enumeration of the sparse higher layers \(p^5,p^9,\dots\). It then reuses the same routine at \(N/2\) to count the odd-\(v_2\) branch.
For family B, the implementation precomputes smallest prime factors up to \(\lfloor\sqrt{N}\rfloor\). Factoring each odd \(m\) reveals whether the number of primes \(p\equiv 1 \pmod 4\) occurring to odd exponent is odd. Whenever the parity condition holds, it adds
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
to the answer.
Finally, the implementation adds the even-\(v_2\) branch of family A, the corresponding odd-\(v_2\) branch obtained from the \(N/2\) bijection, and the family-B contribution.
Let \(M=\lfloor\sqrt{N}\rfloor\). The smallest-prime-factor sieve and the parity table for odd \(m\) cost \(O(M\log\log M)\) time and \(O(M)\) memory. The family-B scan is linear in \(M\). The higher-power part of family A is very small because \(p^5\) already grows quickly.
The dominant work is the quotient-class prime-counting structure used to answer many values of \(\pi_1(x)\) efficiently. It stores \(O(M)\) quotient values and keeps the overall method practical for \(N=10^{12}\). So the implementation uses \(O(M)\) memory, and the runtime is dominated by the prime-counting preprocessing plus the linear-in-\(M\) auxiliary passes.
Für jedes Paar verschiedener positiver Quadrate \(a^2 \lt b^2\) toggelt Peter die Tür \(n=a^2+b^2\), sofern \(n\le N\) ist. Nach allen Aktionen bleibt Tür \(n\) genau dann offen, wenn die Anzahl der strikten Darstellungen
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
ungerade ist. Also gilt
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
Für \(N=10^{12}\) ist direktes Durchprobieren aller Quadrate viel zu teuer. Die Lösung reduziert das Problem daher auf eine Klassifikation der Primexponenten.
Der Ausgangspunkt ist die klassische Funktion, die alle Darstellungen als Summe zweier Quadrate mit Vorzeichen und Reihenfolge mitzählt.
Sei
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
Jede strikte positive Darstellung \(a \lt b\) erzeugt acht geordnete Lösungen mit Vorzeichen. Zwei entartete Fälle liefern dagegen nur vier Lösungen:
$$n=c^2 \quad \text{liefert} \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \text{liefert} \quad (\pm c,\pm c).$$
Definiert man
$$s(n)= \begin{cases} 1,&\text{falls } n \text{ ein Quadrat oder das Doppelte eines Quadrats ist},\\ 0,&\text{sonst}, \end{cases}$$
dann gilt
$$r_2(n)=8u(n)+4s(n),$$
also
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
Genau diese Gleichung verbindet die Türfrage mit Zahlentheorie.
Schreibe
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
Hat ein Primfaktor \(q\equiv 3 \pmod 4\) einen ungeraden Exponenten, dann ist \(n\) gar nicht als Summe zweier Quadrate darstellbar. Interessant sind also nur Zahlen der Form
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$$
Für solche \(n\) lautet die Standardformel
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Setzen wir
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
dann wird die Paritätsfrage zu
$$R(n)=2u(n)+s(n).$$
Zunächst sei \(s(n)=0\), also \(n\) weder Quadrat noch Doppelquadrat. Dann ist \(u(n)\) genau dann ungerade, wenn
$$R(n)\equiv 2 \pmod 4.$$
Da \(\alpha_p+1\) genau dann gerade ist, wenn \(\alpha_p\) ungerade ist, kann das Produkt nur dann \(2 \pmod 4\) sein, wenn es genau einen ungeraden Exponenten gibt und dieser zusätzlich
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4$$
erfüllt. Damit erhält man exakt die Zahlen
$$n=p^{4t+1}m^2 \quad \text{oder} \quad n=2p^{4t+1}m^2,$$
wobei \(p\equiv 1 \pmod 4\) und \(p\nmid m\). Das ist Familie A der Implementierung.
Nun sei \(s(n)=1\). Dann sind alle Exponenten \(\alpha_p\) gerade, also ist \(n\) ein Quadrat oder das Doppelte eines Quadrats. Eindeutig schreiben wir
$$n=2^a m^2,\qquad m \text{ ungerade}.$$
Hier ist \(u(n)\) genau dann ungerade, wenn
$$R(n)\equiv 3 \pmod 4.$$
Schreibt man \(\alpha_p=2\delta_p\), so gilt
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ gerade},\\ 3 \pmod 4,&\delta_p \text{ ungerade}. \end{cases}$$
Daher ist \(R(n)\equiv 3 \pmod 4\) genau dann, wenn im ungeraden Quadratwurzelfaktor \(m\) eine ungerade Anzahl von Primzahlen \(p\equiv 1 \pmod 4\) zu ungeradem Exponenten vorkommt. Das ist Familie B:
$$n=2^a m^2,\qquad m \text{ ungerade},$$
mit genau diesem Paritätsfilter auf \(m\).
Sei \(\pi_1(x)\) die Anzahl der Primzahlen \(p\le x\) mit \(p\equiv 1 \pmod 4\). Für den Teil von Familie A mit geradem \(2\)-Adischem Exponenten zählen wir
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
Für die erste Exponentenlage \(p^1\) trägt ein fixes \(p\) genau
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor$$
bei. Der erste Term wird nach gleichen Quotienten gruppiert:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
Die Subtraktion entfernt genau die verbotenen Fälle, in denen \(p\) bereits in \(m^2\) steckt. Die höheren gültigen Exponenten \(p^5,p^9,\dots\) sind selten und werden direkt über
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1$$
addiert. Der Zweig mit ungeradem \(v_2(n)\) ist per Multiplikation mit \(2\) bijektiv zum geraden Zweig bei Schranke \(N/2\).
Für Familie B liefert jedes zulässige ungerade \(m\le \sqrt{N}\) alle Zahlen
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$$
Die Anzahl der erlaubten Zweierpotenzen ist
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
Man muss also nur für jedes ungerade \(m\) die genannte Parität der \(1 \pmod 4\)-Primfaktoren kennen.
Der Kontrollwert \(F(100)=27\) folgt direkt aus den beiden Familien.
Familie A mit geradem \(v_2\) ergibt
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
also \(16\) Türen.
Familie A mit ungeradem \(v_2\) erhält man durch Verdopplung des geraden Falls bis \(50\), also
$$10,26,34,40,58,74,82,90,$$
das sind weitere \(8\) Türen.
Für Familie B sind die ungeraden Kandidaten \(m\le 10\) gleich \(1,3,5,7,9\). Nur \(m=5\) erfüllt den Paritätsfilter und liefert
$$25,\ 50,\ 100,$$
also \(3\) weitere Türen. Insgesamt damit
$$F(100)=16+8+3=27.$$
Die Implementierungen in C++, Python und Java folgen alle derselben arithmetischen Zerlegung. Der Python-Einstiegspunkt ist nur eine schlanke Hülle um dieselbe numerische Strategie, sodass die Mathematik in allen drei Sprachen identisch bleibt.
Zuerst baut die Implementierung eine Primzahl-Zählstruktur über den Quotientenwerten \(\lfloor N/i\rfloor\) auf. Gespeichert werden sowohl \(\pi(x)\) als auch eine gewichtete Primzahlsumme mit dem Dirichlet-Charakter
$$\chi_4(n)= \begin{cases} 0,&n \text{ gerade},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
Daraus wird
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2}$$
rekonstruiert, also die Anzahl der Primzahlen \(p\le x\) mit \(p\equiv 1 \pmod 4\).
Mit dieser Funktion zählt die Implementierung Familie A in drei Teilen: in der gebündelten \(p^1\)-Schicht, in dem Korrekturterm für Quadratanteile, die den gewählten Primfaktor schon enthalten, und anschließend in den dünnen höheren Schichten \(p^5,p^9,\dots\). Für den Zweig mit ungeradem \(v_2\) wird dieselbe Routine bei \(N/2\) wiederverwendet.
Für Familie B wird bis \(\lfloor\sqrt{N}\rfloor\) eine Tabelle kleinster Primfaktoren aufgebaut. Damit lässt sich jedes ungerade \(m\) faktorisieren und die Parität der \(1 \pmod 4\)-Primfaktoren mit ungeradem Exponenten bestimmen. Falls die Bedingung erfüllt ist, addiert die Implementierung
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
zum Ergebnis. Am Ende addiert die Implementierung den geraden \(v_2\)-Zweig von Familie A, den über die \(N/2\)-Bijektion gewonnenen ungeraden \(v_2\)-Zweig und schließlich den Beitrag von Familie B.
Sei \(M=\lfloor\sqrt{N}\rfloor\). Das SPF-Sieb und die Paritätstabelle für ungerade \(m\) benötigen \(O(M\log\log M)\) Zeit und \(O(M)\) Speicher. Der Durchlauf für Familie B ist linear in \(M\). Der Teil mit höheren Potenzen in Familie A ist klein, weil \(p^5\) sehr schnell wächst.
Die Hauptarbeit steckt in der Primzahl-Zählstruktur auf Quotientenklassen, die viele Werte von \(\pi_1(x)\) effizient verfügbar macht. Sie speichert \(O(M)\) Werte und hält das Verfahren auch für \(N=10^{12}\) praktikabel. Insgesamt ist der Speicherverbrauch \(O(M)\), und die Laufzeit wird von dieser Vorverarbeitung plus den linearen Hilfsdurchläufen dominiert.
Peter, her farklı pozitif kare çifti \(a^2 \lt b^2\) için, eğer \(n=a^2+b^2\le N\) ise \(n\) numaralı kapının durumunu değiştirir. Tüm adımlar tamamlandıktan sonra \(n\) kapısı ancak ve ancak
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
sayısı tek ise açık kalır. Dolayısıyla
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}$$
hesaplanmalıdır. Gerçek sınır \(N=10^{12}\) olduğu için kare çiftlerini doğrudan taramak mümkün değildir. Çözüm, problemi asal üslerinin paritesine indirger.
Ana araç, işaret ve sıra dahil tüm iki-kare-toplamı gösterimlerini sayan klasik fonksiyondur.
Şunu tanımlayalım:
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
Her sıkı pozitif temsil \(a \lt b\), işaret ve sıra sayesinde sekiz çözüm üretir. Yalnız iki dejenere durum sadece dört çözüm verir:
$$n=c^2 \quad \text{için} \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \text{için} \quad (\pm c,\pm c).$$
Bu yüzden
$$s(n)= \begin{cases} 1,&\text{eğer } n \text{ bir kare veya bir karenin iki katı ise},\\ 0,&\text{aksi halde} \end{cases}$$
tanımıyla
$$r_2(n)=8u(n)+4s(n)$$
ve dolayısıyla
$$\frac{r_2(n)}{4}=2u(n)+s(n)$$
elde edilir. Pariteyi belirleyen temel köprü budur.
\(n\)'yi
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}$$
şeklinde ayıralım. Eğer \(q\equiv 3 \pmod 4\) olan bir asal tek üs ile gelirse, \(n\) iki karenin toplamı olarak hiç yazılamaz; o zaman \(r_2(n)=0\) ve \(u(n)\) çifttir. Bu yüzden gerçekten önemli sayılar
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}$$
biçimindedir. Bu durumda klasik formül
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1)$$
olur. Şimdi
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1)$$
dersek, parite koşulu
$$R(n)=2u(n)+s(n)$$
haline gelir.
Önce \(s(n)=0\) olsun; yani \(n\) ne kare ne de iki kat kare olsun. Bu durumda \(u(n)\) tek olması için ve ancak için
$$R(n)\equiv 2 \pmod 4$$
gerekir. \(\alpha_p+1\), yalnızca \(\alpha_p\) tek olduğunda çift olur. Çarpımın \(2 \pmod 4\) olabilmesi için tek üs taşıyan tam olarak bir adet \(p\equiv 1 \pmod 4\) asalı bulunmalıdır ve onun da
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4$$
koşulunu sağlaması gerekir. Böylece kapılar tam olarak şu biçimdedir:
$$n=p^{4t+1}m^2 \quad \text{veya} \quad n=2p^{4t+1}m^2,$$
burada \(p\equiv 1 \pmod 4\) ve \(p\nmid m\). Bu, kodun saydığı ilk ailedir.
Şimdi \(s(n)=1\) olsun. Bu, tüm \(\alpha_p\) üslerinin çift olduğu ve \(n\)'nin ya kare ya da bir karenin iki katı olduğu anlamına gelir. Sayıyı tekil biçimde
$$n=2^a m^2,\qquad m \text{ tek}$$
şeklinde yazarız. Bu kez \(u(n)\) tek olması için
$$R(n)\equiv 3 \pmod 4$$
gerekir. \(\alpha_p=2\delta_p\) yazarsak
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ çift},\\ 3 \pmod 4,&\delta_p \text{ tek} \end{cases}$$
olur. Yani \(R(n)\equiv 3 \pmod 4\) tam olarak, tek karekök parçası \(m\) içinde \(p\equiv 1 \pmod 4\) olan asallardan tek üs ile gelenlerin sayısı tek olduğunda gerçekleşir. İkinci aile budur:
$$n=2^a m^2,\qquad m \text{ tek},$$
ve \(m\) için yukarıdaki parite filtresi uygulanır.
\(\pi_1(x)\), \(x\)'e kadar olan ve \(1 \pmod 4\) sınıfındaki asal sayısı olsun. Ailesi A'nın çift \(2\)-adik kısmında şu sayılar sayılır:
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
İlk katman \(p^1\) için sabit bir \(p\)'nin katkısı
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor$$
olur. İlk terim, aynı karekök bölümlerine göre gruplanır:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
İkinci terim, kare parçası içinde zaten \(p\) bulunan yasak seçimleri çıkarır. Daha yüksek geçerli üsler \(p^5,p^9,\dots\) seyrektir; bunlar doğrudan
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1$$
ile eklenir. \(v_2(n)\) tek olan kol ise \(n \mapsto 2n\) eşlemesi sayesinde \(N/2\) sınırındaki çift kola indirgenir.
Ailesi B'de uygun her tek \(m\le \sqrt{N}\),
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N$$
saylarının tümünü üretir. İzin verilen iki kuvveti sayısı
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
kadardır. Böylece geriye sadece, her tek \(m\) için ilgili \(1 \pmod 4\) asallarının paritesini belirlemek kalır.
Kontrol değeri olan \(F(100)=27\), sınıflandırmadan doğrudan çıkar.
Ailesi A'nın çift \(v_2\) kısmı
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97$$
kapılarını verir; toplam \(16\) kapı.
Tek \(v_2\) kolu, \(50\)'ye kadarki çift kolun ikiyle çarpılmasıdır:
$$10,26,34,40,58,74,82,90,$$
yani \(8\) kapı daha.
Ailesi B için \(m\le 10\) olan tek adaylar \(1,3,5,7,9\)'dur. Bunlardan sadece \(m=5\) parite koşulunu sağlar ve
$$25,\ 50,\ 100$$
değerlerini üretir; yani \(3\) kapı. Sonuç olarak
$$F(100)=16+8+3=27.$$
C++, Python ve Java implementasyonlarının üçü de aynı aritmetik ayrıştırmayı kullanır. Python tarafı yalnızca aynı sayısal stratejinin ince bir sarmalayıcısıdır; dolayısıyla üç dilde de uygulanan matematik aynıdır.
İlk olarak, \(\lfloor N/i\rfloor\) bölüm sınıfları üzerinde çalışan bir asal sayma yapısı kurulur. Bu yapı hem \(\pi(x)\) değerlerini hem de Dirichlet karakteriyle ağırlıklandırılmış asal toplamını saklar:
$$\chi_4(n)= \begin{cases} 0,&n \text{ çift},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
Böylece
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2}$$
hesaplanır; bu da \(x\)'e kadarki \(1 \pmod 4\) asallarını verir.
Daha sonra implementasyon, ailesi A'yı üç parçada toplar: gruplanmış \(p^1\) katmanı, seçilen asalın kare parçasında zaten bulunduğu durumları çıkaran düzeltme terimi ve seyrek \(p^5,p^9,\dots\) katmanlarının doğrudan sayımı. Tek \(v_2\) kolu için aynı işlem \(N/2\) üzerinde tekrar kullanılır.
Ailesi B tarafında \(\lfloor\sqrt{N}\rfloor\)'ye kadar en küçük asal bölen tablosu hazırlanır. Her tek \(m\) bu tabloyla çarpanlarına ayrılır ve \(1 \pmod 4\) asalların tek üs ile geliş sayısının paritesi belirlenir. Koşul sağlanıyorsa
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
cevaba eklenir. Son aşamada implementasyon, ailesi A'nın çift \(v_2\) kolunu, \(N/2\) eşlemesiyle elde edilen tek \(v_2\) kolunu ve ailesi B'nin katkısını toplayarak cevabı oluşturur.
\(M=\lfloor\sqrt{N}\rfloor\) olsun. En küçük asal bölen süzgeci ve tek \(m\) değerleri için parite tablosu \(O(M\log\log M)\) zaman ve \(O(M)\) bellek kullanır. Ailesi B taraması \(M\) üzerinde lineerdir. Ailesi A'nın yüksek üs kısmı ise \(p^5\) çok hızlı büyüdüğü için küçüktür.
Baskın maliyet, çok sayıda \(\pi_1(x)\) sorgusunu verimli hale getiren bölüm-sınıfı asal sayma yapısıdır. Bu yapı \(O(M)\) adet değer saklar ve yöntemi \(N=10^{12}\) için pratik tutar. Toplam bellek \(O(M)\), çalışma süresi ise bu asal sayma ön işlemi ile lineer yardımcı geçişler tarafından belirlenir.
Para cada par de cuadrados positivos distintos \(a^2 \lt b^2\), Peter conmuta la puerta \(n=a^2+b^2\), siempre que \(n\le N\). Al final, la puerta \(n\) queda abierta exactamente cuando el número de representaciones estrictas
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
es impar. Por tanto,
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
Como el valor real es \(N=10^{12}\), no se pueden enumerar directamente todos los pares de cuadrados. La solución convierte el problema en una clasificación de exponentes primos.
El objeto clave es la función clásica que cuenta todas las representaciones como suma de dos cuadrados, incluyendo signos y orden.
Definimos
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
Cada representación estricta positiva \(a \lt b\) produce ocho soluciones con signo y orden. Solo hay dos casos degenerados que aportan cuatro soluciones:
$$n=c^2 \quad \text{da} \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \text{da} \quad (\pm c,\pm c).$$
Si definimos
$$s(n)= \begin{cases} 1,&\text{si } n \text{ es un cuadrado o el doble de un cuadrado},\\ 0,&\text{en otro caso}, \end{cases}$$
entonces
$$r_2(n)=8u(n)+4s(n),$$
y por tanto
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
Esa es la identidad que transforma el problema de las puertas en un problema de paridad aritmética.
Escribimos
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
Si algún primo \(q\equiv 3 \pmod 4\) aparece con exponente impar, entonces \(n\) no es suma de dos cuadrados y \(u(n)\) es par. Por eso solo importan los números de la forma
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$$
Para ellos, la fórmula estándar dice
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Definamos
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Entonces la condición de paridad se convierte en
$$R(n)=2u(n)+s(n).$$
Supongamos primero que \(s(n)=0\), es decir, que \(n\) no es ni cuadrado ni doble-cuadrado. Entonces \(u(n)\) es impar si y solo si
$$R(n)\equiv 2 \pmod 4.$$
Cada factor \(\alpha_p+1\) es par exactamente cuando \(\alpha_p\) es impar. Para que el producto sea \(2 \pmod 4\), debe existir exactamente un primo \(p\equiv 1 \pmod 4\) con exponente impar, y además ese exponente debe cumplir
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$$
Por tanto, los números abiertos en este caso son exactamente
$$n=p^{4t+1}m^2 \quad \text{o} \quad n=2p^{4t+1}m^2,$$
con \(p\equiv 1 \pmod 4\) y \(p\nmid m\). Esa es la familia A de la implementación.
Ahora supongamos que \(s(n)=1\). Eso significa que todos los exponentes \(\alpha_p\) son pares, así que \(n\) es un cuadrado o el doble de un cuadrado. Puede escribirse de manera única como
$$n=2^a m^2,\qquad m \text{ impar}.$$
En este caso \(u(n)\) es impar exactamente cuando
$$R(n)\equiv 3 \pmod 4.$$
Si \(\alpha_p=2\delta_p\), entonces
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ par},\\ 3 \pmod 4,&\delta_p \text{ impar}. \end{cases}$$
Así, \(R(n)\equiv 3 \pmod 4\) exactamente cuando en la raíz cuadrada impar \(m\) aparece un número impar de primos \(p\equiv 1 \pmod 4\) con exponente impar. Eso produce la familia B:
$$n=2^a m^2,\qquad m \text{ impar},$$
junto con ese filtro de paridad sobre \(m\).
Sea \(\pi_1(x)\) el número de primos \(p\le x\) tales que \(p\equiv 1 \pmod 4\). Para la mitad con \(v_2(n)\) par, contamos
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
En la primera capa \(p^1\), la contribución de un primo fijo es
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$$
El primer término se reescribe agrupando valores iguales del cociente cuadrático:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
La resta elimina exactamente los casos prohibidos en los que el factor cuadrado ya contiene a \(p\). Las potencias válidas superiores \(p^5,p^9,\dots\) son muy escasas y se añaden directamente con
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$$
La rama con \(v_2(n)\) impar se obtiene por la biyección \(n\mapsto 2n\), así que basta repetir el mismo conteo con cota \(N/2\).
En la familia B, cada \(m\) impar válido con \(m\le \sqrt{N}\) genera
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$$
El número de exponentes admisibles de \(2\) es
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
Por tanto, solo hace falta saber para cada \(m\) impar si el número de primos \(1 \pmod 4\) que aparecen con exponente impar es impar o par.
El valor de control \(F(100)=27\) sale directamente de la clasificación.
La familia A con \(v_2\) par produce
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
es decir, \(16\) puertas.
La familia A con \(v_2\) impar se obtiene duplicando la rama par hasta \(50\):
$$10,26,34,40,58,74,82,90,$$
lo que aporta \(8\) puertas más.
Para la familia B, los candidatos impares \(m\le 10\) son \(1,3,5,7,9\). Solo \(m=5\) cumple el filtro de paridad, y entonces aporta
$$25,\ 50,\ 100,$$
o sea \(3\) puertas adicionales. En total,
$$F(100)=16+8+3=27.$$
Las implementaciones en C++, Python y Java siguen la misma descomposición aritmética. La versión de Python es solo una envoltura ligera alrededor de esa misma estrategia numérica, así que la matemática es la misma en los tres lenguajes.
Primero, la implementación construye una estructura de conteo de primos sobre los valores cociente \(\lfloor N/i\rfloor\). En ella guarda tanto \(\pi(x)\) como una suma ponderada de primos con el carácter de Dirichlet
$$\chi_4(n)= \begin{cases} 0,&n \text{ par},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
Con ambas tablas recupera
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$$
que es el conteo de primos \(p\le x\) con \(p\equiv 1 \pmod 4\).
Después, la implementación cuenta la familia A en tres partes: la capa agrupada \(p^1\), el término de corrección que elimina raíces cuyo factor cuadrado ya contiene el primo elegido, y la enumeración directa de las capas finas \(p^5,p^9,\dots\). La rama con \(v_2\) impar reutiliza exactamente la misma rutina sobre \(N/2\).
Para la familia B, se precalculan factores primos mínimos hasta \(\lfloor\sqrt{N}\rfloor\). Eso permite factorizar cada \(m\) impar y decidir si el número de primos \(1 \pmod 4\) que aparecen con exponente impar es impar. Cuando la condición se cumple, se suma
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
al total. Al final, la implementación suma la rama de la familia A con \(v_2\) par, la rama correspondiente con \(v_2\) impar obtenida a partir de la biyección con \(N/2\), y la contribución total de la familia B.
Sea \(M=\lfloor\sqrt{N}\rfloor\). La criba SPF y la tabla de paridad para los \(m\) impares cuestan \(O(M\log\log M)\) tiempo y \(O(M)\) memoria. El recorrido de la familia B es lineal en \(M\). La parte de exponentes altos de la familia A es pequeña porque \(p^5\) crece muy deprisa.
El coste dominante está en la estructura de conteo de primos por clases de cociente, que hace eficientes las numerosas consultas de \(\pi_1(x)\). Dicha estructura almacena \(O(M)\) valores y mantiene el método práctico incluso para \(N=10^{12}\). En conjunto, la memoria es \(O(M)\) y el tiempo está dominado por esa precomputación de conteo de primos más los recorridos auxiliares lineales.
对每一对不同的正平方数 \(a^2 \lt b^2\)，Peter 都会翻转编号为 \(n=a^2+b^2\) 的门，只要 \(n\le N\)。所有操作结束后，门 \(n\) 是否开启，取决于严格表示
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
的个数是否为奇数。因此要求的是
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
真实目标是 \(N=10^{12}\)，不可能直接枚举所有平方对。实现采用的做法，是先把“表示个数的奇偶性”转化为“素因子指数的结构分类”。
关键是使用经典的“两平方和表示数”公式，把题目中的门状态和整数分解联系起来。
定义
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
这里 \(r_2(n)\) 计算的是所有有序、有符号的整数解。题目中的一个严格正表示 \(a \lt b\) 会对应 8 个这样的解： \((\pm a,\pm b)\) 和 \((\pm b,\pm a)\)。但有两个退化情形只会产生 4 个解：
$$n=c^2 \quad \Rightarrow \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \Rightarrow \quad (\pm c,\pm c).$$
于是定义
$$s(n)= \begin{cases} 1,&\text{当 } n \text{ 是平方数或两倍平方数时},\\ 0,&\text{否则}, \end{cases}$$
就有
$$r_2(n)=8u(n)+4s(n),$$
从而
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
这一步非常重要，因为它把“门被翻转奇数次”转成了一个纯粹的模 \(4\) 判断问题。
把 \(n\) 分解为
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
经典定理告诉我们：如果某个 \(q\equiv 3 \pmod 4\) 的素数在 \(n\) 中出现奇次幂，那么 \(n\) 根本不能写成两个平方数之和，因此 \(r_2(n)=0\)，题目中的 \(u(n)\) 当然也是偶数。
所以真正需要考虑的，只是
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}$$
这一类数。对这些数有标准公式
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
记
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$$
那么门 \(n\) 是否打开，就由
$$R(n)=2u(n)+s(n)$$
决定。接下来只需分类什么时候 \((R(n)-s(n))/2\) 是奇数。
先看 \(s(n)=0\) 的情况，也就是 \(n\) 既不是平方数，也不是两倍平方数。这时 \(u(n)\) 为奇数，当且仅当
$$R(n)\equiv 2 \pmod 4.$$
注意：\(\alpha_p+1\) 在 \(\alpha_p\) 为偶数时是奇数，在 \(\alpha_p\) 为奇数时是偶数。一个乘积要模 \(4\) 等于 \(2\)，只能有且仅有一个因子贡献一个单独的 \(2\)，其余因子都必须是奇数。于是必须满足：
只有一个 \(p\equiv 1 \pmod 4\) 的指数 \(\alpha_p\) 为奇数，而且这个奇数指数还必须满足
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$$
因此这一类门恰好是
$$n=p^{4t+1}m^2 \quad \text{或} \quad n=2p^{4t+1}m^2,$$
其中 \(p\equiv 1 \pmod 4\)，并且 \(p\nmid m\)。这就是实现中第一大类的来源。
再看 \(s(n)=1\) 的情况。此时所有 \(\alpha_p\) 都必须是偶数，所以 \(n\) 必然是平方数或者两倍平方数。它可以唯一写成
$$n=2^a m^2,\qquad m \text{ 为奇数}.$$
现在 \(u(n)\) 为奇数，当且仅当
$$R(n)\equiv 3 \pmod 4.$$
把 \(\alpha_p\) 写成 \(2\delta_p\)，则
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ 为偶数},\\ 3 \pmod 4,&\delta_p \text{ 为奇数}. \end{cases}$$
所以 \(R(n)\equiv 3 \pmod 4\) 当且仅当在奇数平方根 \(m\) 中，满足 \(p\equiv 1 \pmod 4\) 且指数为奇数的素数个数是奇数。于是第二类可以描述为
$$n=2^a m^2,\qquad m \text{ 为奇数},$$
并且 \(m\) 要通过上面的奇偶性筛选。
设 \(\pi_1(x)\) 表示不超过 \(x\) 且满足 \(p\equiv 1 \pmod 4\) 的素数个数。对家族 A 中 \(2\)-进指数为偶数的那一半，需要统计
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
先看最薄的一层 \(p^1\)。固定一个素数 \(p\) 时，满足条件的 \(m\) 个数是
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$$
第一项统计所有 \(pm^2\le N\) 的平方部分，第二项删掉那些本来就含有额外 \(p\) 的非法情况。为了快速求和，程序把第一项按相同的 \(\left\lfloor\sqrt{N/p}\right\rfloor\) 值分组，得到
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
更高的合法指数层 \(p^5,p^9,\dots\) 很稀疏，所以直接枚举即可，其贡献写成
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$$
若 \(v_2(n)\) 为奇数，那么数的形式是 \(2p^{4t+1}m^2\)。把它除以 2，就与上面的偶数 \(v_2\) 情况一一对应，所以只要把边界换成 \(N/2\) 再统计一次即可。
对家族 B，每个满足筛选条件的奇数 \(m\le \sqrt{N}\) 都会产生
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N$$
这一串数。可选的 \(2\) 的指数个数正好是
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
因此家族 B 的问题就变成：对每个奇数 \(m\)，判断其中指数为奇数的 \(1 \pmod 4\) 素因子个数是奇还是偶。
代码中的检查点 \(F(100)=27\) 可以完整地由上面的分类推出。
家族 A 中 \(v_2\) 为偶数的门是
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
一共 \(16\) 个。
家族 A 中 \(v_2\) 为奇数的门，等价于把不超过 \(50\) 的偶数分支结果乘以 \(2\)，得到
$$10,26,34,40,58,74,82,90,$$
共 \(8\) 个。
对家族 B，满足 \(m\le 10\) 的奇数候选只有 \(1,3,5,7,9\)。其中只有 \(m=5\) 含有奇数个指数为奇数的 \(1 \pmod 4\) 素因子，所以贡献
$$25,\ 50,\ 100,$$
共 \(3\) 个。于是
$$F(100)=16+8+3=27.$$
C++、Python 和 Java 三种实现都遵循同一套算术拆分。Python 入口只是对同一数值策略的一层轻包装，因此三种语言在数学上完全一致。
实现首先在所有商值 \(\lfloor N/i\rfloor\) 上建立一个素数计数结构。这个结构同时保存普通素数计数 \(\pi(x)\) 和带有 Dirichlet 特征的加权素数和，其中
$$\chi_4(n)= \begin{cases} 0,&n \text{ 为偶数},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
于是可以恢复
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$$
也就是 \(p\equiv 1 \pmod 4\) 的素数个数。
有了 \(\pi_1(x)\) 之后，程序把家族 A 分成三部分处理：先计算分组后的 \(p^1\) 层，再减去平方部分已经含有该素数的修正项，最后直接补上稀疏的 \(p^5,p^9,\dots\) 层。然后把同一套逻辑应用到 \(N/2\)，得到奇数 \(v_2\) 的那一半。
对家族 B，程序先预处理到 \(\lfloor\sqrt{N}\rfloor\) 为止的最小素因子表。这样每个奇数 \(m\) 都能快速分解，并判断其中指数为奇数的 \(1 \pmod 4\) 素因子个数是否为奇数。若条件成立，就把
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
加入答案。最后，程序把家族 A 中 \(v_2\) 为偶数的分支、通过 \(N/2\) 双射得到的 \(v_2\) 为奇数的分支，以及家族 B 的贡献相加，得到最终答案。
设 \(M=\lfloor\sqrt{N}\rfloor\)。最小素因子筛和奇数 \(m\) 的奇偶性表需要 \(O(M\log\log M)\) 时间和 \(O(M)\) 空间。家族 B 的扫描是 \(O(M)\)。家族 A 中高指数部分很小，因为 \(p^5\) 增长得非常快。
主要开销来自商值分块的素数计数结构，它让大量 \(\pi_1(x)\) 查询变得高效。该结构保存 \(O(M)\) 个商值，因此整体内存复杂度是 \(O(M)\)，运行时间则主要由这部分素数计数预处理和若干个线性辅助扫描决定。对 \(N=10^{12}\) 来说，这样的做法是完全可行的。
Для каждой пары различных положительных квадратов \(a^2 \lt b^2\) Питер переключает дверь \(n=a^2+b^2\), если \(n\le N\). После всех действий дверь \(n\) остается открытой ровно тогда, когда число строгих представлений
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
нечётно. Следовательно, нужно найти
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
При \(N=10^{12}\) полный перебор всех пар квадратов невозможен, поэтому решение переходит к арифметической классификации по показателям простых.
Ключевой инструмент здесь — классическая функция числа представлений в виде суммы двух квадратов, где учитываются знаки и порядок.
Обозначим
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
Каждое строгое положительное представление \(a \lt b\) даёт восемь упорядоченных решений со знаками. Есть только два вырожденных случая, дающих по четыре решения:
$$n=c^2 \quad \Rightarrow \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \Rightarrow \quad (\pm c,\pm c).$$
Если ввести
$$s(n)= \begin{cases} 1,&\text{если } n \text{ является квадратом или удвоенным квадратом},\\ 0,&\text{иначе}, \end{cases}$$
то получаем
$$r_2(n)=8u(n)+4s(n),$$
а значит,
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
Именно это тождество переводит задачу о дверях в задачу о чётности арифметического произведения.
Разложим \(n\) так:
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
Если хотя бы один простой \(q\equiv 3 \pmod 4\) входит в нечётной степени, то число \(n\) вообще не представимо как сумма двух квадратов. Тогда \(r_2(n)=0\), и дверь точно закрыта. Поэтому нужно рассматривать только
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$$
Для таких \(n\) стандартная формула даёт
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Обозначим
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
Тогда условие нечётности становится
$$R(n)=2u(n)+s(n).$$
Сначала рассмотрим \(s(n)=0\), то есть \(n\) не является ни квадратом, ни удвоенным квадратом. Тогда \(u(n)\) нечётно тогда и только тогда, когда
$$R(n)\equiv 2 \pmod 4.$$
Фактор \(\alpha_p+1\) чётен ровно при нечётном \(\alpha_p\). Чтобы произведение было равно \(2 \pmod 4\), должен существовать ровно один простой \(p\equiv 1 \pmod 4\) с нечётным показателем, причём этот показатель обязан удовлетворять
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$$
Отсюда получаем точную форму чисел этого семейства:
$$n=p^{4t+1}m^2 \quad \text{или} \quad n=2p^{4t+1}m^2,$$
где \(p\equiv 1 \pmod 4\) и \(p\nmid m\). Это и есть семейство A, которое считает реализация.
Теперь пусть \(s(n)=1\). Тогда все показатели \(\alpha_p\) чётны, а значит, \(n\) является квадратом или удвоенным квадратом. Его можно единственным образом записать как
$$n=2^a m^2,\qquad m \text{ нечётно}.$$
В этом случае \(u(n)\) нечётно тогда и только тогда, когда
$$R(n)\equiv 3 \pmod 4.$$
Если \(\alpha_p=2\delta_p\), то
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p \text{ чётно},\\ 3 \pmod 4,&\delta_p \text{ нечётно}. \end{cases}$$
Значит, \(R(n)\equiv 3 \pmod 4\) тогда и только тогда, когда в нечётном корневом множителе \(m\) нечётное число простых \(p\equiv 1 \pmod 4\) входит в нечётной степени. Это и есть семейство B:
$$n=2^a m^2,\qquad m \text{ нечётно},$$
с указанным фильтром по чётности простых делителей.
Пусть \(\pi_1(x)\) обозначает число простых \(p\le x\) с \(p\equiv 1 \pmod 4\). Для части семейства A с чётным \(2\)-адическим показателем нужно считать числа
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
Для самого первого слоя \(p^1\) вклад фиксированного простого равен
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$$
Первое слагаемое группируется по одинаковым значениям корневого частного:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
Вычитание удаляет как раз те случаи, где множитель \(p\) уже содержится в квадратной части. Более высокие допустимые слои \(p^5,p^9,\dots\) редки, поэтому они просто добавляются напрямую по формуле
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$$
Ветвь с нечётным \(v_2(n)\) получается умножением на \(2\), то есть биективно сводится к тому же подсчёту при верхней границе \(N/2\).
В семейство B каждое допустимое нечётное \(m\le \sqrt{N}\) вносит все числа
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$$
Число разрешённых степеней двойки равно
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
Поэтому остаётся лишь быстро определять для каждого нечётного \(m\), нечётно ли число простых \(p\equiv 1 \pmod 4\), входящих в него в нечётной степени.
Контрольное значение \(F(100)=27\) полностью восстанавливается из классификации.
Семейство A при чётном \(v_2\) даёт
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
то есть \(16\) дверей.
Семейство A при нечётном \(v_2\) получается удвоением чётной ветви до \(50\):
$$10,26,34,40,58,74,82,90,$$
это ещё \(8\) дверей.
Для семейства B нечётные кандидаты \(m\le 10\) равны \(1,3,5,7,9\). Только \(m=5\) проходит фильтр чётности и даёт
$$25,\ 50,\ 100,$$
то есть ещё \(3\) двери. Итого
$$F(100)=16+8+3=27.$$
Реализации на C++, Python и Java следуют одной и той же арифметической декомпозиции. Python-версия служит лишь тонкой оболочкой вокруг той же численной стратегии, поэтому математическая схема во всех трёх языках одинакова.
Сначала строится структура подсчёта простых по значениям \(\lfloor N/i\rfloor\). Она хранит как обычную функцию \(\pi(x)\), так и взвешенную сумму простых с символом Дирихле
$$\chi_4(n)= \begin{cases} 0,&n \text{ чётно},\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
Отсюда восстанавливается
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$$
то есть число простых \(p\le x\) с \(p\equiv 1 \pmod 4\).
Затем реализация считает семейство A в трёх частях: сгруппированный слой \(p^1\), корректирующий член, который вычитает квадратные части, уже содержащие выбранный простой, и прямое перечисление редких слоёв \(p^5,p^9,\dots\). Для нечётной ветви \(v_2\) та же процедура запускается на \(N/2\).
Для семейства B предварительно строится таблица наименьших простых делителей до \(\lfloor\sqrt{N}\rfloor\). С её помощью каждое нечётное \(m\) факторизуется и определяется нужная чётность числа простых \(1 \pmod 4\), входящих в нечётной степени. Если условие выполнено, к ответу прибавляется
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
В финале программа складывает ветвь семейства A с чётным \(v_2\), соответствующую ветвь с нечётным \(v_2\), полученную через биекцию с \(N/2\), и вклад семейства B.
Пусть \(M=\lfloor\sqrt{N}\rfloor\). Решето наименьших простых делителей и таблица чётности для нечётных \(m\) требуют \(O(M\log\log M)\) времени и \(O(M)\) памяти. Проход по семейству B линейный по \(M\). Часть семейства A с высокими степенями мала, потому что \(p^5\) растёт очень быстро.
Основная стоимость сосредоточена в структуре подсчёта простых по классам частных, которая делает эффективными многочисленные запросы к \(\pi_1(x)\). Она хранит \(O(M)\) значений, поэтому общий расход памяти равен \(O(M)\), а время работы определяется этой подготовкой плюс линейными вспомогательными проходами. Для \(N=10^{12}\) такой подход остаётся практичным.
لكل زوج من المربعات الموجبة المختلفة \(a^2 \lt b^2\)، يقوم Peter بتبديل حالة الباب ذي الرقم \(n=a^2+b^2\) ما دام \(n\le N\). وبعد تنفيذ جميع الخطوات، يبقى الباب \(n\) مفتوحًا إذا وفقط إذا كان عدد التمثيلات الصارمة
$$u(n)=\#\left\{(a,b)\in \mathbb{Z}_{>0}^2 : a \lt b,\ a^2+b^2=n\right\}$$
عددًا فرديًا. ولذلك نريد حساب
$$F(N)=\#\left\{n\le N : u(n)\equiv 1 \pmod 2\right\}.$$
وبما أن القيمة المطلوبة فعليًا هي \(N=10^{12}\)، فإن التعداد المباشر لكل أزواج المربعات مستحيل عمليًا. لهذا تُحوِّل الخوارزمية المسألة إلى تصنيف حسابي يعتمد على أسس العوامل الأولية.
الفكرة الأساسية هي استخدام الدالة الكلاسيكية التي تعد جميع تمثيلات العدد على صورة مجموع مربعين مع احتساب الإشارات والترتيب.
لنعرّف
$$r_2(n)=\#\left\{(x,y)\in \mathbb{Z}^2 : x^2+y^2=n\right\}.$$
كل تمثيل موجب صارم \(a \lt b\) يولّد 8 حلول مرتبة مع الإشارات. لكن توجد حالتان خاصتان لا تعطيان إلا 4 حلول:
$$n=c^2 \quad \Rightarrow \quad (\pm c,0),(0,\pm c),$$
$$n=2c^2 \quad \Rightarrow \quad (\pm c,\pm c).$$
إذا عرّفنا
$$s(n)= \begin{cases} 1,&\exists c\in\mathbb{Z}_{>0}: n=c^2 \text{ or } n=2c^2,\\ 0,&\text{otherwise}, \end{cases}$$
فإننا نحصل على
$$r_2(n)=8u(n)+4s(n),$$
ومن ثم
$$\frac{r_2(n)}{4}=2u(n)+s(n).$$
هذه هي العلاقة التي تنقل المسألة من العد المباشر للأبواب إلى فحص زوجية تعبير عددي بسيط.
نكتب تحليل \(n\) إلى عوامل أولية على الصورة
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{\beta_q}.$$
إذا ظهر أي أولي \(q\equiv 3 \pmod 4\) بأس فردي، فإن \(n\) لا يمكن تمثيله أصلًا كمجموع مربعين، وبالتالي يكون \(r_2(n)=0\) ويكون \(u(n)\) زوجيًا. لذا فالأعداد المهمة فقط هي
$$n=2^a\prod_{p\equiv 1 \pmod 4} p^{\alpha_p}\prod_{q\equiv 3 \pmod 4} q^{2\gamma_q}.$$
لهذه الأعداد تعطينا الصيغة المعروفة
$$r_2(n)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
ولنعرّف
$$R(n)=\prod_{p\equiv 1 \pmod 4}(\alpha_p+1).$$
عندها تصبح شرطية الفردية
$$R(n)=2u(n)+s(n).$$
لنبدأ بالحالة \(s(n)=0\)، أي عندما لا يكون \(n\) مربعًا ولا ضعف مربع. عندئذ يكون \(u(n)\) فرديًا إذا وفقط إذا
$$R(n)\equiv 2 \pmod 4.$$
كل عامل من الشكل \(\alpha_p+1\) يكون زوجيًا فقط عندما يكون \(\alpha_p\) فرديًا. ولكي يكون حاصل الضرب مكافئًا لـ \(2 \pmod 4\)، فلا بد من وجود أولي واحد فقط \(p\equiv 1 \pmod 4\) بأس فردي، ويجب أن يحقق ذلك الأس أيضًا
$$\alpha_p+1\equiv 2 \pmod 4 \iff \alpha_p\equiv 1 \pmod 4.$$
وهكذا نحصل بالضبط على الأعداد من الصورة
$$n\in\left\{p^{4t+1}m^2,\ 2p^{4t+1}m^2\right\},$$
حيث \(p\equiv 1 \pmod 4\) و\(p\nmid m\). هذه هي العائلة A كما تعتمدها الخوارزمية.
الآن لنأخذ الحالة \(s(n)=1\). هذا يعني أن جميع الأسس \(\alpha_p\) زوجية، وبالتالي فإن \(n\) إما مربع كامل أو ضعف مربع كامل. ويمكن كتابته بشكل وحيد على الصورة
$$n=2^a m^2,\qquad m\equiv 1 \pmod 2.$$
في هذه الحالة يكون \(u(n)\) فرديًا إذا وفقط إذا
$$R(n)\equiv 3 \pmod 4.$$
إذا كتبنا \(\alpha_p=2\delta_p\)، فإن
$$\alpha_p+1=2\delta_p+1\equiv \begin{cases} 1 \pmod 4,&\delta_p\equiv 0 \pmod 2,\\ 3 \pmod 4,&\delta_p\equiv 1 \pmod 2. \end{cases}$$
ومن ثم فإن \(R(n)\equiv 3 \pmod 4\) يحدث بالضبط عندما يكون عدد الأوليات \(p\equiv 1 \pmod 4\) التي تظهر بأس فردي داخل \(m\) عددًا فرديًا. وهذا يحدد العائلة B:
$$n=2^a m^2,\qquad m\equiv 1 \pmod 2,$$
مع فلتر زوجية يعتمد على هذا العد.
لنرمز بـ \(\pi_1(x)\) إلى عدد الأوليات \(p\le x\) التي تحقق \(p\equiv 1 \pmod 4\). في النصف الذي يملك \(v_2(n)\) زوجيًا نحتاج إلى عدّ الأعداد
$$n=p^{4t+1}m^2,\qquad p\equiv 1 \pmod 4,\ p\nmid m,\ n\le N.$$
بالنسبة إلى الطبقة الأولى \(p^1\)، فإن مساهمة أولي ثابت \(p\) هي
$$\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^3}}\right\rfloor.$$
يُعاد ترتيب الحد الأول بتجميع القيم ذات الجذر نفسه:
$$\sum_{p\equiv 1 \pmod 4}\left\lfloor\sqrt{\frac{N}{p}}\right\rfloor =\sum_{t\ge 1} t\left(\pi_1\left(\left\lfloor\frac{N}{t^2}\right\rfloor\right)-\pi_1\left(\left\lfloor\frac{N}{(t+1)^2}\right\rfloor\right)\right).$$
أما الطرح فيزيل الحالات الممنوعة التي يكون فيها العامل التربيعي محتويًا أصلًا على \(p\). وبما أن القوى الأعلى المسموح بها \(p^5,p^9,\dots\) قليلة جدًا، فإن الخوارزمية تضيفها مباشرة بواسطة
$$\left\lfloor\sqrt{\frac{N}{p^{4t+1}}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{p^{4t+3}}}\right\rfloor,\qquad t\ge 1.$$
أما الفرع الذي يملك \(v_2(n)\) فرديًا، فيقابله تقابل واحد لواحد مع الحالة الزوجية بعد استبدال \(N\) بـ \(N/2\).
في العائلة B، كل \(m\) فردي صالح بحيث \(m\le \sqrt{N}\) يولّد الأعداد
$$m^2,\ 2m^2,\ 4m^2,\ \dots,\ 2^a m^2\le N.$$
وعدد قوى \(2\) المسموح بها هو
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1.$$
إذن يبقى فقط أن نعرف، لكل \(m\) فردي، هل عدد الأوليات \(1 \pmod 4\) التي تظهر فيه بأس فردي فردي أم زوجي.
قيمة التحقق \(F(100)=27\) تظهر مباشرة من التصنيف.
العائلة A عندما يكون \(v_2\) زوجيًا تعطي
$$5,13,17,20,29,37,41,45,52,53,61,68,73,80,89,97,$$
أي \(16\) بابًا.
أما العائلة A عندما يكون \(v_2\) فرديًا، فنحصل عليها بمضاعفة الفرع الزوجي حتى \(50\)، أي
$$10,26,34,40,58,74,82,90,$$
فتضيف \(8\) أبواب أخرى.
وفي العائلة B تكون القيم الفردية الممكنة لـ \(m\le 10\) هي \(1,3,5,7,9\). الوحيد الذي ينجح في شرط الزوجية هو \(m=5\)، ولذلك يساهم بالأعداد
$$25,\ 50,\ 100,$$
أي \(3\) أبواب. ومن ثم
$$F(100)=16+8+3=27.$$
تتبع تنفيذات C++ وPython وJava التفكيك الحسابي نفسه. ومدخل Python ليس إلا غلافًا خفيفًا حول الاستراتيجية العددية نفسها، لذلك تبقى الرياضيات المستعملة متطابقة بين اللغات الثلاث.
تبدأ الخوارزمية ببناء بنية لعدّ الأوليات فوق قيم القسمة \(\lfloor N/i\rfloor\). وتخزن هذه البنية كلًا من \(\pi(x)\) ومجموعًا موزونًا للأوليات باستخدام محرف ديريشليه
$$\chi_4(n)= \begin{cases} 0,&n\equiv 0 \pmod 2,\\ 1,&n\equiv 1 \pmod 4,\\ -1,&n\equiv 3 \pmod 4. \end{cases}$$
ومن خلالهما تسترجع
$$\pi_1(x)=\frac{(\pi(x)-1)+\sum_{p\le x}\chi_4(p)}{2},$$
أي عدد الأوليات \(p\le x\) التي تحقق \(p\equiv 1 \pmod 4\).
بعد ذلك تحسب الشيفرة العائلة A في ثلاثة أجزاء: طبقة \(p^1\) المجمعة، وحدّ التصحيح الذي يحذف الجذور التي يحتوي جزؤها التربيعي بالفعل على الأولي المختار، ثم تعداد الطبقات المتناثرة \(p^5,p^9,\dots\) مباشرة. وبعد ذلك تعيد استخدام الروتين نفسه مع \(N/2\) من أجل فرع \(v_2\) الفردي.
أما في العائلة B، فتبني الشيفرة جدولًا لأصغر عامل أولي حتى \(\lfloor\sqrt{N}\rfloor\). هذا يسمح بتحليل كل \(m\) فردي بسرعة، وتحديد ما إذا كان عدد أوليات \(1 \pmod 4\) التي تظهر بأس فردي عددًا فرديًا. وعند تحقق الشرط تُضيف
$$\left\lfloor \log_2\left(\frac{N}{m^2}\right)\right\rfloor+1$$
إلى الجواب. وفي النهاية تجمع الشيفرة فرع العائلة A ذي \(v_2\) الزوجي، والفرع المناظر ذي \(v_2\) الفردي الناتج من تقابل \(N/2\)، ثم تضيف مساهمة العائلة B للحصول على الجواب النهائي.
لنضع \(M=\lfloor\sqrt{N}\rfloor\). يحتاج غربال أصغر عامل أولي وجدول الزوجية الخاص بالقيم الفردية \(m\) إلى زمن \(O(M\log\log M)\) وذاكرة \(O(M)\). أما مسح العائلة B فهو خطي في \(M\). والجزء الخاص بالقوى الأعلى في العائلة A صغير لأن \(p^5\) يكبر بسرعة كبيرة.
أما الكلفة الغالبة فتأتي من بنية عدّ الأوليات على فئات القسمة، لأنها تجعل الاستعلام عن قيم كثيرة من \(\pi_1(x)\) عمليًا. هذه البنية تخزن \(O(M)\) قيمة، ولذلك يكون استهلاك الذاكرة الكلي \(O(M)\)، بينما يهيمن على زمن التنفيذ تجهيز عدّ الأوليات هذا إضافة إلى المرورين الخطيين المساعدين. ولهذا تبقى الطريقة عملية حتى عند \(N=10^{12}\).