For each integer \(n>1\), let \(s(n)\) be its smallest prime factor and let \(a(n)=v_{s(n)}(n)\) be the exponent of that prime in \(n\). The quantity to compute is the limiting average
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
The key observation is that integers can be grouped by their smallest prime factor and by the exact exponent of that prime. That turns the limit into a convergent series over primes, which is what the implementations evaluate.
We work with natural densities. For a fixed prime \(p\), define
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
This is the density of integers not divisible by any smaller prime, so it is the correct prefactor when the smallest prime factor is exactly \(p\).
If \(s(n)=p\), then no prime \(q<p\) divides \(n\). In natural density, each condition \(q\nmid n\) contributes a factor \(1-1/q\), so the density of integers surviving all smaller primes is
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
For example, \(D(2)=1\), \(D(3)=1/2\), and \(D(5)=(1-1/2)(1-1/3)=1/3\).
Now fix \(p\) and ask for the density of integers with \(s(n)=p\) and \(a(n)=k\). Such integers are divisible by \(p^k\) but not by \(p^{k+1}\). The \(p\)-part therefore contributes
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
Multiplying by the smaller-prime factor gives
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
This is the density of integers whose smallest prime factor is \(p\) and whose exponent of \(p\) is exactly \(k\).
Each such integer contributes \((k-1)/(p-1)\) to the mean, so
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
Write \(m=k-1\). Then
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
Using the standard identity \(\sum_{m\ge 0}mx^m=x/(1-x)^2\) with \(x=1/p\), we get
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
Therefore the desired constant is
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
The implementations also track the auxiliary mean obtained by replacing the denominator \(p-1\) with \(p\):
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
The same density calculation yields
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
This companion series is numerically checked against a direct average over a large initial range of integers, which gives an independent confirmation of the density argument.
The first few contributions to \(A\) are easy to compute explicitly.
For \(p=2\), we have \(D(2)=1\), so the contribution is
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
For \(p=3\), the prefactor is \(D(3)=1/2\), so the contribution is
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
For \(p=5\), the prefactor is \(D(5)=1/3\), so the contribution is
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
After only three primes, the partial sum is
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333,$$
which already shows how quickly the series converges.
Because \(0<D(p)\le 1\), each omitted term beyond a cutoff \(B\) is at most \(1/(p(p-1)^2)\), which behaves like \(1/p^3\). So the tail converges absolutely and is extremely small.
The implementation uses the explicit estimate
$$R_B<\frac{1}{2B^2}.$$
With \(B=2\cdot 10^6\), this is below \(5\times 10^{-13}\), which is comfortably smaller than the displayed \(12\)-decimal precision.
The C++, Python, and Java implementations first generate all primes up to \(2\cdot 10^6\) with a standard sieve. They then maintain the running product \(D(p)\) in increasing prime order, updating it by multiplying with \((p-1)/p\) after each prime has been processed.
At every prime, the implementation adds the target term \(D(p)/(p(p-1)^2)\) to the main total. It also accumulates the companion term \(D(p)/(p^2(p-1))\), because that auxiliary constant is used as a numerical cross-check of the derivation.
The C++ implementation performs two additional sanity checks. First, it verifies that the explicit tail estimate at the chosen cutoff is below \(5\times 10^{-13}\). Second, it checks the companion series both against the known decimal value \(0.282419756159\) and against a direct average over the first \(200000\) integers obtained by extracting the smallest prime factor and its exponent. The Python and Java implementations keep the same series evaluation but omit the extra assertions and simply print the target value to \(12\) decimal places.
Let \(B=2\cdot 10^6\) be the sieve bound. Building the prime list costs \(O(B\log\log B)\) time and \(O(B)\) memory. The subsequent summation visits each prime once, so it costs \(O(\pi(B))\) arithmetic steps. High-precision decimal operations increase constant factors but do not change the asymptotic bounds. Overall, the method uses \(O(B)\) memory and runs in \(O(B\log\log B)\) time.
Für jede ganze Zahl \(n>1\) sei \(s(n)\) ihr kleinster Primfaktor und \(a(n)=v_{s(n)}(n)\) der Exponent dieses Primfaktors in \(n\). Gesucht ist der Grenzwert
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
Die Lösung zählt also nicht einzelne Zahlen direkt, sondern gruppiert sie nach kleinstem Primfaktor und nach dessen genauer Potenz. Dadurch wird das Problem zu einer schnell konvergenten Reihe über Primzahlen.
Wir arbeiten mit natürlichen Dichten. Für eine feste Primzahl \(p\) setzen wir
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Dieser Faktor ist die Dichte der Zahlen, die durch keine kleinere Primzahl teilbar sind. Genau deshalb erscheint er, wenn der kleinste Primfaktor gleich \(p\) sein soll.
Die Bedingung \(s(n)=p\) bedeutet, dass kein \(q<p\) die Zahl \(n\) teilt. In natürlicher Dichte liefert jede Bedingung \(q\nmid n\) den Faktor \(1-1/q\). Daher ist
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Beispiele: \(D(2)=1\), \(D(3)=1/2\) und \(D(5)=(1-1/2)(1-1/3)=1/3\).
Fixiere nun \(p\) und den Exponenten \(k\ge 1\). Die Bedingung \(a(n)=k\) heißt: \(p^k\mid n\), aber \(p^{k+1}\nmid n\). Der Beitrag des \(p\)-Teils ist also
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
Zusammen mit dem Faktor der kleineren Primzahlen erhält man die Dichte
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
Das ist genau die Dichte der Zahlen mit kleinstem Primfaktor \(p\) und Exponent \(k\).
Jede solche Zahl trägt \((k-1)/(p-1)\) zum Mittelwert bei. Daher
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
Mit \(m=k-1\) folgt
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
Aus \(\sum_{m\ge 0}mx^m=x/(1-x)^2\) für \(x=1/p\) ergibt sich
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
Damit ist die gesuchte Konstante
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
Zusätzlich verfolgen die Implementierungen den Hilfsmittelwert, bei dem im Nenner \(p\) statt \(p-1\) steht:
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
Die gleiche Rechnung liefert
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
Diese Reihe wird zusätzlich direkt durch einen großen numerischen Mittelwert über Anfangswerte von \(n\) kontrolliert. So lässt sich die Dichteableitung unabhängig überprüfen.
Die ersten Beiträge zu \(A\) lassen sich explizit ausrechnen.
Für \(p=2\) gilt \(D(2)=1\), also ist der Beitrag
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
Für \(p=3\) ist \(D(3)=1/2\), also
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
Für \(p=5\) ist \(D(5)=1/3\), also
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
Nach nur drei Primzahlen erhält man bereits
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333,$$
was die schnelle Konvergenz der Reihe deutlich zeigt.
Da \(0<D(p)\le 1\) gilt, ist jeder ausgelassene Term jenseits einer Grenze \(B\) höchstens \(1/(p(p-1)^2)\) groß und verhält sich also wie \(1/p^3\). Die Restreihe konvergiert deshalb absolut und sehr schnell.
Die Implementierung verwendet die explizite Abschätzung
$$R_B<\frac{1}{2B^2}.$$
Für \(B=2\cdot 10^6\) liegt der Rest damit unter \(5\times 10^{-13}\) und ist weit kleiner als die ausgegebenen \(12\) Nachkommastellen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle Primzahlen bis \(2\cdot 10^6\) mit einem Standardsieb. Danach führen sie in aufsteigender Primreihenfolge das laufende Produkt \(D(p)\) mit, das nach jeder verarbeiteten Primzahl durch Multiplikation mit \((p-1)/p\) aktualisiert wird.
Für jede Primzahl wird der Zielterm \(D(p)/(p(p-1)^2)\) zur Hauptsumme addiert. Zusätzlich wird der Hilfsterm \(D(p)/(p^2(p-1))\) mitgeführt, weil diese zweite Konstante als numerische Gegenprobe dient.
Die C++-Implementierung ergänzt zwei Kontrollen. Erstens wird geprüft, dass die Restabschätzung an der gewählten Grenze kleiner als \(5\times 10^{-13}\) ist. Zweitens wird die Hilfsreihe sowohl mit dem bekannten Dezimalwert \(0.282419756159\) als auch mit einem direkten Mittelwert über die ersten \(200000\) Zahlen verglichen, bei dem jeweils kleinster Primfaktor und Exponent bestimmt werden. Die Python- und Java-Implementierungen führen dieselbe Reihensummation aus, verzichten aber auf die zusätzlichen Assertions und geben nur den Zielwert mit \(12\) Dezimalstellen aus.
Sei \(B=2\cdot 10^6\) die Primgrenze. Das Erzeugen der Primzahlen kostet \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Die anschließende Summation besucht jede Primzahl genau einmal und benötigt daher \(O(\pi(B))\) Rechenschritte. Hochpräzise Dezimalarithmetik verändert nur die Konstanten, nicht die asymptotische Ordnung. Insgesamt arbeitet das Verfahren in \(O(B\log\log B)\) Zeit bei \(O(B)\) Speicherbedarf.
Her \(n>1\) tamsayısı için \(s(n)\) en küçük asal bölen, \(a(n)=v_{s(n)}(n)\) ise bu asalın üs değeri olsun. Hesaplanmak istenen limit ortalama şudur:
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
Temel fikir, sayıları tek tek incelemek yerine onları en küçük asal bölenlerine ve bu asalın tam üssüne göre gruplamaktır. Böylece problem, asallar üzerinde yakınsak bir seriye dönüşür.
Doğal yoğunluklarla çalışalım. Sabit bir asal \(p\) için
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right)$$
tanımını yapalım. Bu çarpım, daha küçük hiçbir asalın sayıyı bölmediği yoğunluğu verir. Dolayısıyla en küçük asal bölen tam olarak \(p\) olduğunda doğru ön katsayı budur.
\(s(n)=p\) olması, \(q<p\) olan hiçbir asalın \(n\)'yi bölmemesi demektir. Doğal yoğunlukta her \(q\nmid n\) koşulu \(1-1/q\) çarpanı getirir. Bu yüzden
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right)$$
elde edilir. Örneğin \(D(2)=1\), \(D(3)=1/2\) ve \(D(5)=(1-1/2)(1-1/3)=1/3\).
Şimdi \(p\) sabit olsun ve \(a(n)=k\ge 1\) durumuna bakalım. Bu, \(p^k\mid n\) ama \(p^{k+1}\nmid n\) demektir. Dolayısıyla \(p\)-kısmının yoğunluğu
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}$$
olur. Daha küçük asallardan gelen katsayı ile çarpınca
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1$$
bulunur. Bu ifade, en küçük asal böleni \(p\) ve bu asala ait üssü tam \(k\) olan sayıların yoğunluğudur.
Bu tür her sayı ortalamaya \((k-1)/(p-1)\) katkı yapar. O halde
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
\(m=k-1\) yazarsak
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
\(\sum_{m\ge 0}mx^m=x/(1-x)^2\) özdeşliğinde \(x=1/p\) konursa
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}$$
elde edilir. Böylece aranan sabit
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
Uygulamalar ayrıca paydada \(p-1\) yerine \(p\) bulunan yardımcı ortalamayı da izler:
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
Aynı yöntemle
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}$$
sonucu çıkar. Bu yardımcı seri, büyük bir başlangıç aralığı üzerinde doğrudan ortalama alınarak sayısal olarak da kontrol edilir.
\(A\) serisinin ilk birkaç katkısını açıkça yazabiliriz.
\(p=2\) için \(D(2)=1\) olduğundan katkı
$$\frac{1}{2(2-1)^2}=\frac{1}{2}$$
olur. \(p=3\) için \(D(3)=1/2\) olduğundan katkı
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}$$
ve \(p=5\) için \(D(5)=1/3\) olduğundan katkı
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}$$
olur. İlk üç asal sonunda kısmi toplam
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333$$
çıkar; bu da serinin çok hızlı yakınsadığını gösterir.
\(0<D(p)\le 1\) olduğu için, \(B\) sınırından sonra kalan her terim en fazla \(1/(p(p-1)^2)\) büyüklüğündedir ve bu da \(1/p^3\) mertebesindedir. Dolayısıyla kuyruk mutlak yakınsaktır ve çok küçüktür.
Uygulama şu açık üst sınırı kullanır:
$$R_B<\frac{1}{2B^2}.$$
\(B=2\cdot 10^6\) için bu miktar \(5\times 10^{-13}\)'ten küçüktür; yani yazdırılan \(12\) ondalık basamağın çok altındadır.
C++, Python ve Java uygulamaları önce standart bir elek ile \(2\cdot 10^6\)'ya kadar tüm asalları üretir. Daha sonra asallar artan sırada gezerken \(D(p)\) çarpımını taşır ve her asal işlendiğinde bu çarpımı \((p-1)/p\) ile güncelleyerek bir sonraki prime geçer.
Her asal için hedef terim \(D(p)/(p(p-1)^2)\) ana toplamın içine eklenir. Aynı anda \(D(p)/(p^2(p-1))\) biçimindeki yardımcı terim de biriktirilir; çünkü bu ikinci sabit, türetimin sayısal doğrulamasında kullanılır.
C++ uygulaması iki ek güvenlik kontrolü yapar. Birincisi, seçilen sınırda kuyruk üst sınırının \(5\times 10^{-13}\)'ten küçük olduğunu doğrular. İkincisi, yardımcı seriyi hem bilinen ondalık değer \(0.282419756159\) ile hem de ilk \(200000\) sayı üzerinde en küçük asal bölen ve üs çıkarılarak hesaplanan doğrudan ortalama ile karşılaştırır. Python ve Java uygulamaları aynı seri toplamını korur, fakat ek doğrulamaları atlayıp yalnızca hedef değeri \(12\) ondalık basamakla yazdırır.
\(B=2\cdot 10^6\) elek sınırı olsun. Asal listesini üretmek \(O(B\log\log B)\) zaman ve \(O(B)\) bellek gerektirir. Sonraki toplam aşaması her asalı bir kez ziyaret ettiği için \(O(\pi(B))\) adım sürer. Yüksek hassasiyetli ondalık aritmetik sadece sabit katsayıları büyütür. Toplamda yöntem \(O(B\log\log B)\) zamanda çalışır ve \(O(B)\) bellek kullanır.
Para cada entero \(n>1\), sea \(s(n)\) su menor factor primo y sea \(a(n)=v_{s(n)}(n)\) el exponente de ese primo en \(n\). Lo que se busca es el promedio límite
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
La idea central no es recorrer los enteros uno por uno, sino agruparlos por su menor primo y por la potencia exacta con la que aparece. Así el problema se convierte en una serie convergente sobre primos.
Trabajamos con densidades naturales. Para un primo fijo \(p\), definimos
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Este factor es la densidad de enteros que no son divisibles por ningún primo menor. Por eso aparece cuando el menor factor primo debe ser exactamente \(p\).
La condición \(s(n)=p\) significa que ningún primo \(q<p\) divide a \(n\). En densidad natural, cada restricción \(q\nmid n\) aporta el factor \(1-1/q\). Por tanto,
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Por ejemplo, \(D(2)=1\), \(D(3)=1/2\) y \(D(5)=(1-1/2)(1-1/3)=1/3\).
Ahora fijemos \(p\) y el exponente \(k\ge 1\). La condición \(a(n)=k\) equivale a pedir \(p^k\mid n\) pero \(p^{k+1}\nmid n\). La parte asociada a \(p\) tiene entonces densidad
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
Al multiplicar por el factor de los primos menores obtenemos
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
Esta es la densidad de enteros cuyo menor factor primo es \(p\) y cuya potencia correspondiente es exactamente \(k\).
Cada entero de este tipo contribuye con \((k-1)/(p-1)\) al promedio. Por lo tanto,
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
Si ponemos \(m=k-1\), queda
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
Usando \(\sum_{m\ge 0}mx^m=x/(1-x)^2\) con \(x=1/p\), se obtiene
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
Así, la constante buscada es
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
Las implementaciones también siguen el promedio auxiliar que aparece si se reemplaza el denominador \(p-1\) por \(p\):
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
La misma cuenta da
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
Esta segunda serie se contrasta numéricamente con un promedio directo sobre un gran tramo inicial de enteros, lo que sirve como comprobación independiente de la derivación.
Las primeras contribuciones a \(A\) pueden escribirse a mano.
Para \(p=2\), \(D(2)=1\), así que la contribución es
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
Para \(p=3\), \(D(3)=1/2\), así que la contribución es
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
Para \(p=5\), \(D(5)=1/3\), así que la contribución es
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
Después de solo tres primos, la suma parcial vale
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333,$$
lo que ya muestra la rapidez de convergencia.
Como \(0<D(p)\le 1\), cada término omitido más allá de un corte \(B\) está acotado por \(1/(p(p-1)^2)\), que es del orden de \(1/p^3\). La cola converge entonces de manera absoluta y muy rápida.
La implementación usa la cota explícita
$$R_B<\frac{1}{2B^2}.$$
Con \(B=2\cdot 10^6\), esta cota es menor que \(5\times 10^{-13}\), muy por debajo de la precisión decimal mostrada.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta \(2\cdot 10^6\) mediante una criba estándar. Luego recorren esos primos en orden creciente manteniendo el producto acumulado \(D(p)\), que se actualiza multiplicando por \((p-1)/p\) al pasar de un primo al siguiente.
En cada primo, la implementación añade el término objetivo \(D(p)/(p(p-1)^2)\) a la suma principal. También acumula el término auxiliar \(D(p)/(p^2(p-1))\), porque esa constante secundaria se usa como control numérico del razonamiento.
La implementación en C++ agrega dos comprobaciones más. Primero verifica que la cota de la cola en el corte elegido sea menor que \(5\times 10^{-13}\). Después compara la serie auxiliar tanto con el valor decimal conocido \(0.282419756159\) como con un promedio directo sobre los primeros \(200000\) enteros, calculando en cada caso el menor primo y su exponente. Las implementaciones en Python y Java conservan la misma suma de series, pero omiten esas verificaciones extra y simplemente imprimen el valor objetivo con \(12\) decimales.
Sea \(B=2\cdot 10^6\) el límite de la criba. Construir la lista de primos cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. La suma posterior visita cada primo una sola vez, por lo que requiere \(O(\pi(B))\) operaciones aritméticas. La aritmética decimal de alta precisión solo cambia los factores constantes. En conjunto, el método usa \(O(B)\) memoria y corre en \(O(B\log\log B)\) tiempo.
对每个 \(n>1\)，记 \(s(n)\) 为它的最小素因子，记 \(a(n)=v_{s(n)}(n)\) 为这个最小素因子在 \(n\) 中的指数。题目要求计算极限平均值
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
真正可行的做法不是直接枚举整数，而是按“最小素因子是什么”和“这个素因子的指数是多少”来分类。这样就能把原来的极限问题化成一个在素数上的快速收敛级数。
下面用自然密度来推导公式。对固定素数 \(p\)，定义
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
这个量表示“一个整数不被任何比 \(p\) 小的素数整除”的自然密度，因此当最小素因子恰好是 \(p\) 时，它就是必须出现的前缀因子。
若 \(s(n)=p\)，那么所有小于 \(p\) 的素数 \(q\) 都不能整除 \(n\)。在自然密度意义下，每个条件 \(q\nmid n\) 都贡献一个因子 \(1-1/q\)，于是
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
例如，\(D(2)=1\)，\(D(3)=1/2\)，而
$$D(5)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=\frac{1}{3}.$$
这一步把“最小素因子必须是 \(p\)”的限制完整地编码成了一个乘积。
现在固定 \(p\)，再固定指数 \(k\ge 1\)。条件 \(a(n)=k\) 的意思是 \(p^k\mid n\)，但 \(p^{k+1}\nmid n\)。因此与 \(p\) 有关的密度部分是
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
再乘上步骤 1 中来自更小素数的因子，就得到联合密度
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
也就是说，\(\delta_{p,k}\) 正是“最小素因子等于 \(p\)，且该素因子的指数恰好等于 \(k\)”这一类整数在整体中的密度。
对于这一类整数，被平均的值是 \((k-1)/(p-1)\)。因此总平均值可写成
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
令 \(m=k-1\)，则内层和为
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
再利用标准恒等式
$$\sum_{m\ge 0}mx^m=\frac{x}{(1-x)^2},\qquad |x|<1,$$
取 \(x=1/p\)，便得到
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
于是所求常数化为
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
这就是三个实现实际累加的主公式。
实现中还会同时跟踪一个辅助平均值，即把分母中的 \(p-1\) 换成 \(p\)：
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
完全相同的密度分解给出
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
这个辅助级数不是最终输出，但它适合做数值核对：可以直接在一大段初始整数上计算平均值，然后与级数结果比较，从而验证推导过程是否正确。
主级数 \(A\) 的前几项可以直接算出来。
当 \(p=2\) 时，\(D(2)=1\)，所以贡献是
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
当 \(p=3\) 时，\(D(3)=1/2\)，所以贡献是
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
当 \(p=5\) 时，\(D(5)=1/3\)，所以贡献是
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
因此只看前三个素数，就已经得到部分和
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333.$$
这说明该级数收敛得非常快，也解释了为什么只求到一个较大的素数界就足够得到稳定的 \(12\) 位小数。
由于 \(0<D(p)\le 1\)，当只累加到某个界 \(B\) 时，剩余尾项满足“每一项都不超过 \(1/(p(p-1)^2)\)”。该量是 \(1/p^3\) 量级，因此尾和绝对收敛并且非常小。
实现中采用的显式估计是
$$R_B<\frac{1}{2B^2}.$$
把 \(B=2\cdot 10^6\) 代入，可得尾项小于 \(5\times 10^{-13}\)。这比最终显示的 \(12\) 位小数还要小得多，所以数值精度是足够的。
C++、Python 和 Java 实现都先用标准筛法生成不超过 \(2\cdot 10^6\) 的全部素数。随后它们按素数递增顺序维护前缀乘积 \(D(p)\)，每处理完一个素数，就乘上 \((p-1)/p\) 以推进到下一个素数对应的前缀状态。
对每个素数，程序把主项 \(D(p)/(p(p-1)^2)\) 加入最终总和。同时也累加辅助项 \(D(p)/(p^2(p-1))\)，因为这个辅助常数会被拿来做数值交叉验证。
C++ 实现还额外做了两项检查。第一项是验证在所选截断界处，尾项上界确实小于 \(5\times 10^{-13}\)。第二项是把辅助级数同时与已知的小数值 \(0.282419756159\) 以及前 \(200000\) 个整数上的直接平均值进行比较，其中直接平均值是通过提取每个整数的最小素因子及其指数得到的。Python 和 Java 实现保留同样的级数求和逻辑，但省略这些断言，只输出主级数的 \(12\) 位小数结果。
设筛法上界为 \(B=2\cdot 10^6\)。构造素数表的时间复杂度是 \(O(B\log\log B)\)，空间复杂度是 \(O(B)\)。后续求和阶段只访问每个素数一次，因此需要 \(O(\pi(B))\) 次高精度算术操作。高精度小数只影响常数，不改变渐近阶。总的来说，该方法时间复杂度为 \(O(B\log\log B)\)，空间复杂度为 \(O(B)\)。
Для каждого целого \(n>1\) обозначим через \(s(n)\) его наименьший простой делитель, а через \(a(n)=v_{s(n)}(n)\) показатель этого простого в разложении числа \(n\). Требуется вычислить предельное среднее
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
Прямой перебор здесь не нужен. Намного выгоднее сгруппировать числа по их наименьшему простому делителю и по точному показателю этого делителя. Тогда задача превращается в сходящийся ряд по простым числам.
Будем рассуждать через естественные плотности. Для фиксированного простого \(p\) положим
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Это плотность чисел, не делящихся ни на один простой \(q<p\). Именно такой множитель нужен, когда наименьший простой делитель должен быть равен \(p\).
Условие \(s(n)=p\) означает, что ни один простой \(q<p\) не делит \(n\). В терминах естественной плотности каждое условие \(q\nmid n\) дает множитель \(1-1/q\). Поэтому
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
Например, \(D(2)=1\), \(D(3)=1/2\), а
$$D(5)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=\frac{1}{3}.$$
Теперь зафиксируем \(p\) и показатель \(k\ge 1\). Условие \(a(n)=k\) эквивалентно тому, что \(p^k\mid n\), но \(p^{k+1}\nmid n\). Значит, вклад \(p\)-части равен
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
Умножая на множитель для меньших простых, получаем совместную плотность
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
Это и есть плотность чисел, у которых наименьший простой делитель равен \(p\), а его показатель равен ровно \(k\).
Каждое такое число вносит в среднее величину \((k-1)/(p-1)\). Поэтому
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
Если положить \(m=k-1\), то
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
Используя тождество \(\sum_{m\ge 0}mx^m=x/(1-x)^2\) при \(x=1/p\), получаем
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
Следовательно, искомая константа равна
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
Реализации также сопровождают вычисление вспомогательным средним, где знаменатель \(p-1\) заменен на \(p\):
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
Та же самая схема дает
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
Этот ряд напрямую сравнивается с эмпирическим средним на большом начальном отрезке натуральных чисел, что служит независимой численной проверкой всей плотностной модели.
Первые вклады в \(A\) легко выписать явно.
Для \(p=2\) имеем \(D(2)=1\), поэтому вклад равен
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
Для \(p=3\) имеем \(D(3)=1/2\), поэтому вклад равен
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
Для \(p=5\) имеем \(D(5)=1/3\), поэтому вклад равен
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
Уже после трех простых получаем частичную сумму
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333,$$
что наглядно показывает очень быструю сходимость ряда.
Поскольку \(0<D(p)\le 1\), каждый отброшенный член после границы \(B\) не превосходит \(1/(p(p-1)^2)\), а это величина порядка \(1/p^3\). Следовательно, хвост сходится абсолютно и очень быстро.
В реализации используется явная оценка
$$R_B<\frac{1}{2B^2}.$$
При \(B=2\cdot 10^6\) это меньше \(5\times 10^{-13}\), то есть намного ниже уровня печатаемых \(12\) знаков после запятой.
Реализации на C++, Python и Java сначала строят список всех простых чисел до \(2\cdot 10^6\) стандартным решетом. Затем они идут по простым в возрастающем порядке и поддерживают текущее произведение \(D(p)\), обновляя его умножением на \((p-1)/p\) после обработки очередного простого.
Для каждого простого числа в основную сумму добавляется целевой член \(D(p)/(p(p-1)^2)\). Одновременно накапливается и вспомогательный член \(D(p)/(p^2(p-1))\), поскольку эта вторая константа используется как численная проверка вывода.
Реализация на C++ выполняет еще две проверки. Во-первых, она удостоверяется, что явная оценка хвоста при выбранной границе меньше \(5\times 10^{-13}\). Во-вторых, она сравнивает вспомогательный ряд как с известным десятичным значением \(0.282419756159\), так и с прямым средним по первым \(200000\) числам, где для каждого числа вычисляются наименьший простой делитель и его показатель. Реализации на Python и Java оставляют ту же суммирующую схему, но не содержат этих дополнительных утверждений и просто печатают целевое значение с \(12\) знаками после запятой.
Пусть \(B=2\cdot 10^6\) — граница решета. Построение списка простых требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Дальнейшее суммирование проходит по каждому простому ровно один раз и потому стоит \(O(\pi(B))\) арифметических операций. Высокоточная десятичная арифметика увеличивает только константы. В итоге метод работает за \(O(B\log\log B)\) времени и использует \(O(B)\) памяти.
لكل عدد صحيح \(n>1\)، نرمز بـ \(s(n)\) إلى أصغر عامل أولي له، وبـ \(a(n)=v_{s(n)}(n)\) إلى أس هذا العامل الأولي في تحليل \(n\). المطلوب هو حساب المتوسط الحدّي
$$A=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)-1}.$$
الفكرة الأساسية ليست فحص كل عدد على حدة، بل تجميع الأعداد بحسب أصغر عامل أولي لها وبحسب الأس الدقيق لذلك العامل. وبهذا تتحول المسألة إلى سلسلة متقاربة على الأعداد الأولية.
سنستخدم مفهوم الكثافة الطبيعية. لعدد أولي ثابت \(p\)، نعرّف
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
هذا المقدار هو كثافة الأعداد التي لا يقسمها أي عدد أولي أصغر من \(p\)، ولذلك فهو العامل التمهيدي الصحيح عندما يكون أصغر عامل أولي مساويًا لـ \(p\) بالضبط.
الشرط \(s(n)=p\) يعني أن كل عدد أولي \(q<p\) لا يقسم \(n\). وفي الكثافة الطبيعية يضيف كل شرط من الصورة \(q\nmid n\) العامل \(1-1/q\). لذلك نحصل على
$$D(p)=\prod_{q<p}\left(1-\frac{1}{q}\right).$$
على سبيل المثال، \(D(2)=1\)، و\(D(3)=1/2\)، و
$$D(5)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=\frac{1}{3}.$$
ثبّت الآن \(p\) وثبّت الأس \(k\ge 1\). الشرط \(a(n)=k\) يعني أن \(p^k\mid n\) ولكن \(p^{k+1}\nmid n\). ومن ثم يكون الجزء الخاص بـ \(p\) ذا كثافة
$$\frac{1}{p^k}-\frac{1}{p^{k+1}}=\frac{p-1}{p^{k+1}}.$$
وعند ضرب هذا في عامل الأعداد الأولية الأصغر نحصل على الكثافة المشتركة
$$\delta_{p,k}=D(p)\frac{p-1}{p^{k+1}},\qquad k\ge 1.$$
وهذه هي بالضبط كثافة الأعداد التي أصغر عامل أولي لها هو \(p\) ويظهر فيها هذا العامل بالأس \(k\) تحديدًا.
كل عدد من هذا النوع يساهم بالمقدار \((k-1)/(p-1)\) في المتوسط. لذلك
$$A=\sum_{p}\sum_{k\ge 1}\delta_{p,k}\frac{k-1}{p-1}=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p^{k+1}}.$$
إذا وضعنا \(m=k-1\)، صار المجموع الداخلي
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\sum_{m\ge 0}\frac{m}{p^m}.$$
وباستخدام الهوية القياسية \(\sum_{m\ge 0}mx^m=x/(1-x)^2\) عند \(x=1/p\)، نحصل على
$$\sum_{k\ge 1}\frac{k-1}{p^{k+1}}=\frac{1}{p^2}\cdot\frac{1/p}{(1-1/p)^2}=\frac{1}{p(p-1)^2}.$$
إذًا تصبح القيمة المطلوبة
$$\boxed{A=\sum_{p}\frac{D(p)}{p(p-1)^2}=\sum_{p}\frac{1}{p(p-1)^2}\prod_{q<p}\left(1-\frac{1}{q}\right).}$$
تتابع التطبيقات أيضًا متوسطًا مساعدًا يُستبدل فيه المقام \(p-1\) بالمقام \(p\):
$$A_1=\lim_{N\to\infty}\frac{1}{N-1}\sum_{n=2}^{N}\frac{a(n)-1}{s(n)}.$$
ونفس التفكيك يعطي
$$A_1=\sum_{p}D(p)\sum_{k\ge 1}\frac{k-1}{p}\cdot\frac{p-1}{p^{k+1}}=\sum_{p}\frac{D(p)}{p^2(p-1)}.$$
هذه السلسلة ليست هي الناتج النهائي، لكنها مفيدة جدًا كفحص عددي مستقل، لأن بالإمكان مقارنتها بمتوسط مباشر على مقطع كبير من الأعداد الأولى.
يمكن حساب أوائل مساهمات السلسلة \(A\) يدويًا.
عند \(p=2\) يكون \(D(2)=1\)، ومن ثم تكون المساهمة
$$\frac{1}{2(2-1)^2}=\frac{1}{2}.$$
وعند \(p=3\) يكون \(D(3)=1/2\)، فتكون المساهمة
$$\frac{1/2}{3(3-1)^2}=\frac{1}{24}.$$
وعند \(p=5\) يكون \(D(5)=1/3\)، فتكون المساهمة
$$\frac{1/3}{5(5-1)^2}=\frac{1}{240}.$$
وبعد أول ثلاثة أعداد أولية فقط يصبح المجموع الجزئي
$$\frac{1}{2}+\frac{1}{24}+\frac{1}{240}=\frac{131}{240}\approx 0.5458333333,$$
وهذا يوضح أن التقارب سريع جدًا.
بما أن \(0<D(p)\le 1\)، فإن كل حد مهمل بعد قطع عند \(B\) لا يتجاوز \(1/(p(p-1)^2)\)، وهو من رتبة \(1/p^3\). لذلك فإن الذيل متقارب تقاربًا مطلقًا وصغير للغاية.
وتستعمل التطبيقات التقدير الصريح
$$R_B<\frac{1}{2B^2}.$$
وعند \(B=2\cdot 10^6\) يصبح هذا أصغر من \(5\times 10^{-13}\)، أي أقل بكثير من دقة العرض ذات \(12\) منزلة عشرية.
تقوم تطبيقات C++ وPython وJava أولًا بتوليد جميع الأعداد الأولية حتى \(2\cdot 10^6\) باستخدام غربال قياسي. ثم تمر على هذه الأوليات تصاعديًا مع الحفاظ على حاصل الضرب التراكمي \(D(p)\)، ويُحدَّث هذا الحاصل بعد كل عدد أولي بضربه في \((p-1)/p\).
وعند كل عدد أولي تُضاف القيمة \(D(p)/(p(p-1)^2)\) إلى المجموع الرئيسي. وفي الوقت نفسه تُجمع القيمة المساعدة \(D(p)/(p^2(p-1))\)، لأن هذه الكمية الثانية تُستخدم كاختبار عددي لاشتقاق الصيغة.
تضيف نسخة C++ فحصين إضافيين. الأول هو التأكد من أن حد الذيل عند نقطة القطع المختارة أصغر من \(5\times 10^{-13}\). والثاني هو مقارنة السلسلة المساعدة بكل من القيمة العشرية المعروفة \(0.282419756159\) ومتوسط مباشر على أول \(200000\) عدد، حيث يُستخرج من كل عدد أصغر عامل أولي له وأسه. أما نسختا Python وJava فتحتفظان بنفس عملية جمع السلسلة، لكنهما تحذفان هذه الاختبارات الإضافية وتطبعان القيمة الهدف فقط إلى \(12\) منزلة عشرية.
ليكن \(B=2\cdot 10^6\) هو حد الغربال. بناء قائمة الأوليات يحتاج إلى زمن \(O(B\log\log B)\) وذاكرة \(O(B)\). بعد ذلك تمر مرحلة الجمع على كل عدد أولي مرة واحدة فقط، فتحتاج إلى \(O(\pi(B))\) خطوة حسابية. والحسابات العشرية عالية الدقة لا تغير الرتبة التقاربية، بل تزيد الثوابت فقط. لذلك فإن الخوارزمية تعمل في \(O(B\log\log B)\) زمنًا وتستخدم \(O(B)\) ذاكرة.