The tiles are numbered in hexagonal layers around the center tile 1. For each tile \(n\), \(PD(n)\) is the number of prime values among the six absolute differences between \(n\) and its six neighbors. The task is to find the 2000th tile for which \(PD(n)=3\).
The key point is that the successful implementations never build the whole spiral explicitly. They prove that, apart from the small exceptional tiles \(1\) and \(2\), every solution must be either the first tile or the last tile of some ring, and then they test only those two closed-form candidates per ring.
Let ring \(k\) be the hexagonal layer at distance \(k\) from the center. Ring 0 consists only of tile 1, and ring \(k\ge 1\) contains \(6k\) tiles.
After finishing ring \(k\), the total number of tiles is
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
Therefore the first and last tiles of ring \(k\) are
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
So ring \(k\) is exactly the interval \([A_k,B_k]\), and its size is
$$B_k-A_k+1=6k.$$
These two endpoint formulas are the basic objects used everywhere in the solution.
Take a tile \(n\) in ring \(k\ge 2\) that is not one of the two endpoints \(A_k\) or \(B_k\). Its two neighbors on the same ring are then the consecutive values \(n-1\) and \(n+1\), so two of the six neighbor differences are already \(1\) and \(1\), which are not prime.
The other four neighbors lie on the adjacent inner and outer rings. Along a side of the spiral, those cross-ring differences appear in two consecutive pairs, and each such pair contains an even number. Hence among those four extra differences, at least two are even and greater than 2, so they are composite.
That means any non-endpoint tile can have at most two prime differences. Therefore, once the small cases are separated out, the only possible tiles with \(PD(n)=3\) are the two endpoints of each ring: the first tile \(A_k\) and the last tile \(B_k\).
For \(k\ge 2\), the six neighbors of \(A_k\) can be written in terms of nearby ring endpoints:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
Subtracting from \(A_k\) gives the six absolute differences
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
Among these, \(1\), \(6k-6\), and \(6k\) are automatically non-prime for \(k\ge 2\). So the condition collapses to exactly three numbers:
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
For the other endpoint \(B_k\), the six neighbors are
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
This yields the six absolute differences
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
Again, \(1\), \(6k\), and \(6k+6\) are certainly composite for \(k\ge 2\). Hence
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
At \(k=2\), the last two expressions are both 17, so the same prime gap occurs from two different neighbors. That still contributes two prime differences, which is exactly why \(B_2=19\) qualifies.
The second ring starts at \(A_2=8\) and ends at \(B_2=19\).
For \(A_2=8\), the six differences are
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
so the prime ones are \(11,13,29\), and therefore \(PD(8)=3\).
For \(B_2=19\), the six differences are
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
so the prime differences are \(11,17,17\), again giving \(PD(19)=3\).
This matches the beginning of the sequence generated by the implementations:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
The center tile satisfies \(PD(1)=3\), and tile 2 is the other exceptional small case. After that, the entire search becomes a scan over \(k=2,3,4,\dots\) with only two tests per ring.
The first endpoint \(A_k\) is accepted when
$$6k-1,\ 6k+1,\ 12k+5$$
are all prime, in which case the tile number is
$$A_k=3k(k-1)+2.$$
The last endpoint \(B_k\) is accepted when
$$6k-1,\ 6k+5,\ 12k-7$$
are all prime, in which case the tile number is
$$B_k=3k(k+1)+1.$$
That is the whole mathematical reduction embodied in the code.
The C++, Python, and Java implementations begin by storing the first two valid tiles, \(1\) and \(2\). They then iterate over ring indices \(k\ge 2\). No coordinate grid, adjacency table, or spiral simulation is built, because the derivation above has already reduced the problem to two explicit candidates per ring.
For each ring, the implementation first forms \(6k-1\), which appears in both endpoint tests. It then checks the three-prime condition for the first endpoint and, if successful, records \(3k(k-1)+2\). After that it checks the three-prime condition for the last endpoint and, if successful, records \(3k(k+1)+1\).
The three language versions differ only in their primality routine. The C++ implementation uses modular multiplication together with a deterministic Miller-Rabin test for 64-bit inputs, the Java implementation uses trial division through numbers of the form \(6m\pm1\), and the Python implementation delegates primality testing to a library predicate. All three apply the same formulas and stop as soon as the requested index is reached.
If the search reaches ring \(K\), the algorithm examines exactly two candidate tiles per ring and performs only constant-time arithmetic around them. Candidate generation is therefore \(O(K)\).
The full running time is \(O(K\cdot P(K))\), where \(P(K)\) is the cost of one primality test on numbers of size \(O(K)\). With trial division this is \(O(K\sqrt{K})\); with deterministic Miller-Rabin on 64-bit integers, primality testing is effectively constant-time at this scale. In practice the search is very small for the Project Euler target.
The implementations keep the successful tiles found so far in a list or array, so the auxiliary space is \(O(T)\) for target index \(T\). For \(T=2000\), this is negligible.
Die Kacheln werden in hexagonalen Schichten um die Mittelkachel 1 nummeriert. Für eine Kachel \(n\) bezeichnet \(PD(n)\) die Anzahl der Primzahlen unter den sechs absoluten Differenzen zwischen \(n\) und seinen sechs Nachbarn. Gesucht ist die 2000. Kachel mit \(PD(n)=3\).
Der entscheidende Punkt ist, dass die funktionierenden Implementierungen die gesamte Spirale nie explizit aufbauen. Sie zeigen, dass außer den kleinen Sonderfällen \(1\) und \(2\) jede Lösung entweder die erste oder die letzte Kachel eines Rings sein muss, und prüfen deshalb pro Ring nur diese beiden geschlossenen Formeln.
Sei Ring \(k\) die hexagonale Schicht im Abstand \(k\) vom Zentrum. Ring 0 besteht nur aus der Kachel 1, und Ring \(k\ge 1\) enthält \(6k\) Kacheln.
Nach Abschluss von Ring \(k\) ist die Gesamtzahl der Kacheln gleich
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
Daraus folgen für die erste und die letzte Kachel von Ring \(k\)
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
Damit ist Ring \(k\) genau das Intervall \([A_k,B_k]\), und seine Länge beträgt
$$B_k-A_k+1=6k.$$
Diese beiden Randformeln sind die zentralen mathematischen Objekte der gesamten Lösung.
Betrachte eine Kachel \(n\) in Ring \(k\ge 2\), die weder \(A_k\) noch \(B_k\) ist. Ihre beiden Nachbarn auf demselben Ring sind dann die aufeinanderfolgenden Werte \(n-1\) und \(n+1\). Zwei der sechs Nachbardifferenzen sind also bereits \(1\) und \(1\), also nicht prim.
Die vier übrigen Nachbarn liegen auf dem inneren beziehungsweise äußeren Nachbarring. Entlang einer Ringseite treten diese Ring-zu-Ring-Differenzen in zwei aufeinanderfolgenden Paaren auf, und jedes solche Paar enthält eine gerade Zahl. Daher sind unter diesen vier zusätzlichen Differenzen mindestens zwei gerade und größer als 2, also zusammengesetzt.
Folglich kann jede Nicht-Randkachel höchstens zwei Primdifferenzen besitzen. Sobald die kleinen Sonderfälle getrennt behandelt sind, bleiben nur noch die beiden Endkacheln jedes Rings als Kandidaten übrig: die erste Kachel \(A_k\) und die letzte Kachel \(B_k\).
Für \(k\ge 2\) lassen sich die sechs Nachbarn von \(A_k\) über benachbarte Ringenden ausdrücken:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
Daraus ergeben sich die sechs absoluten Differenzen
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
Davon sind \(1\), \(6k-6\) und \(6k\) für \(k\ge 2\) automatisch nicht prim. Somit bleibt genau die Bedingung
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
Für den anderen Randpunkt \(B_k\) sind die sechs Nachbarn
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
Die zugehörigen absoluten Differenzen sind
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
Wieder sind \(1\), \(6k\) und \(6k+6\) sicher zusammengesetzt, also gilt
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
Für \(k=2\) sind die letzten beiden Ausdrücke beide gleich 17. Dieselbe Primzahldifferenz entsteht dort also zu zwei verschiedenen Nachbarn, was genau erklärt, warum \(B_2=19\) ein Treffer ist.
Der zweite Ring beginnt bei \(A_2=8\) und endet bei \(B_2=19\).
Für \(A_2=8\) lauten die sechs Differenzen
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
also sind \(11,13,29\) prim und damit \(PD(8)=3\).
Für \(B_2=19\) lauten die sechs Differenzen
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
weshalb die Primdifferenzen \(11,17,17\) sind und erneut \(PD(19)=3\) gilt.
Das passt genau zum Anfang der von den Implementierungen erzeugten Folge:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
Die Mittelkachel erfüllt \(PD(1)=3\), und Kachel 2 ist der zweite kleine Sonderfall. Danach reduziert sich die gesamte Suche auf ein Durchlaufen von \(k=2,3,4,\dots\) mit nur zwei Tests pro Ring.
Der erste Randpunkt \(A_k\) wird akzeptiert, wenn
$$6k-1,\ 6k+1,\ 12k+5$$
allesamt prim sind; dann lautet die Kachelzahl
$$A_k=3k(k-1)+2.$$
Der letzte Randpunkt \(B_k\) wird akzeptiert, wenn
$$6k-1,\ 6k+5,\ 12k-7$$
allesamt prim sind; dann lautet die Kachelzahl
$$B_k=3k(k+1)+1.$$
Genau diese Reduktion setzt der Code direkt um.
Die Implementierungen in C++, Python und Java speichern zuerst die beiden ersten gültigen Kacheln \(1\) und \(2\). Danach laufen sie über Ringindizes \(k\ge 2\). Weder ein Koordinatengitter noch eine Nachbarschaftstabelle noch eine explizite Spiralsimulation wird aufgebaut, weil die Herleitung das Problem bereits auf zwei Formelkandidaten pro Ring reduziert hat.
Pro Ring bildet die Implementierung zunächst \(6k-1\), weil dieser Ausdruck in beiden Tests vorkommt. Anschließend prüft sie die Dreifach-Primzahlbedingung für den ersten Randpunkt und speichert im Erfolgsfall \(3k(k-1)+2\). Danach folgt dieselbe Prüfung für den letzten Randpunkt; bei Erfolg wird \(3k(k+1)+1\) gespeichert.
Die drei Sprachversionen unterscheiden sich nur in der Primzahlroutine. Die C++-Implementierung verwendet modulare Multiplikation zusammen mit einem deterministischen Miller-Rabin-Test für 64-Bit-Eingaben, die Java-Implementierung nutzt Probedivision über Zahlen der Form \(6m\pm1\), und die Python-Implementierung delegiert den Primzahltest an eine Bibliotheksfunktion. Mathematisch prüfen alle drei exakt dieselben Formeln und stoppen, sobald der gewünschte Index erreicht ist.
Wenn die Suche bis Ring \(K\) geht, untersucht der Algorithmus genau zwei Kandidaten pro Ring und führt nur konstant viele arithmetische Operationen darum herum aus. Die Kandidatenerzeugung ist also \(O(K)\).
Die gesamte Laufzeit ist damit \(O(K\cdot P(K))\), wobei \(P(K)\) die Kosten eines Primzahltests für Zahlen der Größe \(O(K)\) bezeichnet. Mit Probedivision ergibt sich \(O(K\sqrt{K})\); mit deterministischem Miller-Rabin auf 64-Bit-Zahlen ist der Primzahltest in dieser Aufgabengröße praktisch konstant. Für das konkrete Project-Euler-Ziel bleibt die Suche in allen Versionen sehr klein.
Die Implementierungen halten die bisher gefundenen Treffer in einer Liste beziehungsweise einem Array, daher beträgt der zusätzliche Speicher \(O(T)\) für Zielindex \(T\). Für \(T=2000\) ist das vernachlässigbar.
Karolar, merkezdeki 1 numaralı karonun etrafında altıgensel halkalar halinde numaralandırılır. Bir \(n\) karosu için \(PD(n)\), \(n\) ile altı komşusu arasındaki mutlak farkların kaç tanesinin asal olduğunu gösterir. Amaç, \(PD(n)=3\) sağlayan 2000. karoyu bulmaktır.
Asıl önemli nokta şudur: çalışan uygulamalar bütün spirali açıkça kurmaz. Bunun yerine, küçük istisnalar olan \(1\) ve \(2\) dışında her çözümün bir halkanın ya ilk ya da son karosu olmak zorunda olduğunu kanıtlarlar ve her halka için yalnızca bu iki kapalı form adayı test ederler.
Merkezden uzaklığı \(k\) olan altıgensel katmana halka \(k\) diyelim. Halka 0 yalnızca 1 karosundan oluşur; \(k\ge 1\) için halka \(k\), \(6k\) karo içerir.
Halka \(k\) tamamlandığında toplam karo sayısı
$$1+6(1+2+\cdots+k)=1+3k(k+1)$$
olur. Buna göre halka \(k\)'nın ilk ve son karoları
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1$$
şeklindedir. Dolayısıyla halka \(k\), tam olarak \([A_k,B_k]\) aralığıdır ve uzunluğu
$$B_k-A_k+1=6k$$
olur. Çözümün her yerinde kullanılan temel nesneler bu iki uç formüldür.
\(k\ge 2\) olan bir halkada, \(A_k\) ve \(B_k\) dışındaki bir \(n\) karosunu ele alalım. Aynı halka üzerindeki iki komşusu bu durumda ardışık sayılar olan \(n-1\) ve \(n+1\)'dir. Böylece altı farktan ikisi daha baştan \(1\) ve \(1\) olur; bunlar asal değildir.
Kalan dört komşu iç ve dış komşu halkalarda bulunur. Spiral üzerinde aynı kenar boyunca bakıldığında bu halka-geçiş farkları ikişerli ardışık çiftler halinde gelir ve her böyle çiftin içinde bir tane çift sayı vardır. Bu yüzden o dört ek farkın en az ikisi 2'den büyük çift sayıdır; dolayısıyla bileşiktir.
Sonuç olarak halka uçlarında olmayan hiçbir karo üç asal farka ulaşamaz; en fazla iki tane asal fark üretebilir. Küçük özel durumları ayırdıktan sonra geriye yalnızca her halkanın iki uç karosu kalır: ilk karo \(A_k\) ve son karo \(B_k\).
\(k\ge 2\) için \(A_k\)'nın altı komşusu yakın halka uçları cinsinden şöyle yazılabilir:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
Bunlardan çıkan altı mutlak fark
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5$$
olur. Bunların içinde \(1\), \(6k-6\) ve \(6k\), \(k\ge 2\) için zaten asal değildir. Bu yüzden koşul tam olarak şu üç sayıya iner:
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
Diğer uç nokta olan \(B_k\) için altı komşu
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}$$
şeklindedir. Buna karşılık gelen altı mutlak fark ise
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6$$
olur. Yine \(1\), \(6k\) ve \(6k+6\) kesin olarak bileşiktir; dolayısıyla
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
\(k=2\) durumunda son iki ifade de 17 olur. Aynı asal fark iki farklı komşudan geldiği için \(B_2=19\) yine geçerli bir çözümdür.
İkinci halka \(A_2=8\) ile başlar ve \(B_2=19\) ile biter.
\(A_2=8\) için altı fark
$$1,\ 6,\ 11,\ 12,\ 13,\ 29$$
olur; dolayısıyla asal olanlar \(11,13,29\)'dur ve \(PD(8)=3\) elde edilir.
\(B_2=19\) için altı fark
$$1,\ 11,\ 12,\ 17,\ 17,\ 18$$
olur; burada asal farklar \(11,17,17\)'dir ve yine \(PD(19)=3\) çıkar.
Bu, uygulamaların ürettiği dizinin başlangıcıyla tam olarak uyuşur:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
Merkez karo için \(PD(1)=3\) sağlanır; karo 2 de ikinci küçük istisnadır. Bundan sonra bütün arama, \(k=2,3,4,\dots\) üzerinde ilerleyen ve her halkada sadece iki test yapan bir taramaya dönüşür.
İlk uç nokta \(A_k\),
$$6k-1,\ 6k+1,\ 12k+5$$
sayılarının tümü asal olduğunda kabul edilir; bu durumda karo numarası
$$A_k=3k(k-1)+2$$
olur. Son uç nokta \(B_k\) ise
$$6k-1,\ 6k+5,\ 12k-7$$
sayılarının tümü asal olduğunda kabul edilir; bu durumda karo numarası
$$B_k=3k(k+1)+1$$
olur. Kodun yaptığı matematiksel indirgeme tam olarak budur.
C++, Python ve Java uygulamaları önce geçerli ilk iki karoyu, yani \(1\) ve \(2\)'yi saklar. Sonra \(k\ge 2\) halka indeksleri üzerinde döngü kurarlar. Koordinat ızgarası, komşuluk tablosu ya da açık bir spiral simülasyonu oluşturulmaz; çünkü yukarıdaki türetim problemi zaten halka başına iki açık form adaya indirmiştir.
Her halka için uygulama önce \(6k-1\) ifadesini hesaplar; çünkü bu değer iki uç testinde de ortaktır. Sonra ilk uç nokta için üç asal koşulunu kontrol eder ve başarılıysa \(3k(k-1)+2\) değerini kaydeder. Ardından son uç nokta için üç asal koşulunu dener ve başarılıysa \(3k(k+1)+1\) değerini kaydeder.
Üç dil sürümü yalnızca asal testi bakımından ayrılır. C++ uygulaması modüler çarpma ile birlikte 64 bit girişler için deterministik Miller-Rabin kullanır, Java uygulaması \(6m\pm1\) biçimindeki bölenler üzerinden deneme bölmesi yapar, Python uygulaması ise asal kontrolünü bir kütüphane yordamına bırakır. Üçü de aynı formülleri uygular ve istenen sıraya ulaşır ulaşmaz durur.
Arama halka \(K\)'ya kadar gidiyorsa algoritma halka başına tam iki aday inceler ve bunların etrafında yalnızca sabit sayıda aritmetik işlem yapar. Bu nedenle aday üretimi \(O(K)\) olur.
Toplam çalışma süresi \(O(K\cdot P(K))\)'dir; burada \(P(K)\), büyüklüğü \(O(K)\) olan sayılar üzerindeki tek bir asal testinin maliyetidir. Deneme bölmesiyle bu \(O(K\sqrt{K})\) verir; 64 bit aralıkta deterministik Miller-Rabin kullanıldığında ise bu problem ölçeğinde asal testi pratik olarak sabit zamanlı davranır. Project Euler girdisi için tarama çok küçüktür.
Uygulamalar bulunan başarılı karoları bir liste ya da dizi içinde tuttuğu için ek bellek maliyeti hedef sıra \(T\) için \(O(T)\)'dir. \(T=2000\) için bu ihmal edilebilir düzeydedir.
Las fichas se numeran en capas hexagonales alrededor de la ficha central 1. Para una ficha \(n\), \(PD(n)\) es la cantidad de valores primos entre las seis diferencias absolutas entre \(n\) y sus seis vecinas. La tarea consiste en encontrar la ficha número 2000 para la cual \(PD(n)=3\).
La idea decisiva es que las implementaciones correctas nunca construyen toda la espiral de forma explícita. Demuestran que, salvo los pequeños casos excepcionales \(1\) y \(2\), toda solución debe ser la primera o la última ficha de algún anillo, y por eso solo prueban esos dos candidatos en forma cerrada por anillo.
Llamemos anillo \(k\) a la capa hexagonal situada a distancia \(k\) del centro. El anillo 0 contiene únicamente la ficha 1, y el anillo \(k\ge 1\) contiene \(6k\) fichas.
Al terminar el anillo \(k\), el número total de fichas es
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
Por tanto, la primera y la última ficha del anillo \(k\) son
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
Así, el anillo \(k\) es exactamente el intervalo \([A_k,B_k]\), y su tamaño es
$$B_k-A_k+1=6k.$$
Estas dos fórmulas de borde son los objetos básicos de toda la solución.
Tomemos una ficha \(n\) del anillo \(k\ge 2\) que no sea uno de los dos extremos \(A_k\) o \(B_k\). Sus dos vecinas del mismo anillo son entonces los valores consecutivos \(n-1\) y \(n+1\), de modo que dos de las seis diferencias ya son \(1\) y \(1\), que no son primas.
Las otras cuatro vecinas pertenecen a los anillos interior y exterior adyacentes. A lo largo de un mismo lado de la espiral, esas diferencias entre anillos aparecen en dos pares consecutivos, y cada uno de esos pares contiene un número par. Por ello, entre esas cuatro diferencias adicionales hay al menos dos números pares mayores que 2, y por tanto compuestos.
En consecuencia, cualquier ficha que no sea un extremo del anillo puede tener como máximo dos diferencias primas. Una vez separados los casos pequeños, solo quedan como candidatos los dos extremos de cada anillo: la primera ficha \(A_k\) y la última ficha \(B_k\).
Para \(k\ge 2\), las seis vecinas de \(A_k\) pueden describirse mediante extremos de anillos cercanos:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
Al restarlas de \(A_k\), obtenemos las seis diferencias absolutas
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
Aquí, \(1\), \(6k-6\) y \(6k\) son automáticamente no primos cuando \(k\ge 2\). Por eso la condición se reduce exactamente a
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
Para el otro extremo \(B_k\), las seis vecinas son
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
Esto produce las seis diferencias absolutas
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
De nuevo, \(1\), \(6k\) y \(6k+6\) son compuestos seguros para \(k\ge 2\). Luego
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
Cuando \(k=2\), las dos últimas expresiones valen 17. La misma diferencia prima aparece entonces con dos vecinas distintas, y precisamente por eso \(B_2=19\) también es válido.
El segundo anillo comienza en \(A_2=8\) y termina en \(B_2=19\).
Para \(A_2=8\), las seis diferencias son
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
de modo que las primas son \(11,13,29\), y por tanto \(PD(8)=3\).
Para \(B_2=19\), las seis diferencias son
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
así que las diferencias primas son \(11,17,17\), y nuevamente \(PD(19)=3\).
Esto coincide con el comienzo de la sucesión generada por las implementaciones:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
La ficha central cumple \(PD(1)=3\), y la ficha 2 es el otro caso pequeño excepcional. A partir de ahí, toda la búsqueda se convierte en recorrer \(k=2,3,4,\dots\) realizando solo dos pruebas por anillo.
El primer extremo \(A_k\) se acepta cuando
$$6k-1,\ 6k+1,\ 12k+5$$
son primos; en ese caso la ficha es
$$A_k=3k(k-1)+2.$$
El último extremo \(B_k\) se acepta cuando
$$6k-1,\ 6k+5,\ 12k-7$$
son primos; en ese caso la ficha es
$$B_k=3k(k+1)+1.$$
Esa es exactamente la reducción matemática que usa el código.
Las implementaciones en C++, Python y Java comienzan almacenando las dos primeras fichas válidas, \(1\) y \(2\). Luego iteran sobre índices de anillo \(k\ge 2\). No construyen coordenadas para toda la rejilla, ni una tabla de adyacencias, ni una simulación explícita de la espiral, porque la derivación anterior ya reduce el problema a dos candidatos por anillo.
En cada anillo, la implementación calcula primero \(6k-1\), ya que ese valor aparece en ambas condiciones. Después comprueba la condición de tres primos para el primer extremo y, si se cumple, añade \(3k(k-1)+2\). A continuación comprueba la condición correspondiente para el último extremo y, si se cumple, añade \(3k(k+1)+1\).
Las tres versiones difieren solo en la rutina de primalidad. La implementación en C++ usa multiplicación modular y un test determinista de Miller-Rabin para enteros de 64 bits, la versión en Java usa división de prueba sobre números de la forma \(6m\pm1\), y la versión en Python delega el test de primalidad en un predicado de biblioteca. Matemáticamente, las tres aplican los mismos filtros y se detienen en cuanto alcanzan el índice pedido.
Si la búsqueda alcanza el anillo \(K\), el algoritmo examina exactamente dos candidatas por anillo y realiza solo una cantidad constante de aritmética alrededor de ellas. Por tanto, la generación de candidatas es \(O(K)\).
El tiempo total es \(O(K\cdot P(K))\), donde \(P(K)\) es el costo de una prueba de primalidad sobre números de tamaño \(O(K)\). Con división de prueba, esto da \(O(K\sqrt{K})\); con Miller-Rabin determinista en 64 bits, el costo de primalidad es efectivamente constante a esta escala. En la práctica, la búsqueda necesaria para el objetivo de Project Euler es pequeña.
Las implementaciones guardan las fichas válidas encontradas hasta el momento en una lista o arreglo, de modo que el espacio auxiliar es \(O(T)\) para objetivo \(T\). Para \(T=2000\), ese espacio es despreciable.
题目把图块按六边形螺旋方式围绕中心的 1 号图块编号。对任意图块 \(n\)，\(PD(n)\) 表示它与六个相邻图块之间的六个绝对差值中，有多少个是素数。目标是找出满足 \(PD(n)=3\) 的第 2000 个图块。
真正高效的关键不在于模拟整张网格，而在于先把几何结构压缩成闭式公式。三个实现都利用同一个事实：除去很小的特例 \(1\) 和 \(2\) 之外，所有满足条件的图块都必须出现在某一圈的起点或终点，因此每一圈只需要检查两个候选值。
把距离中心为 \(k\) 的六边形层称为第 \(k\) 圈。第 0 圈只有图块 1；当 \(k\ge 1\) 时，第 \(k\) 圈恰好有 \(6k\) 个图块。
走完第 \(k\) 圈以后，图块总数为
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
因此，第 \(k\) 圈的起始图块与结束图块分别是
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
也就是说，第 \(k\) 圈正好对应整数区间 \([A_k,B_k]\)，而它的长度就是
$$B_k-A_k+1=6k.$$
后面的所有推导都围绕这两个端点公式展开。
先看第 \(k\ge 2\) 圈中的某个图块 \(n\)，并且假设它既不是起点 \(A_k\)，也不是终点 \(B_k\)。那么它在同一圈上的两个邻居就是连续整数 \(n-1\) 与 \(n+1\)，所以六个邻居差值里已经有两个固定为 \(1\) 和 \(1\)。由于 1 不是素数，这两项一开始就无法贡献给 \(PD(n)\)。
剩下的四个邻居分别落在相邻的内圈和外圈。沿着螺旋的一条边观察，这些跨圈差值总是以两个“连续对”的形式出现，而每一个连续对里一定有一个偶数。于是这四个额外差值中至少有两个是大于 2 的偶数，因此必为合数。
这样一来，任何不是圈端点的图块至多只能得到两个素数差值，不可能达到 \(PD(n)=3\)。所以，把小特例单独处理以后，真正可能成功的只剩下每一圈的两个端点：起始图块 \(A_k\) 与结束图块 \(B_k\)。
对 \(k\ge 2\)，\(A_k\) 的六个邻居可以直接用相邻各圈的端点表示为
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
把它们与 \(A_k\) 做绝对差，就得到
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
其中 \(1\)、\(6k-6\)、\(6k\) 在 \(k\ge 2\) 时显然都不是素数，因此条件完全压缩为三个数：
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
对另一个端点 \(B_k\)，六个邻居为
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
于是六个绝对差变成
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
同样地，\(1\)、\(6k\)、\(6k+6\) 一定是合数，所以
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
当 \(k=2\) 时，后两个表达式都等于 17，也就是说相同的素数差值会从两个不同邻居处出现。这仍然会贡献两个素数差，因此 \(B_2=19\) 依旧满足条件。
第二圈从 \(A_2=8\) 开始，到 \(B_2=19\) 结束。
对 \(A_2=8\)，六个差值是
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
其中素数差为 \(11,13,29\)，所以 \(PD(8)=3\)。
对 \(B_2=19\)，六个差值是
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
其中素数差为 \(11,17,17\)，因此 \(PD(19)=3\)。
这正好对应实现中产生序列的开头：
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
中心图块满足 \(PD(1)=3\)，而图块 2 是另一个小规模特例。从这里开始，整个问题就变成遍历 \(k=2,3,4,\dots\)，并且每一圈只做两次判断。
当
$$6k-1,\ 6k+1,\ 12k+5$$
全部为素数时，接受第一个端点，其图块编号为
$$A_k=3k(k-1)+2.$$
当
$$6k-1,\ 6k+5,\ 12k-7$$
全部为素数时，接受最后一个端点，其图块编号为
$$B_k=3k(k+1)+1.$$
实现代码所做的数学工作，本质上就只有这一层筛选。
C++、Python 和 Java 三个实现都会先把前两个有效图块 \(1\) 与 \(2\) 放入结果表，然后从 \(k\ge 2\) 开始逐圈扫描。它们不会建立整张六边形坐标网格，也不会显式存储邻接关系，因为上面的推导已经把问题压缩成“每圈两个候选值”。
在每一圈里，程序先计算 \(6k-1\)，因为它同时出现在两个端点条件中。随后检查起始端点的三个素数条件，若通过就记录 \(3k(k-1)+2\)。再检查末尾端点的三个素数条件，若通过就记录 \(3k(k+1)+1\)。
三种语言版本的差别只在素性测试上。C++ 版本使用模乘和 64 位范围内的确定性 Miller-Rabin；Java 版本使用针对 \(6m\pm1\) 形式的试除；Python 版本把素性判断交给库函数。虽然实现细节不同，但三者应用的是完全相同的环端点公式，并在达到目标下标后立即停止。
如果搜索推进到第 \(K\) 圈，那么算法每圈只检查两个候选图块，并进行常数次算术运算。因此候选生成部分是 \(O(K)\)。
总时间复杂度可写成 \(O(K\cdot P(K))\)，其中 \(P(K)\) 表示对规模为 \(O(K)\) 的整数做一次素性测试的代价。若使用试除法，则得到 \(O(K\sqrt{K})\)；若使用 64 位范围内的确定性 Miller-Rabin，则在本题规模上素性测试几乎可以视为常数时间。对 Project Euler 的目标输入而言，这个搜索范围相当小。
实现会把已经找到的有效图块保存在列表或数组中，因此辅助空间是关于目标序号 \(T\) 的 \(O(T)\)。当 \(T=2000\) 时，这部分空间开销可以忽略不计。
Плитки нумеруются по спирали в шестиугольных слоях вокруг центральной плитки 1. Для плитки \(n\) величина \(PD(n)\) означает, сколько из шести абсолютных разностей между \(n\) и его соседями являются простыми числами. Требуется найти 2000-ю плитку, для которой \(PD(n)=3\).
Главная идея состоит в том, что эффективные реализации вообще не строят всю спираль целиком. Они доказывают, что кроме малых исключений \(1\) и \(2\), любое подходящее значение обязано быть либо первой, либо последней плиткой некоторого кольца, а значит на каждом кольце нужно проверять только два явных кандидата.
Назовем кольцом \(k\) шестиугольный слой на расстоянии \(k\) от центра. Кольцо 0 состоит только из плитки 1, а кольцо \(k\ge 1\) содержит \(6k\) плиток.
После завершения кольца \(k\) общее количество плиток равно
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
Отсюда первая и последняя плитки кольца \(k\) задаются формулами
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
Следовательно, кольцо \(k\) есть ровно интервал \([A_k,B_k]\), а его длина равна
$$B_k-A_k+1=6k.$$
Именно эти две формулы для концов кольца используются далее во всей задаче.
Рассмотрим плитку \(n\) в кольце \(k\ge 2\), которая не является ни \(A_k\), ни \(B_k\). Тогда ее два соседа на том же кольце имеют значения \(n-1\) и \(n+1\). Значит, две из шести разностей уже равны \(1\) и \(1\), а единица не является простым числом.
Оставшиеся четыре соседа лежат на соседних внутреннем и внешнем кольцах. Вдоль одной стороны спирали такие межкольцевые разности образуют две пары последовательных чисел, а в каждой такой паре обязательно есть четное число. Поэтому среди этих четырех дополнительных разностей как минимум две являются четными и больше 2, то есть составными.
Отсюда следует, что любая плитка, не являющаяся концом кольца, может иметь не более двух простых разностей. После отделения малых особых случаев остаются только два кандидата на каждом кольце: первая плитка \(A_k\) и последняя плитка \(B_k\).
Для \(k\ge 2\) шесть соседей \(A_k\) удобно записать через концы соседних колец:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
Тогда шесть абсолютных разностей равны
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
Числа \(1\), \(6k-6\) и \(6k\) при \(k\ge 2\) заведомо не простые. Поэтому условие сводится ровно к трем значениям:
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
Для другого конца \(B_k\) шесть соседей имеют вид
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
Отсюда получаются разности
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
Снова \(1\), \(6k\) и \(6k+6\) гарантированно составные, поэтому
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
При \(k=2\) два последних выражения совпадают и равны 17. Одна и та же простая разность появляется у двух разных соседей, и именно поэтому \(B_2=19\) тоже подходит.
Второе кольцо начинается с \(A_2=8\) и заканчивается на \(B_2=19\).
Для \(A_2=8\) шесть разностей равны
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
поэтому простыми являются \(11,13,29\), и значит \(PD(8)=3\).
Для \(B_2=19\) шесть разностей равны
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
так что простые разности здесь \(11,17,17\), и снова получаем \(PD(19)=3\).
Это точно совпадает с началом последовательности, которую строят реализации:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
Центральная плитка удовлетворяет \(PD(1)=3\), а плитка 2 является вторым малым исключением. После этого вся задача сводится к перебору \(k=2,3,4,\dots\) и к двум проверкам на каждом кольце.
Первый конец \(A_k\) принимается, если
$$6k-1,\ 6k+1,\ 12k+5$$
простые; тогда номер плитки равен
$$A_k=3k(k-1)+2.$$
Последний конец \(B_k\) принимается, если
$$6k-1,\ 6k+5,\ 12k-7$$
простые; тогда номер плитки равен
$$B_k=3k(k+1)+1.$$
Это и есть вся математическая редукция, лежащая в основе кода.
Реализации на C++, Python и Java сначала сохраняют две первые подходящие плитки, \(1\) и \(2\). Затем они перебирают индексы колец \(k\ge 2\). Никакая полная координатная модель решетки, таблица соседей или явная симуляция спирали не строится, потому что изложенное выше рассуждение уже сократило задачу до двух кандидатов на кольцо.
Для каждого кольца программа сначала вычисляет \(6k-1\), так как этот множитель участвует в обоих тестах. Затем проверяется условие трех простых чисел для первого конца; если оно выполнено, добавляется \(3k(k-1)+2\). После этого проверяется условие для последнего конца; если оно выполнено, добавляется \(3k(k+1)+1\).
Различия между тремя языками касаются только проверки на простоту. В C++ используется модульное умножение и детерминированный тест Миллера-Рабина для 64-битных целых, в Java применяется пробное деление по числам вида \(6m\pm1\), а в Python проверка простоты передается библиотечной функции. С математической точки зрения все три версии делают одно и то же и останавливаются сразу после достижения нужного индекса.
Если поиск доходит до кольца \(K\), алгоритм рассматривает ровно два кандидата на кольцо и выполняет только постоянное число арифметических операций вокруг них. Значит, генерация кандидатов имеет сложность \(O(K)\).
Полное время работы равно \(O(K\cdot P(K))\), где \(P(K)\) обозначает стоимость одной проверки простоты для чисел размера \(O(K)\). При пробном делении это дает \(O(K\sqrt{K})\); при детерминированном Миллере-Рабине на 64-битном диапазоне стоимость проверки на простоту на практике почти постоянна. Для входа Project Euler требуемый поиск очень мал.
Реализации хранят найденные подходящие плитки в списке или массиве, поэтому дополнительная память равна \(O(T)\) для целевого индекса \(T\). При \(T=2000\) этот объем ничтожен.
تُرقَّم البلاطات على شكل طبقات سداسية حول البلاطة المركزية 1. وبالنسبة إلى البلاطة \(n\)، فإن \(PD(n)\) هو عدد القيم الأولية بين الفروق المطلقة الستة بين \(n\) وبين جيرانه الستة. المطلوب هو إيجاد البلاطة رقم 2000 التي تحقق \(PD(n)=3\).
الفكرة الحاسمة هي أن التطبيقات الصحيحة لا تبني الحلزون كاملًا. فهي تثبت أن كل حل، باستثناء الحالتين الصغيرتين \(1\) و\(2\)، لا بد أن يكون إما أول بلاطة في حلقة ما أو آخر بلاطة فيها، ولهذا يكفي فحص مرشحين فقط لكل حلقة بصيغ مغلقة.
لنسَمِّ الحلقة \(k\) الطبقة السداسية التي تبعد مسافة \(k\) عن المركز. الحلقة 0 تتكون من البلاطة 1 فقط، أما الحلقة \(k\ge 1\) فتحتوي على \(6k\) بلاطات.
بعد إكمال الحلقة \(k\)، يصبح العدد الكلي للبلاطات
$$1+6(1+2+\cdots+k)=1+3k(k+1).$$
ومن ثم فإن أول وآخر بلاطة في الحلقة \(k\) هما
$$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$$
أي إن الحلقة \(k\) هي بالضبط الفترة \([A_k,B_k]\)، وطولها يساوي
$$B_k-A_k+1=6k.$$
هاتان الصيغتان للطرفين هما الأساس الذي تُبنى عليه بقية البرهنة.
خذ بلاطة \(n\) في الحلقة \(k\ge 2\) بشرط ألا تكون \(A_k\) ولا \(B_k\). عندها يكون جاراها على الحلقة نفسها هما العددين المتتاليين \(n-1\) و\(n+1\)، وبالتالي فاثنان من الفروق الستة يساويان \(1\) و\(1\)، والواحد ليس عددًا أوليًا.
أما الجيران الأربعة الآخرون فيقعون على الحلقتين الداخلية والخارجية المجاورتين. وعلى امتداد ضلع واحد من الحلزون، تظهر فروق الانتقال بين الحلقات على شكل زوجين من أعداد متتالية، وكل زوج من هذا النوع يحتوي بالضرورة على عدد زوجي. لذلك يوجد بين هذه الفروق الأربعة على الأقل عددان زوجيان أكبر من 2، أي إنهما عددان مركبان.
إذن أي بلاطة ليست من طرفي الحلقة لا يمكن أن تمتلك أكثر من فرقين أوليين. وبعد فصل الحالات الصغيرة الخاصة، يبقى فقط طرفا كل حلقة كمرشحين محتملين: البلاطة الأولى \(A_k\) والبلاطة الأخيرة \(B_k\).
عندما \(k\ge 2\)، يمكن كتابة الجيران الستة للبلاطة \(A_k\) بدلالة أطراف الحلقات المجاورة:
$$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$$
وبأخذ الفروق المطلقة مع \(A_k\) نحصل على
$$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$$
ومن بين هذه القيم، تكون \(1\) و\(6k-6\) و\(6k\) غير أولية حتمًا عندما \(k\ge 2\). ولهذا يختزل الشرط إلى ثلاثة أعداد فقط:
$$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$$
أما الطرف الآخر \(B_k\)، فجيرانه الستة هم
$$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$$
ومن ثم تصبح الفروق المطلقة
$$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$$
ومرة أخرى، فإن \(1\) و\(6k\) و\(6k+6\) أعداد مركبة بالتأكيد، لذلك
$$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$$
وعند \(k=2\) يتساوى الحدّان الأخيران ويصبحان 17. أي إن الفرق الأولي نفسه يظهر مع جارين مختلفين، وهذا بالضبط ما يجعل \(B_2=19\) صالحًا.
تبدأ الحلقة الثانية عند \(A_2=8\) وتنتهي عند \(B_2=19\).
بالنسبة إلى \(A_2=8\)، تكون الفروق الستة
$$1,\ 6,\ 11,\ 12,\ 13,\ 29,$$
ومن ثم تكون الفروق الأولية هي \(11,13,29\)، وبالتالي \(PD(8)=3\).
وبالنسبة إلى \(B_2=19\)، تكون الفروق الستة
$$1,\ 11,\ 12,\ 17,\ 17,\ 18,$$
فتكون الفروق الأولية \(11,17,17\)، ونحصل مرة أخرى على \(PD(19)=3\).
وهذا يطابق بداية المتتالية التي تولدها التطبيقات:
$$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$$
البلاطة المركزية تحقق \(PD(1)=3\)، والبلاطة 2 هي الحالة الصغيرة الخاصة الأخرى. بعد ذلك، تتحول المسألة كلها إلى مسح القيم \(k=2,3,4,\dots\) مع اختبارين فقط في كل حلقة.
يُقبل الطرف الأول \(A_k\) عندما تكون
$$6k-1,\ 6k+1,\ 12k+5$$
كلها أولية، وعندئذ يكون رقم البلاطة
$$A_k=3k(k-1)+2.$$
ويُقبل الطرف الأخير \(B_k\) عندما تكون
$$6k-1,\ 6k+5,\ 12k-7$$
كلها أولية، وعندئذ يكون رقم البلاطة
$$B_k=3k(k+1)+1.$$
وهذا هو تمامًا الاختزال الرياضي الذي تجسده الشيفرة.
تبدأ تطبيقات C++ وPython وJava بحفظ أول بلاطتين صحيحتين، وهما \(1\) و\(2\). بعد ذلك تنتقل إلى الحلقات ذات الفهارس \(k\ge 2\). لا تُبنى شبكة إحداثيات كاملة ولا جدول مجاورة ولا محاكاة صريحة للحلزون، لأن الاشتقاق السابق اختزل المسألة سلفًا إلى مرشحين اثنين لكل حلقة.
في كل حلقة، تحسب الشيفرة أولًا القيمة \(6k-1\) لأنها تظهر في الشرطين معًا. ثم تفحص شرط الأعداد الأولية الثلاثة للطرف الأول، فإذا تحقق أضافت \(3k(k-1)+2\). وبعد ذلك تفحص الشرط المناظر للطرف الأخير، فإذا تحقق أضافت \(3k(k+1)+1\).
الاختلاف بين النسخ الثلاث يقع فقط في اختبار الأولية. إصدار C++ يستخدم الضرب المعياري مع اختبار Miller-Rabin حتمي لأعداد 64-بت، وإصدار Java يستخدم القسمة التجريبية على الأعداد من الشكل \(6m\pm1\)، أما إصدار Python فيفوّض اختبار الأولية إلى دالة مكتبية. لكن من حيث الجوهر الرياضي فهي جميعًا تطبق الصيغ نفسها وتتوقف بمجرد الوصول إلى الفهرس المطلوب.
إذا امتد البحث حتى الحلقة \(K\)، فإن الخوارزمية تفحص مرشحين اثنين فقط لكل حلقة وتنفذ عددًا ثابتًا من العمليات الحسابية حولهما. لذلك فإن توليد المرشحين نفسه يملك تعقيدًا \(O(K)\).
أما الزمن الكلي فهو \(O(K\cdot P(K))\)، حيث تمثل \(P(K)\) كلفة اختبار أولية واحد على أعداد بحجم \(O(K)\). ومع القسمة التجريبية يصبح ذلك \(O(K\sqrt{K})\)، أما مع Miller-Rabin الحتمي ضمن مجال 64-بت فتكون كلفة اختبار الأولية شبه ثابتة عمليًا لهذا الحجم من المدخلات. وفي مسألة Project Euler يبقى مدى البحث صغيرًا جدًا.
وتحفظ التطبيقات البلاطات الصحيحة التي عُثر عليها في قائمة أو مصفوفة، لذا فإن الذاكرة الإضافية هي \(O(T)\) عندما يكون الهدف هو الفهرس \(T\). وبالنسبة إلى \(T=2000\)، فهذه الكلفة مهملة.