For even \(k\ge 2\), let \(D(k)\) be the denominator of the Bernoulli number \(B_k\) written in lowest terms. Define \(F(n)\) as the \(n\)-th positive integer \(k\) for which
$$D(k)=20010.$$
The goal is to compute \(F(10^5)\). The crucial observation is that the problem does not require explicit Bernoulli-number arithmetic: only the prime divisibility pattern of \(k\) matters.
The three implementations turn the denominator condition into a sieve over multipliers of a mandatory base value.
For every even \(k\), the denominator of \(B_k\) is
$$D(k)=\prod_{p-1\mid k} p,$$
where the product runs over all primes \(p\) such that \(p-1\) divides \(k\). So the denominator is determined entirely by which values \(p-1\) occur as divisors of \(k\). Once this formula is used, the Bernoulli numbers themselves disappear from the computation.
The target denominator factors as
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
Therefore \(k\) must be divisible by the corresponding values
$$1,\ 2,\ 4,\ 22,\ 28,$$
because those are the numbers \(p-1\) attached to the required primes. The nontrivial conditions combine into
$$\operatorname{lcm}(2,4,22,28)=308.$$
Hence every admissible term has the form
$$k=308m,\qquad m\ge 1.$$
This guarantees that the primes \(2,3,5,23,29\) all appear in the denominator. The remaining work is to make sure that no other prime appears.
Take a prime \(p\notin\{2,3,5,23,29\}\). If \(p-1\mid k\), then \(p\) would also divide \(D(k)\), which is forbidden. Write
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
Since \(308=g\cdot \frac{308}{g}\), we have
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
Now remove the common factor between \(u\) and \(308/g\). Define
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
Then
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
So each unwanted prime produces a forbidden divisor \(r\): every multiple of \(r\) gives an invalid multiplier \(m\).
Every prime \(p>2\) is odd, so every value \(p-1\) is even. Therefore \(g=\gcd(p-1,308)\) can only be one of the even divisors of \(308\):
$$g\in\{2,4,14,22,28,44,154,308\}.$$
For a fixed \(g\), the candidate primes are exactly the numbers of the form
$$p=g\,u+1.$$
Instead of primality-testing each candidate separately, the implementations sieve directly in the \(u\)-space. For every small prime \(q\nmid g\), the congruence
$$g\,u+1\equiv 0 \pmod q$$
has the unique solution
$$u\equiv -g^{-1}\pmod q,$$
because \(g\) has a multiplicative inverse modulo \(q\). Every value in that arithmetic progression makes \(g\,u+1\) composite, so it can be crossed out. The sieve starts far enough along the progression that the prime \(q\) itself is not accidentally removed when \(g\,u+1=q\).
After the sieve for a fixed \(g\), every surviving \(u\) gives a prime \(p=g\,u+1\). Each such prime is translated into its forbidden divisor \(r\), and all multiples of \(r\) are marked in a second sieve over the multiplier axis. If the unmarked multipliers are
$$m_1<m_2<m_3<\dots,$$
then the required sequence is simply
$$F(n)=308m_n.$$
The smallest multiplier is \(m=1\), so \(k=308\). The divisors of \(308\) are
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
Among these, the values \(d\) for which \(d+1\) is prime are \(1,2,4,22,28\), yielding
$$2,3,5,23,29.$$
Therefore
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
so \(308\) is valid. In contrast, if \(m=2\), then \(k=616\), and \(617\) is prime with \(617-1=616\mid k\). That extra prime would appear in the denominator, so \(616\) is invalid. A second useful example is \(p=67\): here \(67-1=66\), \(\gcd(66,308)=22\), so \(u=3\) and \(308/22=14\). Thus
$$r=\frac{3}{\gcd(3,14)}=3,$$
which means every multiple of \(3\) is invalid. The implementations also verify the checkpoint
$$F(10)=96404.$$
The C++, Python, and Java implementations share the same structure. They first build a small-prime table up to \(\sqrt{308X+1}\), where \(X\) is the current search bound on the multipliers. That table supports both the tiny validation checks and the arithmetic-form sieves that generate primes of the form \(g\,u+1\).
For each even divisor \(g\) of \(308\), the implementation allocates a boolean array indexed by \(u=1,2,\dots,X\). Using each small prime \(q\) that does not divide \(g\), it computes the unique residue class modulo \(q\) for which \(g\,u+1\) is divisible by \(q\), then clears that whole progression. Any index that survives corresponds to a prime candidate \(g\,u+1\). The required primes \(2,3,5,23,29\) are skipped, while every other surviving prime is converted into a forbidden divisor of the multiplier.
A second sieve marks every multiple of every forbidden divisor. Scanning the multiplier array from left to right then produces the admissible values in increasing order. If the requested index has not yet been reached, the search bound is doubled and the process is repeated. The implementations also include small consistency checks such as \(D(4)=30\), \(D(308)=20010\), and \(F(10)=96404\).
Let \(X\) be the search bound on the multipliers \(m\). Building the prime table up to \(\sqrt{308X+1}\) costs \(O(\sqrt{X}\log\log X)\) time and \(O(\sqrt{X})\) memory. The eight arithmetic-form sieves over \(u\) have total harmonic cost \(O(X\log\log X)\) up to a constant factor. The final multiple-marking phase costs
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
where \(R\) is the set of forbidden divisors discovered up to \(X\); in the worst case this is \(O(X\log X)\). Therefore the implemented method uses \(O(X)\) memory and worst-case time \(O(X\log X)\), while still being vastly faster in practice than recomputing Bernoulli denominators for every even \(k\).
Für gerade \(k\ge 2\) sei \(D(k)\) der Nenner der Bernoulli-Zahl \(B_k\) in vollständig gekürzter Form. Definiere \(F(n)\) als die \(n\)-te positive ganze Zahl \(k\) mit
$$D(k)=20010.$$
Gesucht ist also \(F(10^5)\). Der entscheidende Punkt ist, dass man die Bernoulli-Zahlen selbst nie ausrechnen muss; ausschlaggebend ist allein das Teilbarkeitsmuster von \(k\).
Die drei Implementierungen verwandeln die Nennerbedingung in ein Sieb über Multiplikatoren eines erzwungenen Grundwerts.
Für jedes gerade \(k\) gilt
$$D(k)=\prod_{p-1\mid k} p,$$
wobei das Produkt über alle Primzahlen \(p\) läuft, für die \(p-1\) ein Teiler von \(k\) ist. Der Nenner wird also vollständig dadurch bestimmt, welche Werte \(p-1\) in \(k\) aufgehen. Damit verschwindet die eigentliche Bernoulli-Arithmetik aus dem Problem.
Der Zielnenner zerfällt in
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
Daher muss \(k\) durch die zugehörigen Werte
$$1,\ 2,\ 4,\ 22,\ 28$$
teilbar sein, denn genau das sind die Zahlen \(p-1\) der geforderten Primzahlen. Die nichttrivialen Bedingungen lassen sich zusammenfassen zu
$$\operatorname{lcm}(2,4,22,28)=308.$$
Damit hat jedes zulässige Folgenglied die Form
$$k=308m,\qquad m\ge 1.$$
So ist bereits gesichert, dass die Primzahlen \(2,3,5,23,29\) im Nenner vorkommen. Jetzt muss nur noch verhindert werden, dass weitere Primzahlen hinzukommen.
Betrachte eine Primzahl \(p\notin\{2,3,5,23,29\}\). Falls \(p-1\mid k\), dann würde auch \(p\) den Nenner teilen, was nicht erlaubt ist. Schreibe
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
Da \(308=g\cdot \frac{308}{g}\) gilt, folgt
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
Nun entfernen wir den gemeinsamen Faktor von \(u\) und \(308/g\). Definiere
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
Dann ist
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
Jede unerwünschte Primzahl liefert also einen verbotenen Teiler \(r\): Jedes Vielfache von \(r\) macht den Multiplikator \(m\) ungültig.
Jede Primzahl \(p>2\) ist ungerade, also ist \(p-1\) stets gerade. Deshalb kann \(g=\gcd(p-1,308)\) nur ein gerader Teiler von \(308\) sein:
$$g\in\{2,4,14,22,28,44,154,308\}.$$
Für festes \(g\) haben die Kandidaten für Primzahlen genau die Form
$$p=g\,u+1.$$
Statt jede Zahl einzeln auf Primzahl zu testen, sieben die Implementierungen direkt im \(u\)-Raum. Für jede kleine Primzahl \(q\nmid g\) hat die Kongruenz
$$g\,u+1\equiv 0 \pmod q$$
die eindeutige Lösung
$$u\equiv -g^{-1}\pmod q,$$
weil \(g\) modulo \(q\) invertierbar ist. Alle Werte dieser arithmetischen Progression machen \(g\,u+1\) zusammengesetzt und können gestrichen werden. Das Sieb beginnt weit genug hinten, damit die Primzahl \(q\) selbst nicht versehentlich entfernt wird, wenn einmal \(g\,u+1=q\) gilt.
Nach dem Sieb für ein festes \(g\) liefert jedes übrig gebliebene \(u\) eine Primzahl \(p=g\,u+1\). Jede solche Primzahl wird in ihren verbotenen Teiler \(r\) übersetzt, und in einem zweiten Sieb werden alle Vielfachen von \(r\) auf der Multiplikatorachse markiert. Sind die unmarkierten Multiplikatoren
$$m_1<m_2<m_3<\dots,$$
dann ist die gesuchte Folge einfach
$$F(n)=308m_n.$$
Der kleinste Multiplikator ist \(m=1\), also \(k=308\). Die Teiler von \(308\) sind
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
Unter diesen sind genau diejenigen \(d\) interessant, für die \(d+1\) prim ist, also \(1,2,4,22,28\). Das ergibt die Primzahlen
$$2,3,5,23,29.$$
Folglich ist
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
also ist \(308\) gültig. Dagegen erhält man für \(m=2\) den Wert \(k=616\), und \(617\) ist prim mit \(617-1=616\mid k\). Diese zusätzliche Primzahl würde im Nenner erscheinen, also ist \(616\) ungültig. Ein zweites nützliches Beispiel ist \(p=67\): Dann ist \(67-1=66\), \(\gcd(66,308)=22\), also \(u=3\) und \(308/22=14\). Damit folgt
$$r=\frac{3}{\gcd(3,14)}=3,$$
und somit ist jedes Vielfache von \(3\) ungültig. Die Implementierungen prüfen außerdem den Kontrollwert
$$F(10)=96404.$$
Die Implementierungen in C++, Python und Java verwenden dieselbe Struktur. Zuerst erzeugen sie eine Liste kleiner Primzahlen bis \(\sqrt{308X+1}\), wobei \(X\) die aktuelle Suchgrenze für die Multiplikatoren ist. Diese Primzahlliste dient sowohl den kleinen Plausibilitätsprüfungen als auch den Sieben, die Primzahlen der Form \(g\,u+1\) erzeugen.
Für jeden geraden Teiler \(g\) von \(308\) wird ein boolesches Feld mit Indizes \(u=1,2,\dots,X\) angelegt. Mit jeder kleinen Primzahl \(q\), die \(g\) nicht teilt, wird diejenige Restklasse modulo \(q\) berechnet, für die \(g\,u+1\) durch \(q\) teilbar ist; anschließend wird diese ganze Progression gelöscht. Jeder überlebende Index entspricht damit einem Primzahlkandidaten \(g\,u+1\). Die benötigten Primzahlen \(2,3,5,23,29\) werden übersprungen, alle anderen überlebenden Primzahlen werden in verbotene Teiler des Multiplikators übersetzt.
Ein zweites Sieb markiert dann alle Vielfachen aller verbotenen Teiler. Ein Durchlauf von links nach rechts über das Multiplikatorfeld liefert die zulässigen Werte in aufsteigender Reihenfolge. Wenn der gewünschte Index noch nicht erreicht ist, wird die Suchgrenze verdoppelt und der Prozess wiederholt. Zusätzlich enthalten die Implementierungen kleine Konsistenztests wie \(D(4)=30\), \(D(308)=20010\) und \(F(10)=96404\).
Sei \(X\) die Suchgrenze für die Multiplikatoren \(m\). Das Erzeugen der Primzahlliste bis \(\sqrt{308X+1}\) kostet \(O(\sqrt{X}\log\log X)\) Zeit und \(O(\sqrt{X})\) Speicher. Die acht Siebe über arithmetische Formen im \(u\)-Raum haben zusammen harmonische Kosten von \(O(X\log\log X)\), abgesehen von einem konstanten Faktor. Die abschließende Markierung aller Vielfachen verbotener Teiler benötigt
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
wobei \(R\) die bis \(X\) gefundenen verbotenen Teiler bezeichnet; im schlechtesten Fall ist das \(O(X\log X)\). Damit benötigt das implementierte Verfahren \(O(X)\) Speicher und im Worst Case \(O(X\log X)\) Zeit, ist in der Praxis aber um Größenordnungen schneller als eine direkte Nennerberechnung für jedes gerade \(k\).
Çift \(k\ge 2\) için \(B_k\) Bernoulli sayısının sadeleştirilmiş paydasını \(D(k)\) ile gösterelim. \(D(k)=20010\) koşulunu sağlayan pozitif \(k\) değerlerini artan sırada dizip \(n\). elemana \(F(n)\) diyelim. Amaç,
$$F(10^5)$$
değerini bulmaktır. Buradaki temel nokta, Bernoulli sayılarını doğrudan hesaplamaya gerek olmamasıdır; yalnızca \(k\)'nın hangi \(p-1\) değerlerine bölündüğü önemlidir.
Üç implementasyon da payda koşulunu, zorunlu bir taban değerin katları üzerinde çalışan bir eleğe dönüştürür.
Her çift \(k\) için
$$D(k)=\prod_{p-1\mid k} p$$
eşitliği geçerlidir; burada çarpım, \(p-1\) değeri \(k\)'yı bölen tüm asal sayılar üzerindedir. Dolayısıyla payda tamamen hangi \(p-1\) değerlerinin \(k\)'yı böldüğüyle belirlenir. Bu noktadan sonra Bernoulli sayılarının kendisi hesaplamadan çıkar.
Hedef payda
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29$$
şeklinde ayrılır. O halde \(k\), ilgili
$$1,\ 2,\ 4,\ 22,\ 28$$
değerlerine bölünmelidir; çünkü istenen asallar için \(p-1\) tam olarak bunlardır. Önemsiz olmayan koşulların EKOK'u
$$\operatorname{lcm}(2,4,22,28)=308$$
olduğundan her uygun terim
$$k=308m,\qquad m\ge 1$$
biçimindedir. Bu sayede \(2,3,5,23,29\) asallarının paydada yer alması garanti edilir. Geriye başka hiçbir asalın eklenmemesini sağlamak kalır.
\(\{2,3,5,23,29\}\) dışında bir asal \(p\) alalım. Eğer \(p-1\mid k\) olursa, \(p\) de \(D(k)\)'ya girer ve hedef bozulur. Şöyle yazalım:
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
\(308=g\cdot \frac{308}{g}\) olduğundan
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m$$
olur. Şimdi \(u\) ile \(308/g\) arasındaki ortak çarpanı ayıralım ve
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}$$
tanımını yapalım. O zaman
$$u\mid \frac{308}{g}\,m \iff r\mid m$$
elde edilir. Yani her istenmeyen asal, \(m\) için yasak bir bölen \(r\) üretir; \(r\)'nin her katı geçersizdir.
\(p>2\) olan her asal tek olduğundan \(p-1\) daima çifttir. Bu yüzden \(g=\gcd(p-1,308)\), \(308\)'in yalnızca çift bölenlerinden biri olabilir:
$$g\in\{2,4,14,22,28,44,154,308\}.$$
Sabit bir \(g\) için asal adayları tam olarak
$$p=g\,u+1$$
şeklindedir. Her adayı tek tek test etmek yerine implementasyonlar doğrudan \(u\)-uzayında elek kurar. \(g\)'yi bölmeyen her küçük asal \(q\) için
$$g\,u+1\equiv 0 \pmod q$$
kongruansının tek çözümü
$$u\equiv -g^{-1}\pmod q$$
olur; çünkü \(g\), \(q\) modunda terslenebilir. Bu aritmetik dizideki tüm değerler \(g\,u+1\)'i bileşik yapar ve elenir. Eleğin başlangıcı, eğer bir yerde \(g\,u+1=q\) oluyorsa asal \(q\)'nun kendisinin yanlışlıkla silinmeyeceği kadar ileri seçilir.
Sabit bir \(g\) için elekten sağ çıkan her \(u\), bir asal \(p=g\,u+1\) verir. Her böyle asal ilgili yasak bölen \(r\)'ye çevrilir ve ikinci bir elekte \(r\)'nin tüm katları çarpan ekseninde işaretlenir. Eğer işaretlenmeyen çarpanlar
$$m_1<m_2<m_3<\dots$$
şeklindeyse, aranan dizi doğrudan
$$F(n)=308m_n$$
olur.
En küçük çarpan \(m=1\) olduğundan \(k=308\) elde edilir. \(308\)'in bölenleri
$$1,2,4,7,11,14,22,28,44,77,154,308$$
şeklindedir. Bunlar içinde \(d+1\) asal olanlar \(1,2,4,22,28\)'dir ve bunlar
$$2,3,5,23,29$$
asallarını verir. Dolayısıyla
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010$$
olur; yani \(308\) geçerlidir. Buna karşılık \(m=2\) için \(k=616\) elde edilir ve \(617\) asaldır; ayrıca \(617-1=616\mid k\). Bu ekstra asal paydaya gireceği için \(616\) geçersizdir. Bir başka faydalı örnek \(p=67\)'dir: burada \(67-1=66\), \(\gcd(66,308)=22\), dolayısıyla \(u=3\) ve \(308/22=14\) olur. Böylece
$$r=\frac{3}{\gcd(3,14)}=3$$
elde edilir; yani \(3\)'ün her katı geçersizdir. Implementasyonlar ayrıca
$$F(10)=96404$$
kontrol değerini doğrular.
C++, Python ve Java implementasyonları aynı iskeleti izler. Önce \(m\) çarpanları için mevcut arama sınırı \(X\) alınır ve \(\sqrt{308X+1}\)'e kadar küçük asal listesi oluşturulur. Bu liste hem küçük doğrulama adımlarında hem de \(g\,u+1\) biçimindeki asalları üretmek için kurulan eleklerde kullanılır.
\(308\)'in her çift böleni \(g\) için \(u=1,2,\dots,X\) indisli bir boole dizisi ayrılır. \(g\)'yi bölmeyen her küçük asal \(q\) için, \(g\,u+1\)'in \(q\)'ya bölündüğü tek kalan sınıfı hesaplanır ve bu dizinin tamamı temizlenir. Geriye kalan indisler birer asal adayı \(g\,u+1\) verir. Gerekli asallar \(2,3,5,23,29\) atlanır; diğer tüm yaşayan asallar yasak bölenlere dönüştürülür.
İkinci bir elek, bu yasak bölenlerin bütün katlarını işaretler. Sonra çarpan dizisi soldan sağa taranır ve işaretlenmemiş değerler artan sırada geçerli kabul edilir. İstenen sıra numarasına henüz ulaşılamadıysa arama sınırı iki katına çıkarılır ve süreç tekrarlanır. Implementasyonlar ayrıca \(D(4)=30\), \(D(308)=20010\) ve \(F(10)=96404\) gibi küçük tutarlılık kontrolleri de içerir.
\(X\), \(m\) çarpanları için arama sınırı olsun. \(\sqrt{308X+1}\)'e kadar asal tablosu kurmak \(O(\sqrt{X}\log\log X)\) zaman ve \(O(\sqrt{X})\) bellek gerektirir. \(u\)-uzayındaki sekiz aritmetik biçimli eleğin toplam harmonik maliyeti sabit katsayı dışında \(O(X\log\log X)\)'dir. Son aşamadaki kat işaretleme işlemi ise
$$O\left(X\sum_{r\in R}\frac{1}{r}\right)$$
maliyetindedir; burada \(R\), \(X\)'e kadar bulunan yasak bölenler kümesidir. En kötü durumda bu terim \(O(X\log X)\) olur. Dolayısıyla uygulanan yöntem \(O(X)\) bellek ve en kötü halde \(O(X\log X)\) zaman kullanır; buna rağmen her çift \(k\) için Bernoulli paydasını ayrı ayrı hesaplamaktan pratikte çok daha hızlıdır.
Para \(k\ge 2\) par, sea \(D(k)\) el denominador del número de Bernoulli \(B_k\) escrito en su forma reducida. Definimos \(F(n)\) como el \(n\)-ésimo entero positivo \(k\) que satisface
$$D(k)=20010.$$
La meta es calcular \(F(10^5)\). La idea decisiva es que no hace falta construir los números de Bernoulli: basta con entender qué valores \(p-1\) dividen a \(k\).
Las tres implementaciones convierten la condición sobre el denominador en una criba sobre múltiplos de una base obligatoria.
Para todo \(k\) par se cumple
$$D(k)=\prod_{p-1\mid k} p,$$
donde el producto recorre todos los primos \(p\) tales que \(p-1\) divide a \(k\). Por tanto, el denominador queda determinado por el conjunto de divisores \(p-1\) presentes en \(k\). Una vez usada esta fórmula, los números de Bernoulli dejan de intervenir de forma explícita.
El denominador objetivo se factoriza como
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
Así, \(k\) debe ser divisible por
$$1,\ 2,\ 4,\ 22,\ 28,$$
que son exactamente los valores \(p-1\) asociados a esos primos. Las condiciones no triviales se condensan en
$$\operatorname{lcm}(2,4,22,28)=308.$$
En consecuencia, todo término válido tiene la forma
$$k=308m,\qquad m\ge 1.$$
Esto garantiza que \(2,3,5,23,29\) aparecen en el denominador. Solo falta excluir cualquier primo adicional.
Tomemos un primo \(p\notin\{2,3,5,23,29\}\). Si \(p-1\mid k\), entonces \(p\) también aparecería en \(D(k)\), lo cual no está permitido. Escribimos
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
Como \(308=g\cdot \frac{308}{g}\), se obtiene
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
Ahora eliminamos el factor común entre \(u\) y \(308/g\). Definimos
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
Entonces
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
Por lo tanto, cada primo no deseado produce un divisor prohibido \(r\): cualquier múltiplo de \(r\) hace inválido al multiplicador \(m\).
Todo primo \(p>2\) es impar, así que \(p-1\) siempre es par. En consecuencia, \(g=\gcd(p-1,308)\) solo puede ser uno de los divisores pares de \(308\):
$$g\in\{2,4,14,22,28,44,154,308\}.$$
Para un \(g\) fijo, los candidatos a primo tienen exactamente la forma
$$p=g\,u+1.$$
En vez de comprobar primalidad caso por caso, las implementaciones cribán directamente el espacio de \(u\). Para cada primo pequeño \(q\nmid g\), la congruencia
$$g\,u+1\equiv 0 \pmod q$$
tiene la solución única
$$u\equiv -g^{-1}\pmod q,$$
porque \(g\) admite inverso multiplicativo módulo \(q\). Todos los valores de esa progresión hacen que \(g\,u+1\) sea compuesto y pueden eliminarse. La criba empieza suficientemente adelante para no borrar por error al propio primo \(q\) cuando ocurre \(g\,u+1=q\).
Después de la criba para un valor fijo de \(g\), cada \(u\) superviviente produce un primo \(p=g\,u+1\). Cada uno de esos primos se traduce en su divisor prohibido \(r\), y una segunda criba marca todos los múltiplos de \(r\) en el eje de multiplicadores. Si los multiplicadores no marcados son
$$m_1<m_2<m_3<\dots,$$
entonces la sucesión pedida es
$$F(n)=308m_n.$$
El menor multiplicador es \(m=1\), así que \(k=308\). Los divisores de \(308\) son
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
Entre ellos, los valores \(d\) tales que \(d+1\) es primo son \(1,2,4,22,28\), que producen
$$2,3,5,23,29.$$
Por consiguiente,
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
de modo que \(308\) es válido. En cambio, si \(m=2\), entonces \(k=616\), y \(617\) es primo con \(617-1=616\mid k\). Ese primo extra aparecería en el denominador, así que \(616\) es inválido. Otro ejemplo útil es \(p=67\): entonces \(67-1=66\), \(\gcd(66,308)=22\), luego \(u=3\) y \(308/22=14\). Así,
$$r=\frac{3}{\gcd(3,14)}=3,$$
lo que significa que todo múltiplo de \(3\) es inválido. Las implementaciones también verifican el punto de control
$$F(10)=96404.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero construyen una tabla de primos pequeños hasta \(\sqrt{308X+1}\), donde \(X\) es la cota de búsqueda actual para los multiplicadores. Esa tabla sirve tanto para las comprobaciones pequeñas como para las cribas que generan primos de la forma \(g\,u+1\).
Para cada divisor par \(g\) de \(308\), la implementación reserva un arreglo booleano indexado por \(u=1,2,\dots,X\). Con cada primo pequeño \(q\) que no divide a \(g\), calcula la clase residual módulo \(q\) que hace divisible a \(g\,u+1\) por \(q\), y luego elimina toda esa progresión. Los índices que sobreviven corresponden a candidatos primos \(g\,u+1\). Los primos obligatorios \(2,3,5,23,29\) se omiten, mientras que cada otro primo superviviente se convierte en un divisor prohibido del multiplicador.
Una segunda criba marca todos los múltiplos de todos los divisores prohibidos. Recorriendo el arreglo de multiplicadores de izquierda a derecha se obtienen los valores válidos en orden creciente. Si todavía no se alcanzó el índice pedido, la cota de búsqueda se duplica y el proceso se repite. Además, las implementaciones contienen comprobaciones de consistencia como \(D(4)=30\), \(D(308)=20010\) y \(F(10)=96404\).
Sea \(X\) la cota de búsqueda sobre los multiplicadores \(m\). Construir la tabla de primos hasta \(\sqrt{308X+1}\) cuesta \(O(\sqrt{X}\log\log X)\) tiempo y \(O(\sqrt{X})\) memoria. Las ocho cribas de formas aritméticas sobre el espacio de \(u\) tienen un coste armónico total \(O(X\log\log X)\), salvo por un factor constante. La fase final de marcado de múltiplos cuesta
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
donde \(R\) es el conjunto de divisores prohibidos encontrados hasta \(X\); en el peor caso esto es \(O(X\log X)\). Por tanto, el método implementado usa \(O(X)\) memoria y tiempo \(O(X\log X)\) en el peor caso, aunque en la práctica es muchísimo más rápido que calcular denominadores de Bernoulli uno por uno para cada \(k\) par.
对偶数 \(k\ge 2\)，记 \(D(k)\) 为 Bernoulli 数 \(B_k\) 的既约分母。把所有满足
$$D(k)=20010$$
的正整数 \(k\) 按从小到大排列，并把第 \(n\) 个记为 \(F(n)\)。题目要求计算 \(F(10^5)\)。真正的关键并不是去显式求 Bernoulli 数，而是把“分母等于 20010”改写成关于 \(k\) 的整除条件。
三种语言的实现都把问题化成了“在一个必然基数的倍数中筛掉非法项”的过程。
对每个偶数 \(k\)，都有
$$D(k)=\prod_{p-1\mid k} p,$$
其中乘积遍历所有满足 \(p-1\mid k\) 的素数 \(p\)。这说明分母完全由 \(k\) 能被哪些 \(p-1\) 整除决定。一旦用上这条定理，Bernoulli 数本身就不需要再参与计算了。
目标分母分解为
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
因此 \(k\) 必须能被
$$1,\ 2,\ 4,\ 22,\ 28$$
整除，因为这些正是所需素数对应的 \(p-1\)。把非平凡条件合并起来，有
$$\operatorname{lcm}(2,4,22,28)=308.$$
所以每一个候选值都必须写成
$$k=308m,\qquad m\ge 1.$$
这样就已经保证了 \(2,3,5,23,29\) 一定出现在分母里。接下来的任务，就是确保不会再出现任何别的素数。
考虑一个不在目标集合中的素数 \(p\notin\{2,3,5,23,29\}\)。如果 \(p-1\mid k\)，那么根据上面的定理，\(p\) 也会进入 \(D(k)\)，这就破坏了目标分母。记
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
由于 \(308=g\cdot \frac{308}{g}\)，于是
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
接下来把 \(u\) 与 \(308/g\) 的公共因子约掉，定义
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
那么就有
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
这一步非常重要：它告诉我们，每一个不希望出现的素数 \(p\)，都会对应出 \(m\) 的一个禁用因子 \(r\)。只要 \(m\) 是这个 \(r\) 的倍数，就一定非法。
因为每个素数 \(p>2\) 都是奇数，所以 \(p-1\) 一定是偶数。于是 \(g=\gcd(p-1,308)\) 只能是 \(308\) 的偶因子，即
$$g\in\{2,4,14,22,28,44,154,308\}.$$
在固定某个 \(g\) 之后，候选素数恰好都写成
$$p=g\,u+1$$
的形式。实现并没有对每个候选逐个做素性测试，而是直接在 \(u\) 的空间上做筛。对于每个不整除 \(g\) 的小素数 \(q\)，同余式
$$g\,u+1\equiv 0 \pmod q$$
有唯一解
$$u\equiv -g^{-1}\pmod q,$$
因为这时 \(g\) 在模 \(q\) 意义下有乘法逆元。这个同余类中的所有 \(u\) 都会使 \(g\,u+1\) 被 \(q\) 整除，因此都可以直接划掉。实现还会把起始位置放到足够靠后，从而避免在某些情况下把素数 \(q\) 本身误删掉。
对固定的 \(g\) 完成筛法之后，所有幸存的 \(u\) 都对应一个素数 \(p=g\,u+1\)。对每个这样的素数，都可以计算出它对应的禁用因子 \(r\)，然后在第二层筛法中把所有 \(r\) 的倍数全部标成非法。若未被标记的乘子依次为
$$m_1<m_2<m_3<\dots,$$
那么目标序列就直接是
$$F(n)=308m_n.$$
最小乘子是 \(m=1\)，因此 \(k=308\)。\(308\) 的全部因子为
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
其中满足 \(d+1\) 为素数的因子恰好是 \(1,2,4,22,28\)，对应素数
$$2,3,5,23,29.$$
因此
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
说明 \(308\) 本身就是合法项。相反，如果 \(m=2\)，那么 \(k=616\)，而 \(617\) 是素数，并且 \(617-1=616\mid k\)。于是分母中会额外出现因子 \(617\)，所以 \(616\) 不合法。再看另一个很有代表性的例子 \(p=67\)：此时 \(67-1=66\)，\(\gcd(66,308)=22\)，所以 \(u=3\)，而 \(308/22=14\)。于是
$$r=\frac{3}{\gcd(3,14)}=3,$$
这说明所有 \(3\) 的倍数乘子都会被判为非法。实现还验证了检查点
$$F(10)=96404.$$
C++、Python 和 Java 实现采用同一套流程。首先，它们在当前乘子搜索上界 \(X\) 下，构造到 \(\sqrt{308X+1}\) 为止的小素数表。这张表有两个用途：一是支持很小规模的正确性校验，二是驱动“形如 \(g\,u+1\)”的素数筛。
对于 \(308\) 的每个偶因子 \(g\)，实现都会建立一个以 \(u=1,2,\dots,X\) 为下标的布尔数组。对每个不整除 \(g\) 的小素数 \(q\)，程序计算出会使 \(g\,u+1\) 被 \(q\) 整除的唯一剩余类，然后把整条等差序列全部清掉。剩余的下标就对应候选素数 \(g\,u+1\)。目标中必须保留的素数 \(2,3,5,23,29\) 会被跳过，其余幸存素数则全部转化成乘子的禁用因子。
接着第二层筛法把所有禁用因子的倍数统一标记为非法。最后按从小到大的顺序扫描乘子数组，所有未标记的值就是合法乘子。如果当前上界还不足以找到所需的第 \(n\) 项，就把上界翻倍后重新执行整个过程。实现里还带有若干小型一致性检查，例如 \(D(4)=30\)、\(D(308)=20010\) 以及 \(F(10)=96404\)。
设 \(X\) 为乘子 \(m\) 的搜索上界。建立到 \(\sqrt{308X+1}\) 的素数表需要 \(O(\sqrt{X}\log\log X)\) 时间和 \(O(\sqrt{X})\) 空间。八个 \(u\)-空间算术型筛法的总调和复杂度为 \(O(X\log\log X)\)，只差一个常数因子。最后，对所有禁用因子的倍数进行标记的成本为
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
其中 \(R\) 表示在上界 \(X\) 内发现的禁用因子集合；最坏情况下这一项是 \(O(X\log X)\)。因此，当前实现的空间复杂度为 \(O(X)\)，最坏时间复杂度为 \(O(X\log X)\)，但与逐个偶数 \(k\) 直接求 Bernoulli 分母相比，实际速度要快得多。
Для чётного \(k\ge 2\) обозначим через \(D(k)\) знаменатель числа Бернулли \(B_k\) в несократимом виде. Пусть \(F(n)\) обозначает \(n\)-е положительное число \(k\), для которого
$$D(k)=20010.$$
Требуется найти \(F(10^5)\). Главная идея состоит в том, что сами числа Бернулли вычислять не нужно: всё сводится к тому, какие значения \(p-1\) делят \(k\).
Все три реализации превращают условие на знаменатель в решето по множителям обязательной базовой величины.
Для любого чётного \(k\) верно
$$D(k)=\prod_{p-1\mid k} p,$$
где произведение берётся по всем простым \(p\), для которых \(p-1\) делит \(k\). Значит, знаменатель полностью определяется тем, какие значения \(p-1\) входят в набор делителей числа \(k\). После этого сами числа Бернулли исчезают из вычисления.
Целевой знаменатель раскладывается так:
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
Следовательно, \(k\) должно делиться на
$$1,\ 2,\ 4,\ 22,\ 28,$$
потому что именно эти числа равны \(p-1\) для нужных простых. Нетрудно объединить нетривиальные условия:
$$\operatorname{lcm}(2,4,22,28)=308.$$
Значит, всякий допустимый член имеет вид
$$k=308m,\qquad m\ge 1.$$
Тем самым мы уже гарантировали присутствие простых \(2,3,5,23,29\) в знаменателе. Остаётся исключить появление любых других простых.
Рассмотрим простое \(p\notin\{2,3,5,23,29\}\). Если \(p-1\mid k\), то по формуле выше простое \(p\) тоже войдёт в \(D(k)\), а этого быть не должно. Запишем
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
Поскольку \(308=g\cdot \frac{308}{g}\), имеем
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
Теперь сократим общий множитель между \(u\) и \(308/g\). Введём
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
Тогда получаем эквивалентность
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
Итак, каждое нежелательное простое порождает запрещённый делитель \(r\): любой множитель \(m\), кратный \(r\), недопустим.
Каждое простое \(p>2\) нечётно, значит \(p-1\) всегда чётно. Поэтому \(g=\gcd(p-1,308)\) может быть только чётным делителем числа \(308\):
$$g\in\{2,4,14,22,28,44,154,308\}.$$
При фиксированном \(g\) кандидаты на простые имеют вид
$$p=g\,u+1.$$
Вместо отдельной проверки каждого кандидата реализации строят решето прямо в пространстве \(u\). Для каждого малого простого \(q\nmid g\) сравнение
$$g\,u+1\equiv 0 \pmod q$$
имеет единственное решение
$$u\equiv -g^{-1}\pmod q,$$
потому что \(g\) обратимо по модулю \(q\). Все значения из этой арифметической прогрессии делают \(g\,u+1\) составным, поэтому их можно сразу вычеркнуть. Начало прогрессии выбирается достаточно большим, чтобы не удалить само простое \(q\), если вдруг \(g\,u+1=q\).
После решета для фиксированного \(g\) каждое оставшееся \(u\) даёт простое \(p=g\,u+1\). Для каждого такого простого вычисляется запрещённый делитель \(r\), а затем во втором решете отмечаются все кратные \(r\) на оси множителей. Если неотмеченные множители равны
$$m_1<m_2<m_3<\dots,$$
то искомая последовательность имеет вид
$$F(n)=308m_n.$$
Минимальный множитель равен \(m=1\), поэтому \(k=308\). Делители числа \(308\) таковы:
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
Среди них условие «\(d+1\) простое» выполняется ровно для \(1,2,4,22,28\), что даёт простые
$$2,3,5,23,29.$$
Следовательно,
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
то есть \(308\) подходит. А вот при \(m=2\) получаем \(k=616\), и число \(617\) простое, причём \(617-1=616\mid k\). Это добавило бы в знаменатель лишний множитель \(617\), поэтому \(616\) недопустимо. Ещё один полезный пример даёт простое \(p=67\): тогда \(67-1=66\), \(\gcd(66,308)=22\), так что \(u=3\) и \(308/22=14\). Значит,
$$r=\frac{3}{\gcd(3,14)}=3,$$
и все кратные \(3\) автоматически запрещены. Реализации также проверяют контрольное значение
$$F(10)=96404.$$
Реализации на C++, Python и Java устроены одинаково. Сначала они строят таблицу малых простых до \(\sqrt{308X+1}\), где \(X\) - текущая граница поиска по множителям. Эта таблица нужна и для небольших проверок корректности, и для решета, порождающего простые числа вида \(g\,u+1\).
Для каждого чётного делителя \(g\) числа \(308\) реализация создаёт булев массив с индексами \(u=1,2,\dots,X\). Для каждого малого простого \(q\), не делящего \(g\), вычисляется единственный класс вычетов, при котором \(g\,u+1\) делится на \(q\), после чего вся эта прогрессия зануляется. Оставшиеся индексы соответствуют кандидатам на простые \(g\,u+1\). Нужные простые \(2,3,5,23,29\) пропускаются, а все остальные выжившие простые переводятся в запрещённые делители множителя.
Второе решето отмечает все кратные всех запрещённых делителей. Далее массив множителей просматривается слева направо, и неотмеченные значения дают допустимые элементы в возрастающем порядке. Если нужный номер ещё не достигнут, граница поиска удваивается и вся процедура повторяется. Кроме того, реализации содержат небольшие проверки согласованности вроде \(D(4)=30\), \(D(308)=20010\) и \(F(10)=96404\).
Пусть \(X\) - граница поиска по множителям \(m\). Построение таблицы простых до \(\sqrt{308X+1}\) требует \(O(\sqrt{X}\log\log X)\) времени и \(O(\sqrt{X})\) памяти. Восемь решёт по арифметическим формам в пространстве \(u\) суммарно имеют гармоническую стоимость \(O(X\log\log X)\) с точностью до константы. Финальная фаза отметки кратных имеет стоимость
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
где \(R\) - множество запрещённых делителей, найденных до уровня \(X\); в худшем случае это даёт \(O(X\log X)\). Итак, реализованный алгоритм использует \(O(X)\) памяти и имеет худшее время работы \(O(X\log X)\), но на практике работает намного быстрее прямого вычисления знаменателей для каждого чётного \(k\).
للقيم الزوجية \(k\ge 2\)، نرمز بـ \(D(k)\) إلى مقام عدد برنولي \(B_k\) بعد الاختزال. ونعرّف \(F(n)\) بأنه العدد الموجب رقم \(n\) من القيم \(k\) التي تحقق
$$D(k)=20010.$$
المطلوب هو حساب \(F(10^5)\). الفكرة الأساسية هنا أن المسألة لا تحتاج إلى حساب أعداد برنولي نفسها، بل إلى فهم أي القيم من الشكل \(p-1\) تقسم \(k\).
البرامج الثلاثة تحول شرط المقام إلى عملية غربلة على مضاعفات قيمة أساسية مفروضة سلفاً.
لكل \(k\) زوجي لدينا
$$D(k)=\prod_{p-1\mid k} p,$$
حيث يمتد الجداء على جميع الأعداد الأولية \(p\) التي تحقق أن \(p-1\) يقسم \(k\). إذن المقام يتحدد كلياً من خلال مجموعة القيم \(p-1\) التي تظهر كقواسم لـ \(k\). بعد هذه الخطوة لا تبقى أعداد برنولي نفسها جزءاً من الحساب.
يتفكك المقام الهدف على الصورة
$$20010=2\cdot 3\cdot 5\cdot 23\cdot 29.$$
لذلك يجب أن يكون \(k\) قابلاً للقسمة على
$$1,\ 2,\ 4,\ 22,\ 28,$$
لأن هذه هي القيم \(p-1\) الموافقة للأوليات المطلوبة. بجمع الشروط غير التافهة نحصل على
$$\operatorname{lcm}(2,4,22,28)=308.$$
وعليه فإن كل عنصر صالح يكتب بالشكل
$$k=308m,\qquad m\ge 1.$$
وهذا يضمن ظهور الأوليات \(2,3,5,23,29\) في المقام. ويبقى فقط منع ظهور أي أولي إضافي.
خذ أولياً \(p\notin\{2,3,5,23,29\}\). إذا تحقق \(p-1\mid k\)، فإن \(p\) سيدخل أيضاً في \(D(k)\)، وهذا غير مسموح. نكتب
$$d=p-1,\qquad g=\gcd(d,308),\qquad d=g\,u.$$
وبما أن \(308=g\cdot \frac{308}{g}\)، فإن
$$d\mid 308m \iff g\,u\mid g\cdot \frac{308}{g}\,m \iff u\mid \frac{308}{g}\,m.$$
نزيل الآن العامل المشترك بين \(u\) و \(308/g\)، ونعرف
$$r=\frac{u}{\gcd\left(u,\frac{308}{g}\right)}.$$
فنحصل على التكافؤ
$$u\mid \frac{308}{g}\,m \iff r\mid m.$$
وهذا يعني أن كل أولي غير مرغوب فيه يولد قاسماً ممنوعاً \(r\)، وكل مضاعف لهذا \(r\) يجعل \(m\) غير صالح.
كل أولي \(p>2\) هو عدد فردي، ولذلك فإن \(p-1\) يكون زوجياً دائماً. ومن ثم فإن \(g=\gcd(p-1,308)\) لا يمكن إلا أن يكون واحداً من القواسم الزوجية للعدد \(308\):
$$g\in\{2,4,14,22,28,44,154,308\}.$$
وعند تثبيت قيمة \(g\)، فإن جميع المرشحين الأوليين يأخذون الصورة
$$p=g\,u+1.$$
بدلاً من اختبار أولية كل مرشح على حدة، تعمل التنفيذات مباشرة في فضاء \(u\). ولكل أولي صغير \(q\nmid g\)، فإن الموافقة
$$g\,u+1\equiv 0 \pmod q$$
لها حل وحيد هو
$$u\equiv -g^{-1}\pmod q,$$
لأن \(g\) يملك معكوساً ضريبياً بترديد \(q\). كل قيمة في هذه المتتالية الحسابية تجعل \(g\,u+1\) عدداً مركباً، ولذلك يمكن شطبها مباشرة. وتبدأ الغربلة من موضع متأخر بما يكفي حتى لا يُحذف الأولي \(q\) نفسه خطأً إذا حدث أن \(g\,u+1=q\).
بعد إنهاء الغربلة لقيمة ثابتة من \(g\)، فإن كل \(u\) باقٍ يعطي أولياً \(p=g\,u+1\). ثم يُحوَّل كل أولي من هذا النوع إلى القاسم الممنوع الموافق \(r\)، وبعد ذلك تعلِّم غربلة ثانية جميع مضاعفات \(r\) على محور المضاعفات. إذا كانت المضاعفات غير المعلَّمة هي
$$m_1<m_2<m_3<\dots,$$
فإن المتتالية المطلوبة تكون ببساطة
$$F(n)=308m_n.$$
أصغر مضاعف هو \(m=1\)، ومن ثم \(k=308\). قواسم \(308\) هي
$$1,2,4,7,11,14,22,28,44,77,154,308.$$
ومن بينها تكون القيم التي تجعل \(d+1\) أولياً هي \(1,2,4,22,28\)، فتنتج الأوليات
$$2,3,5,23,29.$$
إذن
$$D(308)=2\cdot 3\cdot 5\cdot 23\cdot 29=20010,$$
ولذلك فإن \(308\) صالح. أما إذا أخذنا \(m=2\)، فسنحصل على \(k=616\)، والعدد \(617\) أولي، كما أن \(617-1=616\mid k\). هذا يضيف عاملاً أولياً زائداً إلى المقام، لذا تكون \(616\) غير صالحة. ومثال آخر مفيد هو \(p=67\): عندها \(67-1=66\)، و \(\gcd(66,308)=22\)، وبالتالي \(u=3\) و \(308/22=14\). ومن ثم
$$r=\frac{3}{\gcd(3,14)}=3,$$
أي أن كل مضاعف للعدد \(3\) غير صالح. كما تتحقق التنفيذات أيضاً من قيمة الفحص
$$F(10)=96404.$$
التنفيذات في C++ و Python و Java تتبع المخطط نفسه. فهي تبدأ ببناء جدول للأوليات الصغيرة حتى \(\sqrt{308X+1}\)، حيث \(X\) هو حد البحث الحالي للمضاعفات. ويُستخدم هذا الجدول في التحققات الصغيرة، كما يُستخدم في الغربلة التي تولد أوليات من الشكل \(g\,u+1\).
لكل قاسم زوجي \(g\) من قواسم \(308\)، تنشئ الشفرة مصفوفة منطقية مفهرسة بالقيم \(u=1,2,\dots,X\). وباستخدام كل أولي صغير \(q\) لا يقسم \(g\)، تحسب الشفرة فئة البواقي الوحيدة التي تجعل \(g\,u+1\) قابلاً للقسمة على \(q\)، ثم تمسح كامل هذه المتتالية. كل فهرس يبقى بعد ذلك يقابل مرشحاً أولياً من الشكل \(g\,u+1\). تُستثنى الأوليات المطلوبة \(2,3,5,23,29\)، بينما يُحوَّل كل أولي باقٍ إلى قاسم ممنوع للمضاعف.
بعد ذلك تعلِّم غربلة ثانية جميع مضاعفات جميع القواسم الممنوعة. وبالمسح من اليسار إلى اليمين نحصل على القيم الصالحة بترتيب تصاعدي. وإذا لم يكن الحد الحالي كافياً للوصول إلى الرتبة المطلوبة، تُضاعَف قيمة الحد ويُعاد تنفيذ العملية كلها. كما تتضمن التنفيذات اختبارات اتساق صغيرة من نوع \(D(4)=30\) و \(D(308)=20010\) و \(F(10)=96404\).
ليكن \(X\) حد البحث للمضاعفات \(m\). بناء جدول الأوليات حتى \(\sqrt{308X+1}\) يكلف \(O(\sqrt{X}\log\log X)\) زمناً و \(O(\sqrt{X})\) ذاكرة. أما الغربلات الثماني في فضاء \(u\) فتكلف معاً \(O(X\log\log X)\) حتى عامل ثابت. ومرحلة تعليم جميع مضاعفات القواسم الممنوعة تكلف
$$O\left(X\sum_{r\in R}\frac{1}{r}\right),$$
حيث \(R\) هي مجموعة القواسم الممنوعة المكتشفة حتى الحد \(X\)؛ وفي أسوأ الأحوال يصبح ذلك \(O(X\log X)\). لذلك تستخدم الخوارزمية المنفذة ذاكرة \(O(X)\) وزمناً أسوأه \(O(X\log X)\)، لكنها عملياً أسرع بكثير من إعادة حساب مقام برنولي لكل \(k\) زوجي على حدة.