Goldbach's other conjecture claims that every odd composite number can be written in the form \(n = p + 2s^2\), where \(p\) is prime and \(s \ge 1\) is an integer. The problem asks for the smallest odd composite for which no such decomposition exists.
The provided implementations solve that search problem directly. They do not rely on a sieve or on advanced additive number theory; instead, they repeatedly test whether a fixed odd composite leaves a prime residue after subtracting twice a square.
Fix an odd composite number \(n\). The entire problem is to decide whether at least one square term produces a prime remainder.
The defining condition is
$$n = p + 2s^2.$$
For a fixed \(n\), this is equivalent to
$$p = n - 2s^2.$$
So the relevant mathematical object is the finite set
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
The conjecture holds for \(n\) exactly when \(R(n)\) contains at least one prime. If every element of \(R(n)\) is composite, then \(n\) is a counterexample.
Because \(n\) is odd and \(2s^2\) is even, every residue \(n-2s^2\) is odd. That parity observation matters: once the special case \(2\) is ruled out, any successful residue must be an odd prime, so even trial divisors can be skipped in the primality test.
If \(2s^2 \ge n\), then \(n-2s^2 \le 0\), and a non-positive integer cannot be prime. Therefore only finitely many values of \(s\) need to be checked:
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor.$$
This bound is exactly what makes the brute-force search small. For each candidate odd composite, the inner loop is not open-ended; it stops as soon as twice the square reaches or exceeds \(n\).
There are two natural ways to test the conjecture for a fixed \(n\):
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
One can iterate over primes \(p<n\) and ask whether \((n-p)/2\) is a perfect square, or iterate over the square parameter \(s\) and ask whether \(n-2s^2\) is prime. The implementations choose the second viewpoint, because it generates the sequence \(2,8,18,32,\dots\) in a simple monotone order and reduces every test to one integer subtraction followed by one primality check.
The checkpoint values used by the implementations are good illustrations of the method.
For \(n=33\), the first square already works:
$$33-2\cdot 1^2=31,$$
and \(31\) is prime, so \(33=31+2\cdot 1^2\).
For \(n=45\), the same thing happens:
$$45-2\cdot 1^2=43,$$
and \(43\) is prime, so \(45=43+2\cdot 1^2\).
For \(n=27\), the first residue fails but the second succeeds:
$$27-2\cdot 1^2=25 \quad \text{(composite)},$$
$$27-2\cdot 2^2=19 \quad \text{(prime)}.$$
Hence \(27=19+2\cdot 2^2\). A true counterexample would be an odd composite for which every admissible residue behaves like the first line above and none behaves like the second.
The property "can be written as a prime plus twice a square" is local to each \(n\); there is no recurrence linking one candidate to the next. Therefore the mathematically complete strategy is simply to scan odd numbers in increasing order, ignore the primes, and test each odd composite by the residue criterion.
Once the search reaches an odd composite for which no prime residue exists, the problem is solved immediately. Every smaller odd composite has already been checked and found representable, so the first failure is automatically the smallest counterexample.
The C++, Python, and Java implementations first reject numbers below \(2\), then handle the even case separately. For an odd candidate, they try odd divisors \(3,5,7,\dots\) until the divisor squared would exceed the candidate. If no divisor is found, the candidate is prime.
For a fixed odd composite \(n\), the implementation enumerates \(s=1,2,3,\dots\) while \(2s^2<n\). At each step it forms the residue \(n-2s^2\) and sends that number to the primality test. The moment one residue is prime, the current \(n\) is certified representable and the inner loop stops early.
The outer loop runs through \(9,11,13,\dots\) in increasing order. Prime values are skipped immediately. Composite values are tested by the method above, and the first one that fails is returned as the answer. Before starting the full search, the implementations also verify that \(33\) and \(45\) do satisfy the conjectured form, which serves as a lightweight sanity check.
For a candidate of size \(n\), there are \(O(\sqrt{n})\) admissible values of \(s\). Each residue is checked for primality by trial division in \(O(\sqrt{n})\) time, so the worst-case cost of testing one odd composite is \(O(n)\).
If the search is carried out up to some bound \(N\), the total worst-case running time is \(O(N^2)\), because the algorithm examines \(O(N)\) odd numbers and may spend linear time in the current value on each difficult composite. The memory usage is \(O(1)\): the implementations keep only a few integers and do not build a sieve table. In practice the method is still fast because the first counterexample occurs at a modest size and many composites succeed after only one or two square tests.
Goldbachs andere Vermutung behauptet, dass sich jede ungerade zusammengesetzte Zahl in der Form \(n = p + 2s^2\) schreiben lasse, wobei \(p\) eine Primzahl und \(s \ge 1\) eine ganze Zahl ist. Gesucht ist die kleinste ungerade zusammengesetzte Zahl, für die eine solche Darstellung nicht existiert.
Die vorhandenen Implementierungen lösen genau diese Suchaufgabe direkt. Sie verwenden weder ein Sieb noch tiefe Sätze aus der additiven Zahlentheorie, sondern prüfen wiederholt, ob bei einer festen ungeraden Kompositzahl nach dem Abziehen von zweimal einem Quadrat ein Primrest übrig bleibt.
Sei \(n\) eine feste ungerade zusammengesetzte Zahl. Dann besteht das gesamte Problem darin, zu entscheiden, ob mindestens ein Quadratterm einen Primrest erzeugt.
Die Bedingung lautet
$$n = p + 2s^2.$$
Für festes \(n\) ist das gleichbedeutend mit
$$p = n - 2s^2.$$
Das zentrale mathematische Objekt ist also die endliche Menge
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
Die Vermutung gilt für \(n\) genau dann, wenn \(R(n)\) mindestens eine Primzahl enthält. Sind alle Elemente von \(R(n)\) zusammengesetzt, dann ist \(n\) ein Gegenbeispiel.
Da \(n\) ungerade und \(2s^2\) gerade ist, ist auch jeder Rest \(n-2s^2\) ungerade. Diese Paritätsbeobachtung ist praktisch wichtig: Sobald der Spezialfall \(2\) ausgeschlossen ist, kann ein erfolgreicher Rest nur eine ungerade Primzahl sein, also dürfen gerade Teiler in der Primzahlprüfung übersprungen werden.
Falls \(2s^2 \ge n\), gilt \(n-2s^2 \le 0\), und eine nichtpositive Zahl kann keine Primzahl sein. Es genügt also, nur
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor$$
zu prüfen. Diese Schranke ist exakt die Grenze der inneren Schleife. Für jede ungerade Kompositzahl ist die Zahl der notwendigen Tests daher von vornherein endlich und klein.
Man kann die Vermutung für ein festes \(n\) auf zwei gleichwertige Arten testen:
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
Entweder iteriert man über Primzahlen \(p<n\) und fragt, ob \((n-p)/2\) ein Quadrat ist, oder man iteriert über den Quadratparameter \(s\) und fragt, ob \(n-2s^2\) prim ist. Die Implementierungen wählen die zweite Sichtweise, weil die Folge \(2,8,18,32,\dots\) einfach erzeugt wird und jeder Schritt nur aus einer Subtraktion und einem Primzahltest besteht.
Die in den Implementierungen verwendeten Prüfwerte illustrieren das Verfahren gut.
Für \(n=33\) funktioniert schon das erste Quadrat:
$$33-2\cdot 1^2=31,$$
und \(31\) ist prim. Also gilt \(33=31+2\cdot 1^2\).
Für \(n=45\) passiert dasselbe:
$$45-2\cdot 1^2=43,$$
und \(43\) ist prim. Also gilt \(45=43+2\cdot 1^2\).
Bei \(n=27\) scheitert der erste Rest, der zweite aber nicht:
$$27-2\cdot 1^2=25 \quad \text{(zusammengesetzt)},$$
$$27-2\cdot 2^2=19 \quad \text{(prim)}.$$
Damit folgt \(27=19+2\cdot 2^2\). Ein echtes Gegenbeispiel müsste so beschaffen sein, dass jeder zulässige Rest wie die erste Zeile endet und keiner wie die zweite.
Die Eigenschaft "als Primzahl plus zweimal ein Quadrat darstellbar" ist lokal für jedes \(n\); es gibt keine Rekursion, die verschiedene Kandidaten miteinander verknüpft. Deshalb ist die mathematisch vollständige Strategie ganz einfach: ungerade Zahlen der Reihe nach durchsuchen, Primzahlen überspringen und jede ungerade Kompositzahl mit dem Restetest prüfen.
Sobald eine ungerade Kompositzahl erreicht ist, für die kein Primrest existiert, ist die Aufgabe beendet. Alle kleineren ungeraden Kompositzahlen wurden bereits erfolgreich geprüft, also ist der erste Fehlschlag automatisch das kleinste Gegenbeispiel.
Die C++-, Python- und Java-Implementierungen verwerfen zuerst Zahlen kleiner als \(2\) und behandeln den geraden Fall separat. Für einen ungeraden Kandidaten testen sie die ungeraden Teiler \(3,5,7,\dots\), bis das Quadrat des Teilers den Kandidaten überschreiten würde. Wird kein Teiler gefunden, ist die Zahl prim.
Für eine feste ungerade Kompositzahl \(n\) läuft die Implementierung durch \(s=1,2,3,\dots\), solange \(2s^2<n\) gilt. In jedem Schritt wird der Rest \(n-2s^2\) gebildet und auf Primzahl geprüft. Sobald ein Primrest auftaucht, ist die aktuelle Zahl \(n\) als darstellbar bestätigt, und die innere Schleife bricht sofort ab.
Die äußere Schleife betrachtet \(9,11,13,\dots\) in aufsteigender Reihenfolge. Primzahlen werden sofort übersprungen. Zusammengesetzte Zahlen werden mit der beschriebenen Methode geprüft, und der erste Fehlschlag wird zurückgegeben. Vor der vollständigen Suche verifizieren die Implementierungen außerdem noch, dass \(33\) und \(45\) tatsächlich die vermutete Form besitzen; das ist eine kleine, aber nützliche Plausibilitätskontrolle.
Für einen Kandidaten der Größe \(n\) gibt es \(O(\sqrt{n})\) zulässige Werte von \(s\). Jeder zugehörige Rest wird per Probedivision in \(O(\sqrt{n})\) auf Primzahl getestet, also kostet die Prüfung einer einzelnen ungeraden Kompositzahl im Worst Case \(O(n)\).
Wird bis zu einer Schranke \(N\) gesucht, ergibt sich insgesamt eine Worst-Case-Laufzeit von \(O(N^2)\), weil \(O(N)\) ungerade Zahlen betrachtet werden und schwierige Kompositzahlen linear in ihrer aktuellen Größe kosten können. Der Speicherverbrauch ist \(O(1)\): Es werden nur wenige Ganzzahlen gehalten, kein Sieb und keine große Tabelle. Praktisch ist das Verfahren dennoch schnell, weil das erste Gegenbeispiel klein ist und viele Kompositzahlen schon nach einem oder zwei Quadrattests erfolgreich sind.
Goldbach'ın diğer varsayımı, her tek bileşik sayının \(n = p + 2s^2\) biçiminde yazılabildiğini söyler; burada \(p\) bir asal sayı, \(s \ge 1\) ise bir tam sayıdır. Soruda istenen şey, böyle bir ayrışımı olmayan en küçük tek bileşik sayıyı bulmaktır.
Mevcut uygulamalar bu aramayı doğrudan yapar. Bir asal eleği kurmazlar ve ileri düzey toplamsal sayı teorisi kullanmazlar; bunun yerine sabit bir tek bileşik için, iki kat bir kare çıkarıldığında asal bir kalan oluşup oluşmadığını tekrar tekrar sınarlar.
\(n\) sabit bir tek bileşik sayı olsun. Bütün mesele, en az bir kare teriminin asal bir artık üretip üretmediğini belirlemektir.
Temel koşul şudur:
$$n = p + 2s^2.$$
Sabit \(n\) için bu,
$$p = n - 2s^2$$
ifadesiyle eşdeğerdir. Dolayısıyla esas matematiksel nesne
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}$$
sonlu kümesidir. Varsayım, \(R(n)\) içinde en az bir asal varsa \(n\) için doğrudur. Eğer \(R(n)\)'in bütün elemanları bileşikse, o zaman \(n\) bir karşı örnektir.
\(n\) tek ve \(2s^2\) çift olduğu için her artık \(n-2s^2\) yine tektir. Bu parite gözlemi pratiktir: \(2\) özel durumu zaten dışarıda kaldığından, başarılı bir kalan ancak tek bir asal olabilir. Bu yüzden asal testi yapılırken çift bölenleri atlamak doğrudur.
Eğer \(2s^2 \ge n\) ise \(n-2s^2 \le 0\) olur ve pozitif olmayan bir sayı asal olamaz. Bu nedenle yalnızca
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor$$
değerlerini denemek gerekir. Bu sınır, iç döngünün neden kısa olduğunu tam olarak açıklar. Her aday için test edilecek kare sayısı baştan bellidir.
Sabit bir \(n\) için varsayımı sınamanın iki doğal yolu vardır:
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
Bir yaklaşım, \(p<n\) asalları üzerinde dolaşıp \((n-p)/2\)'nin tam kare olup olmadığını sormaktır. Diğer yaklaşım ise kare parametresi \(s\) üzerinde dolaşıp \(n-2s^2\)'nin asal olup olmadığını kontrol etmektir. Uygulamalar ikinci yolu seçer; çünkü \(2,8,18,32,\dots\) dizisi doğal olarak üretilir ve her adım yalnızca bir çıkarma ile bir asal testinden ibarettir.
Uygulamaların doğrulama için kullandığı sayılar yöntemi açıkça gösterir.
\(n=33\) için ilk kare hemen işe yarar:
$$33-2\cdot 1^2=31,$$
ve \(31\) asaldır. Yani \(33=31+2\cdot 1^2\).
\(n=45\) için de aynı durum geçerlidir:
$$45-2\cdot 1^2=43,$$
ve \(43\) asaldır. Dolayısıyla \(45=43+2\cdot 1^2\).
\(n=27\) için ilk artık başarısız, ikinci artık başarılıdır:
$$27-2\cdot 1^2=25 \quad \text{(bileşik)},$$
$$27-2\cdot 2^2=19 \quad \text{(asal)}.$$
Böylece \(27=19+2\cdot 2^2\) elde edilir. Gerçek bir karşı örnekte ise izinli artıkların hepsi ilk satırdaki gibi bileşik çıkmalı, hiçbiri ikinci satırdaki gibi asal olmamalıdır.
"Bir asal ile iki kat bir karenin toplamı olarak yazılabilme" özelliği her \(n\) için yereldir; bir adayın sonucu diğerine bağlı değildir. Bu nedenle matematiksel olarak tam strateji çok basittir: tek sayıları artan sırayla tara, asalları atla ve her tek bileşiği artık testiyle kontrol et.
Asal artık üretmeyen ilk tek bileşik bulunduğu anda iş biter. Ondan küçük tüm tek bileşikler zaten kontrol edilip temsil edilebilir bulunmuştur; dolayısıyla ilk başarısızlık otomatik olarak en küçük karşı örnektir.
C++, Python ve Java uygulamaları önce \(2\)'den küçük sayıları eler, ardından çift sayı durumunu ayrı ele alır. Tek bir aday için ise \(3,5,7,\dots\) biçimindeki tek bölenleri denerler; bölenin karesi aday sayıyı aşacağı noktaya gelince dururlar. Hiç bölen bulunmazsa sayı asaldır.
Sabit bir tek bileşik \(n\) için uygulama \(2s^2<n\) olduğu sürece \(s=1,2,3,\dots\) değerlerini dolaşır. Her adımda \(n-2s^2\) kalanı hesaplanır ve asal teste gönderilir. Kalanlardan biri asal çıkar çıkmaz mevcut \(n\)'nin varsayılan biçimde yazılabildiği anlaşılır ve iç döngü erken sonlanır.
Dış döngü \(9,11,13,\dots\) dizisini artan sırayla gezer. Asal değerler hemen atlanır. Bileşik değerler yukarıdaki yöntemle test edilir ve başarısız olan ilk sayı sonuç olarak döndürülür. Tam aramadan önce uygulamalar ayrıca \(33\) ve \(45\)'in gerçekten varsayılan biçimde yazılabildiğini doğrular; bu da hafif ama yararlı bir tutarlılık kontrolüdür.
Büyüklüğü \(n\) olan bir aday için \(O(\sqrt{n})\) adet uygun \(s\) değeri vardır. Her kalanın asallığı deneme bölmesiyle \(O(\sqrt{n})\) zamanda sınandığı için, tek bir tek bileşiği test etmenin en kötü durum maliyeti \(O(n)\) olur.
Arama \(N\) sınırına kadar sürdürülürse toplam en kötü durum çalışma süresi \(O(N^2)\)'dir; çünkü algoritma \(O(N)\) kadar tek sayı inceler ve zor adaylarda mevcut sayı büyüklüğü mertebesinde iş yapabilir. Bellek kullanımı \(O(1)\)'dir: yalnızca birkaç tam sayı tutulur, büyük bir tablo ya da asal eleği kurulmaz. Pratikte yöntem yine de hızlıdır; çünkü ilk karşı örnek küçüktür ve birçok bileşik, bir veya iki kare denemesinden sonra başarıyla elenir.
La otra conjetura de Goldbach afirma que todo número compuesto impar puede escribirse como \(n = p + 2s^2\), donde \(p\) es primo y \(s \ge 1\) es un entero. La tarea consiste en encontrar el menor compuesto impar para el cual no existe tal descomposición.
Las implementaciones disponibles resuelven esa búsqueda de forma directa. No usan un tamiz de primos ni teoría aditiva profunda; simplemente comprueban repetidamente si un compuesto impar fijo deja un residuo primo después de restarle el doble de un cuadrado.
Fijemos un número compuesto impar \(n\). Todo el problema consiste en decidir si al menos un término cuadrático produce un resto primo.
La condición básica es
$$n = p + 2s^2.$$
Para un \(n\) fijo, esto equivale a
$$p = n - 2s^2.$$
Por tanto, el objeto matemático central es el conjunto finito
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
La conjetura es válida para \(n\) exactamente cuando \(R(n)\) contiene al menos un primo. Si todos los elementos de \(R(n)\) son compuestos, entonces \(n\) es un contraejemplo.
Como \(n\) es impar y \(2s^2\) es par, cada residuo \(n-2s^2\) también es impar. Esa observación de paridad es útil: una vez descartado el caso especial \(2\), cualquier residuo exitoso debe ser un primo impar, de modo que en la prueba de primalidad pueden omitirse los divisores pares.
Si \(2s^2 \ge n\), entonces \(n-2s^2 \le 0\), y un entero no positivo no puede ser primo. Por ello basta con revisar
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor.$$
Esta cota es exactamente la razón por la que la búsqueda por fuerza bruta resulta pequeña. Para cada compuesto impar, el bucle interior está acotado desde el principio.
Hay dos maneras naturales de comprobar la conjetura para un \(n\) fijo:
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
Se puede iterar sobre los primos \(p<n\) y preguntar si \((n-p)/2\) es un cuadrado perfecto, o bien iterar sobre el parámetro cuadrático \(s\) y preguntar si \(n-2s^2\) es primo. Las implementaciones adoptan la segunda visión, porque genera la sucesión \(2,8,18,32,\dots\) en orden creciente y cada paso se reduce a una resta entera seguida de una prueba de primalidad.
Los valores de comprobación usados por las implementaciones muestran bien el mecanismo.
Para \(n=33\), el primer cuadrado ya funciona:
$$33-2\cdot 1^2=31,$$
y \(31\) es primo. Por tanto, \(33=31+2\cdot 1^2\).
Para \(n=45\), ocurre lo mismo:
$$45-2\cdot 1^2=43,$$
y \(43\) es primo. Luego \(45=43+2\cdot 1^2\).
En \(n=27\), el primer residuo falla pero el segundo sí sirve:
$$27-2\cdot 1^2=25 \quad \text{(compuesto)},$$
$$27-2\cdot 2^2=19 \quad \text{(primo)}.$$
Así, \(27=19+2\cdot 2^2\). Un contraejemplo auténtico tendría que comportarse como la primera línea para todos los residuos permitidos y nunca como la segunda.
La propiedad "puede escribirse como un primo más el doble de un cuadrado" es local para cada \(n\); no hay ninguna recurrencia que conecte un candidato con el siguiente. Por eso la estrategia matemáticamente completa es simplemente recorrer los impares en orden creciente, ignorar los primos y probar cada compuesto impar mediante el criterio de residuos.
En cuanto se alcanza un compuesto impar sin ningún residuo primo, el problema queda resuelto. Todos los compuestos impares menores ya han sido examinados y sí admiten representación, así que el primer fallo es automáticamente el menor contraejemplo.
Las implementaciones en C++, Python y Java primero descartan los números menores que \(2\) y tratan el caso par por separado. Para un candidato impar, prueban divisores impares \(3,5,7,\dots\) hasta que el cuadrado del divisor superaría al candidato. Si no aparece ningún divisor, el número es primo.
Para un compuesto impar fijo \(n\), la implementación recorre \(s=1,2,3,\dots\) mientras \(2s^2<n\). En cada paso calcula el residuo \(n-2s^2\) y lo somete a la prueba de primalidad. En cuanto uno de esos residuos resulta primo, el número actual \(n\) queda certificado como representable y el bucle interior termina de inmediato.
El bucle exterior recorre \(9,11,13,\dots\) en orden ascendente. Los valores primos se omiten enseguida. Los compuestos se someten al test anterior, y el primero que falla se devuelve como respuesta. Antes de iniciar la búsqueda completa, las implementaciones también verifican que \(33\) y \(45\) sí satisfacen la forma conjeturada; eso actúa como una comprobación ligera de consistencia.
Para un candidato de tamaño \(n\), existen \(O(\sqrt{n})\) valores admisibles de \(s\). Cada residuo se comprueba con división de prueba en \(O(\sqrt{n})\), de modo que el coste en el peor caso para un solo compuesto impar es \(O(n)\).
Si la búsqueda se prolonga hasta una cota \(N\), el tiempo total en el peor caso es \(O(N^2)\), porque el algoritmo examina \(O(N)\) números impares y puede gastar tiempo lineal en el valor actual para algunos compuestos difíciles. El uso de memoria es \(O(1)\): solo se mantienen unos pocos enteros y no se construye ningún tamiz. En la práctica, el método es muy rápido porque el primer contraejemplo aparece pronto y muchos compuestos se aceptan tras una o dos pruebas de cuadrados.
哥德巴赫的另一猜想声称：每个奇合数都可以写成 \(n = p + 2s^2\) 的形式，其中 \(p\) 是素数，\(s \ge 1\) 是整数。本题要求找出最小的一个奇合数，使它无法写成这种形式。
给出的实现采用的是直接搜索，而不是复杂理论。它们既不建立素数筛，也不依赖深层的加法数论结果；核心做法只是反复检查：对一个固定的奇合数 \(n\)，减去若干个 \(2s^2\) 之后，是否能留下一个素数余数。
固定一个奇合数 \(n\)。整个问题就变成：是否存在某个正整数 \(s\)，使得减去 \(2s^2\) 之后得到的数是素数。
题目的表示式是
$$n = p + 2s^2.$$
对于固定的 \(n\)，它等价于
$$p = n - 2s^2.$$
因此真正需要研究的数学对象是下面这个有限集合：
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
如果 \(R(n)\) 中至少有一个元素是素数，那么这个 \(n\) 就满足猜想；如果 \(R(n)\) 中所有元素都是合数，那么 \(n\) 就是一个反例。
这里有一个很直接但很有用的奇偶性事实：\(n\) 是奇数，而 \(2s^2\) 一定是偶数，所以每个余数 \(n-2s^2\) 也都是奇数。这意味着一旦排除了特殊值 \(2\)，真正可能成功的余数只能是奇素数，因此素性检测时完全可以跳过所有偶数试除因子。
如果 \(2s^2 \ge n\)，那么
$$n-2s^2 \le 0,$$
非正整数不可能是素数。因此只需要枚举满足
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor$$
的那些 \(s\)。这条上界非常关键，因为它说明内层检查不是无限搜索，而是一个严格受限的有限循环。对于每个候选奇合数，要检查的平方项数量大约只有 \(\sqrt{n/2}\) 级别。
对于固定的 \(n\)，可以从两个方向来理解同一个条件：
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
一种想法是枚举所有小于 \(n\) 的素数 \(p\)，再检查 \((n-p)/2\) 是否为完全平方数。另一种想法是反过来枚举平方参数 \(s\)，直接看 \(n-2s^2\) 是否为素数。给出的实现统一采用第二种视角，因为它只需要生成序列
$$2,\,8,\,18,\,32,\,50,\dots$$
然后逐项做整数减法和素性判断，不需要额外的“是否为完全平方数”的判定逻辑。
实现里用到的检查样例正好能说明算法是如何工作的。
对 \(n=33\)，第一个平方项就已经成功：
$$33-2\cdot 1^2=31,$$
而 \(31\) 是素数，所以
$$33=31+2\cdot 1^2.$$
对 \(n=45\)，同样是第一步成功：
$$45-2\cdot 1^2=43,$$
\(43\) 也是素数，因此
$$45=43+2\cdot 1^2.$$
再看一个稍微有层次的例子 \(n=27\)。第一次尝试失败：
$$27-2\cdot 1^2=25 \quad \text{（合数）},$$
但第二次尝试成功：
$$27-2\cdot 2^2=19 \quad \text{（素数）}.$$
于是得到
$$27=19+2\cdot 2^2.$$
真正的反例必须更加“顽固”：对所有允许的 \(s\)，对应的余数都像 \(25\) 那样是合数，而不会像 \(19\) 那样突然出现一个素数。
“能否表示成一个素数加上两倍平方数”这个性质，对每个 \(n\) 来说都是独立判定的；前一个候选值不会给后一个候选值提供递推关系。因此最完整、也最直接的数学策略就是：按从小到大的顺序扫描奇数，跳过其中的素数，只对奇合数做上述余数测试。
一旦遇到某个奇合数，它对所有允许的 \(s\) 都无法产生素数余数，那么题目就已经解决。因为所有更小的奇合数都已经被检查过并确认可以表示，所以这个“第一个失败值”自动就是最小反例。
C++、Python 和 Java 版本都会先排除小于 \(2\) 的数，再单独处理偶数情况。对于奇数候选，它们只尝试奇因子 \(3,5,7,\dots\)，直到试除因子的平方即将超过候选值为止。如果始终没有整除因子，那么这个数就是素数。
对固定的奇合数 \(n\)，实现按顺序枚举 \(s=1,2,3,\dots\)，只要满足 \(2s^2<n\) 就继续。每一步都计算余数 \(n-2s^2\)，然后对这个余数做素性判断。只要某一步发现余数是素数，就说明当前 \(n\) 可以写成题目要求的形式，于是内层循环立刻提前结束。
外层循环依次考察 \(9,11,13,\dots\)。如果当前值本身是素数，就直接跳过；如果是合数，就进入前面的平方枚举测试。第一个无法通过测试的奇合数会被立即返回。正式搜索开始前，这些实现还会先验证 \(33\) 和 \(45\) 的确能够写成题目中的形式，这相当于一个很轻量的正确性检查。
当候选数的大小为 \(n\) 时，可枚举的 \(s\) 大约有 \(O(\sqrt{n})\) 个。每个余数的素性判断又需要 \(O(\sqrt{n})\) 级别的试除，因此测试单个奇合数的最坏时间复杂度是 \(O(n)\)。
如果把搜索一直进行到某个上界 \(N\)，总的最坏时间复杂度就是 \(O(N^2)\)：因为算法会检查 \(O(N)\) 个奇数，而对某些较难的合数，代价可能与当前数值同阶。空间复杂度是 \(O(1)\)，因为实现中只维护少量整数变量，没有建立筛表或大型缓存。尽管如此，这个直接算法在本题里仍然非常快，因为最小反例出现得不大，而且很多合数在前一两个平方尝试时就已经找到素数余数了。
Другая гипотеза Гольдбаха утверждает, что каждое нечётное составное число можно представить в виде \(n = p + 2s^2\), где \(p\) - простое число, а \(s \ge 1\) - целое. Требуется найти наименьшее нечётное составное число, для которого такого представления не существует.
Данные реализации решают именно эту задачу прямым перебором. Они не строят решето простых чисел и не опираются на глубокие результаты аддитивной теории чисел; вместо этого они многократно проверяют, остаётся ли после вычитания \(2s^2\) из фиксированного нечётного составного числа простой остаток.
Зафиксируем нечётное составное число \(n\). Тогда вся задача сводится к вопросу: существует ли хотя бы одно значение \(s\), при котором остаток оказывается простым.
Исходное условие имеет вид
$$n = p + 2s^2.$$
Для фиксированного \(n\) это равносильно равенству
$$p = n - 2s^2.$$
Следовательно, центральным математическим объектом становится конечное множество
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
Гипотеза верна для данного \(n\) тогда и только тогда, когда в \(R(n)\) есть хотя бы одно простое число. Если же все элементы \(R(n)\) составные, то \(n\) является контрпримером.
Так как \(n\) нечётно, а \(2s^2\) всегда чётно, каждый остаток \(n-2s^2\) тоже нечётен. Это важное наблюдение по чётности: после исключения специального случая \(2\) возможный успешный остаток может быть только нечётным простым числом, поэтому при проверке простоты можно сразу пропускать чётные делители.
Если \(2s^2 \ge n\), то \(n-2s^2 \le 0\), а неположительное число не может быть простым. Значит, достаточно проверять только
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor.$$
Именно эта граница делает перебор коротким: внутренняя проверка для каждого кандидата заранее ограничена и не может продолжаться бесконечно.
Для фиксированного \(n\) гипотезу можно проверять двумя естественными способами:
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
Можно перебирать простые числа \(p<n\) и спрашивать, является ли \((n-p)/2\) точным квадратом. А можно, наоборот, перебирать параметр \(s\) и проверять, простое ли число \(n-2s^2\). Реализации выбирают второй вариант, потому что последовательность \(2,8,18,32,\dots\) строится очень просто, а каждый шаг сводится к одному вычитанию и одной проверке простоты.
Контрольные значения, используемые в реализациях, хорошо показывают механику метода.
Для \(n=33\) уже первый квадрат даёт успех:
$$33-2\cdot 1^2=31,$$
а \(31\) простое. Следовательно,
$$33=31+2\cdot 1^2.$$
Для \(n=45\) происходит то же самое:
$$45-2\cdot 1^2=43,$$
и \(43\) простое, значит
$$45=43+2\cdot 1^2.$$
Для \(n=27\) первый остаток не подходит, но второй подходит:
$$27-2\cdot 1^2=25 \quad \text{(составное)},$$
$$27-2\cdot 2^2=19 \quad \text{(простое)}.$$
Отсюда получается
$$27=19+2\cdot 2^2.$$
Настоящий контрпример должен вести себя гораздо жёстче: для каждого допустимого \(s\) остаток должен оказаться составным, и ни один шаг не должен дать простой результат.
Свойство "представимо как простое число плюс удвоенный квадрат" проверяется локально для каждого \(n\); никакой рекуррентной связи между соседними кандидатами здесь нет. Поэтому математически полный метод очень прост: идти по нечётным числам в порядке возрастания, пропускать простые и проверять каждое нечётное составное по критерию остатков.
Как только встречается нечётное составное число, для которого не найдено ни одного простого остатка, задача решена. Все меньшие нечётные составные уже были проверены и оказались представимыми, значит первый неуспех автоматически является наименьшим контрпримером.
Реализации на C++, Python и Java сначала отбрасывают числа меньше \(2\), затем отдельно обрабатывают чётный случай. Для нечётного кандидата они пробуют нечётные делители \(3,5,7,\dots\), пока квадрат текущего делителя не превысит проверяемое число. Если делитель не найден, число объявляется простым.
Для фиксированного нечётного составного \(n\) реализация перебирает \(s=1,2,3,\dots\), пока выполняется неравенство \(2s^2<n\). На каждом шаге вычисляется остаток \(n-2s^2\), после чего он проверяется на простоту. Как только находится простой остаток, текущее \(n\) признаётся представимым, и внутренняя проверка завершается досрочно.
Внешний цикл проходит по значениям \(9,11,13,\dots\) в возрастающем порядке. Простые числа пропускаются сразу. Составные числа отправляются в описанную выше проверку, и первое неудачное значение возвращается как ответ. Перед полным перебором реализации дополнительно убеждаются, что \(33\) и \(45\) действительно имеют требуемое представление; это служит небольшой проверкой корректности.
Для кандидата размера \(n\) существует \(O(\sqrt{n})\) допустимых значений \(s\). Проверка простоты каждого остатка методом пробного деления занимает \(O(\sqrt{n})\), поэтому проверка одного нечётного составного числа в худшем случае стоит \(O(n)\).
Если поиск ведётся до некоторой границы \(N\), то суммарное время работы в худшем случае равно \(O(N^2)\): алгоритм рассматривает \(O(N)\) нечётных чисел и на некоторых трудных составных может тратить время, линейное по текущему значению. Память расходуется в объёме \(O(1)\), потому что хранятся лишь несколько целых чисел и не строится ни решето, ни большая таблица. На практике метод всё равно очень быстр, так как первый контрпример находится сравнительно рано, а многие составные числа проходят проверку уже после одного-двух квадратов.
تنص حدسية غولدباخ الأخرى على أن كل عدد مركب فردي يمكن كتابته على الصورة \(n = p + 2s^2\)، حيث \(p\) عدد أولي و\(s \ge 1\) عدد صحيح. والمطلوب هو إيجاد أصغر عدد مركب فردي لا يملك مثل هذا التمثيل.
التنفيذات المعطاة تتعامل مع هذه المهمة مباشرة. فهي لا تبني منخلًا للأعداد الأولية، ولا تعتمد على نتائج عميقة في نظرية الأعداد الجمعية؛ بل تكرر فقط السؤال التالي: إذا ثبتنا عددًا مركبًا فرديًا \(n\)، فهل يبقى عدد أولي بعد طرح \(2s^2\) لبعض قيمة صحيحة موجبة لـ \(s\)؟
لنثبت عددًا مركبًا فرديًا \(n\). تصبح المسألة كلها هي التحقق مما إذا كانت هناك قيمة واحدة على الأقل لـ \(s\) تجعل الباقي عددًا أوليًا.
الشرط الأساسي هو
$$n = p + 2s^2.$$
ومع تثبيت \(n\)، فهذا يكافئ
$$p = n - 2s^2.$$
إذن الكائن الرياضي المركزي هنا هو المجموعة المنتهية
$$R(n)=\{\,n-2s^2 : s\in\mathbb{Z}_{\ge 1},\ 2s^2<n\,\}.$$
تكون الحدسية صحيحة بالنسبة إلى \(n\) إذا وفقط إذا احتوت \(R(n)\) على عدد أولي واحد على الأقل. أما إذا كانت جميع عناصر \(R(n)\) أعدادًا مركبة، فإن \(n\) يكون مثالًا مضادًا.
هناك ملاحظة بسيطة لكنها مهمة: \(n\) فردي و\(2s^2\) زوجي دائمًا، لذلك فإن كل باقي من الصورة \(n-2s^2\) يكون فرديًا أيضًا. ونتيجة لذلك، وبعد استبعاد الحالة الخاصة للعدد \(2\)، فإن أي باقي ناجح لا بد أن يكون عددًا أوليًا فرديًا، ولهذا يمكن تجاهل القواسم الزوجية أثناء اختبار الأولية.
إذا كان \(2s^2 \ge n\)، فإن
$$n-2s^2 \le 0,$$
والعدد غير الموجب لا يمكن أن يكون أوليًا. لذلك يكفي فحص القيم التي تحقق
$$1 \le s \le \left\lfloor \sqrt{\frac{n-1}{2}} \right\rfloor.$$
هذه الحدود هي بالضبط ما يجعل البحث المباشر محدودًا وقصيرًا. فلكل عدد مركب فردي يوجد عدد نهائي صغير من القيم الممكنة لـ \(s\)، ولا توجد أي حلقة غير منتهية في الجزء الداخلي من الخوارزمية.
يمكن اختبار الشرط نفسه بطريقتين متكافئتين:
$$n = p + 2s^2 \iff \frac{n-p}{2}=s^2.$$
فإما أن نُحصي الأعداد الأولية \(p<n\) ونسأل هل \((n-p)/2\) مربع كامل، أو نُحصي قيم \(s\) ونسأل هل \(n-2s^2\) عدد أولي. التنفيذات تختار المنظور الثاني لأنه يولد المتتالية \(2,8,18,32,\dots\) بصورة طبيعية، ويجعل كل خطوة مجرد طرح صحيح واحد يتبعه اختبار أولية واحد.
قيم التحقق المستخدمة داخل التنفيذات توضح الآلية جيدًا.
عند \(n=33\)، ينجح أول مربع مباشرة:
$$33-2\cdot 1^2=31,$$
و\(31\) عدد أولي، إذن
$$33=31+2\cdot 1^2.$$
وعند \(n=45\)، يحدث الشيء نفسه:
$$45-2\cdot 1^2=43,$$
و\(43\) أولي، وبالتالي
$$45=43+2\cdot 1^2.$$
أما عند \(n=27\)، فالمحاولة الأولى تفشل لكن الثانية تنجح:
$$27-2\cdot 1^2=25.$$
والنتيجة هنا عدد مركب.
$$27-2\cdot 2^2=19.$$
والنتيجة هنا عدد أولي.
ومن ثم
$$27=19+2\cdot 2^2.$$
أما المثال المضاد الحقيقي فلا بد أن يكون أكثر صرامة: كل باقي مسموح يجب أن يكون مركبًا، ولا يجوز أن تظهر أي قيمة أولية في أي خطوة.
خاصية "إمكانية الكتابة على صورة عدد أولي زائد ضعفي مربع" هي خاصية محلية تخص كل \(n\) على حدة؛ فلا توجد علاقة عودية تربط المرشح الحالي بالمرشح التالي. ولهذا فإن الاستراتيجية الرياضية الكاملة بسيطة جدًا: نفحص الأعداد الفردية بترتيب تصاعدي، نتجاوز الأعداد الأولية، ونطبق اختبار البواقي على كل عدد مركب فردي.
بمجرد الوصول إلى عدد مركب فردي لا ينتج أي باقي أولي، تنتهي المسألة فورًا. فجميع الأعداد المركبة الفردية الأصغر قد فُحصت سابقًا وثبت أنها قابلة للتمثيل، ولذلك يكون أول فشل تلقائيًا هو أصغر مثال مضاد.
تنفيذات C++ وPython وJava تبدأ باستبعاد الأعداد الأصغر من \(2\)، ثم تعالج حالة الأعداد الزوجية على حدة. وبعد ذلك، إذا كان المرشح فرديًا، فإنها تجرب القواسم الفردية \(3,5,7,\dots\) حتى النقطة التي يصبح فيها مربع القاسم أكبر من العدد المراد اختباره. إذا لم يظهر أي قاسم صحيح، فالعدد أولي.
عند تثبيت عدد مركب فردي \(n\)، يجري التنفيذ على القيم \(s=1,2,3,\dots\) ما دام الشرط \(2s^2<n\) محققًا. في كل خطوة يُحسب الباقي \(n-2s^2\)، ثم يُختبر هذا الباقي من حيث الأولية. فإذا ظهر باقي أولي في أي خطوة، يتأكد أن \(n\) قابل للتمثيل بالشكل المطلوب، وتتوقف الحلقة الداخلية مباشرة.
الحلقة الخارجية تمر على القيم \(9,11,13,\dots\) بترتيب تصاعدي. إذا كانت القيمة الحالية أولية فإنها تُتجاوز فورًا، وإذا كانت مركبة فإنها تُرسل إلى الاختبار السابق. أول عدد يفشل في هذا الاختبار يُعاد بوصفه الجواب. وقبل بدء البحث الكامل، تتحقق التنفيذات أيضًا من أن \(33\) و\(45\) يملكان تمثيلًا صحيحًا، وذلك كفحص خفيف للسلامة المنطقية.
إذا كان حجم المرشح هو \(n\)، فعدد القيم المسموح بها لـ \(s\) هو \(O(\sqrt{n})\). وكل باقي يُختبر للأولية بالقسمة التجريبية في زمن \(O(\sqrt{n})\)، ولذلك تكون كلفة فحص عدد مركب فردي واحد في أسوأ حالة هي \(O(n)\).
وإذا استمر البحث حتى حد أعلى \(N\)، فإن زمن التنفيذ الكلي في أسوأ حالة يصبح \(O(N^2)\)، لأن الخوارزمية تمر على \(O(N)\) عددًا فرديًا، وقد تنفق زمنًا خطيًا في القيمة الحالية على بعض الأعداد المركبة الصعبة. أما الذاكرة فهي \(O(1)\) فقط، إذ لا تُخزَّن إلا مجموعة صغيرة من القيم الصحيحة ولا يُبنى منخل أو جدول كبير. ومع ذلك تبقى الطريقة سريعة عمليًا لأن المثال المضاد الأول يظهر عند قيمة صغيرة نسبيًا، ولأن كثيرًا من الأعداد المركبة تنجح بعد تجربة مربع واحد أو مربعين فقط.