For each odd prime \(p \lt 10^6\), Problem 826 leads to a single problem-specific quantity from the birds-on-a-wire setting. The C++, Python, and Java implementations do not simulate wire configurations directly. Instead, they rely on the already derived closed form
$$B(p)=\frac{7p+15}{18(p+1)}.$$
The final answer is the arithmetic mean of \(B(p)\) over all odd primes below \(10^6\). Once that formula is known, the job becomes purely computational: generate the relevant primes, evaluate the rational expression for each one, and average the results.
Let
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ is prime}\}.$$
The required value is
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
The mathematics used by the implementations is the reduction of the original combinatorial quantity to this prime-indexed rational function.
For every admissible prime \(p\), the quantity attached to the problem is already known in exact form:
$$B(p)=\frac{7p+15}{18(p+1)}.$$
This is the decisive simplification. There is no remaining state space to enumerate, no random process to simulate, and no recursive structure to evaluate. The whole problem collapses to averaging one rational expression over a specified set of primes.
The implementations average only over odd primes strictly smaller than \(10^6\). That is why the set begins at \(3\) and why \(p=2\) is skipped.
So the answer is not a weighted sum, and it is not an average over all integers. It is the simple arithmetic mean
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
where \(p_1,p_2,\dots,p_k\) are exactly the primes in \(\mathcal P\).
A useful algebraic rewrite is
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
This makes the structure transparent. Most of the value comes from the constant term \(7/18\), while the dependence on \(p\) is entirely contained in the smaller correction term \(4/(9(p+1))\).
Because \(p\ge 3\), the correction is always positive and at most \(1/9\). Therefore
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
The upper endpoint occurs at the smallest allowed prime \(p=3\), and larger primes push the value downward toward \(7/18\).
Substituting the decomposition into the mean gives
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
This identity is mathematically simple but conceptually useful. It shows that the answer is a fixed baseline \(7/18\) plus the average of a decaying reciprocal correction. In particular, the result must lie only slightly above \(7/18\), because \(1/(p+1)\) becomes small very quickly.
If we temporarily replace the full prime set by the smaller set \(\{3,5,7\}\), then
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
Their arithmetic mean is
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
The same procedure is what the implementations apply to the full set of odd primes below \(10^6\); only the size of the prime set changes.
The C++, Python, and Java implementations all follow the same numerical pipeline. First they build a sieve of Eratosthenes up to \(10^6\), which marks exactly which integers are prime.
They then iterate through the valid odd primes, evaluate
$$\frac{7p+15}{18(p+1)}$$
for each one, add that value to a running sum, and increment a counter. After the loop finishes, they divide the accumulated sum by the number of processed primes to obtain the mean.
One implementation also includes a small checkpoint at \(p=3\), verifying numerically that the formula gives \(1/2\). Finally, all three implementations print the result with ten digits after the decimal point.
Let \(n=10^6\). Building the sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. The averaging pass is linear in the number of integers scanned, or equivalently \(O(\pi(n))\) arithmetic evaluations over the primes themselves. Since the closed formula is constant-time to evaluate, the sieve dominates the running time, and the overall memory usage stays \(O(n)\).
Für jede ungerade Primzahl \(p \lt 10^6\) führt Problem 826 auf eine einzelne problemspezifische Größe aus dem Birds-on-a-Wire-Modell. Die C++, Python- und Java-Implementierungen simulieren keine Konfigurationen auf dem Draht, sondern verwenden direkt die bereits hergeleitete geschlossene Formel
$$B(p)=\frac{7p+15}{18(p+1)}.$$
Gesucht ist der arithmetische Mittelwert von \(B(p)\) über alle ungeraden Primzahlen unter \(10^6\). Sobald diese Formel feststeht, bleibt nur noch effiziente Primzahlerzeugung plus eine numerisch saubere Mittelung.
Sei
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ ist prim}\}.$$
Dann lautet die Zielgröße
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
Die Mathematik der Implementierung besteht also darin, die ursprüngliche kombinatorische Größe auf diese rationale Funktion in der Primvariablen zurückzuführen.
Für jede zulässige Primzahl \(p\) ist die relevante Größe exakt durch
$$B(p)=\frac{7p+15}{18(p+1)}$$
gegeben. Das ist die eigentliche Vereinfachung des Problems. Es gibt keinen verbleibenden Zustandsraum, der noch durchsucht werden müsste, und auch keine Simulation eines Zufallsprozesses. Übrig bleibt allein das Auswerten einer rationalen Funktion.
Gemittelt wird nur über ungerade Primzahlen kleiner als \(10^6\). Deshalb beginnt die Menge bei \(3\), und deshalb wird \(p=2\) explizit ausgeschlossen.
Die gesuchte Zahl ist also der gewöhnliche arithmetische Mittelwert
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
wobei \(p_1,p_2,\dots,p_k\) genau die Primzahlen aus \(\mathcal P\) sind.
Eine nützliche Umformung lautet
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
Damit wird die Struktur sofort sichtbar: Der Hauptbeitrag ist die Konstante \(7/18\), und die gesamte \(p\)-Abhängigkeit steckt in der kleineren Korrektur \(4/(9(p+1))\).
Weil \(p\ge 3\) gilt, ist die Korrektur stets positiv und höchstens \(1/9\). Daher folgt
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
Das Maximum wird bei \(p=3\) erreicht; für größere Primzahlen nähert sich \(B(p)\) dem Grenzwert \(7/18\) von oben.
Setzt man die Zerlegung in den Mittelwert ein, erhält man
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
Diese Identität zeigt, dass die gesuchte Zahl aus einem festen Basiswert \(7/18\) plus dem Mittel einer schnell kleiner werdenden reziproken Korrektur besteht. Deshalb liegt das Gesamtergebnis nur wenig über \(7/18\).
Ersetzt man die volle Primzahlmenge testweise durch \(\{3,5,7\}\), so gilt
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
Der arithmetische Mittelwert ist dann
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
Genau dieselbe Rechnung wird in der Implementierung für alle ungeraden Primzahlen unter \(10^6\) durchgeführt.
Die C++, Python- und Java-Implementierungen verwenden dieselbe Rechenkette. Zuerst bauen sie ein Sieb des Eratosthenes bis \(10^6\) auf und markieren damit alle Primzahlen.
Danach laufen sie über die gültigen ungeraden Primzahlen, werten
$$\frac{7p+15}{18(p+1)}$$
für jede dieser Primzahlen aus, addieren den Wert zu einer laufenden Summe und erhöhen einen Zähler. Nach Abschluss der Schleife wird die Summe durch die Anzahl der berücksichtigten Primzahlen geteilt.
Eine der Implementierungen enthält zusätzlich einen kleinen Kontrolltest bei \(p=3\), der numerisch \(B(3)=1/2\) bestätigt. Anschließend wird das Ergebnis mit zehn Nachkommastellen ausgegeben.
Mit \(n=10^6\) kostet das Sieb \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Die anschließende Mittelung benötigt nur konstante Arbeit pro relevanter Primzahl, also insgesamt \(O(\pi(n))\) Auswertungen. Da die Formel selbst in konstanter Zeit berechnet wird, dominiert das Sieb die Laufzeit, und der Speicherverbrauch bleibt \(O(n)\).
Problem 826, her \(p \lt 10^6\) tek asalı için birds-on-a-wire modelinden gelen tek bir problemsel büyüklüğe indirgeniyor. C++, Python ve Java uygulamaları tel üzerindeki olası yerleşimleri tek tek simüle etmiyor; bunun yerine doğrudan şu kapalı formülü kullanıyor:
$$B(p)=\frac{7p+15}{18(p+1)}.$$
İstenen sonuç, bu değerin \(10^6\)'dan küçük tüm tek asallar üzerindeki aritmetik ortalamasıdır. Dolayısıyla kapalı formül elde edildikten sonra geriye kalan iş, asal sayıları hızlı üretmek ve rasyonel ifadeyi güvenilir biçimde ortalamaktır.
Şunu tanımlayalım:
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ asaldır}\}.$$
Aranan değer
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p)$$
şeklindedir. Yani uygulamaların kullandığı matematik, özgün kombinatorik niceliği prime bağlı bu rasyonel ifadeye indirgemekten ibarettir.
Her uygun asal \(p\) için problemdeki nicelik tam olarak
$$B(p)=\frac{7p+15}{18(p+1)}$$
olur. Asıl kırılma noktası budur. Artık taranacak bir durum uzayı, çalıştırılacak bir simülasyon ya da derin bir dinamik programlama yapısı kalmaz. Bütün hesap tek bir rasyonel fonksiyonun farklı asallarda değerlendirilmesine dönüşür.
Ortalama tüm tamsayılar üzerinde değil, yalnızca \(10^6\)'dan küçük tek asallar üzerinde alınır. Bu yüzden küme \(3\)'ten başlar ve \(p=2\) özellikle dışarıda bırakılır.
Dolayısıyla sonuç sıradan bir aritmetik ortalamadır:
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
burada \(p_1,p_2,\dots,p_k\), \(\mathcal P\) içindeki asalların tamamıdır.
Şu cebirsel dönüşüm çok faydalıdır:
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
Böylece yapıyı açıkça görürüz. Değerin büyük kısmı sabit \(7/18\) teriminden gelir; \(p\)'ye bağlı olan bölüm ise yalnızca \(4/(9(p+1))\) düzeltmesidir.
\(p\ge 3\) olduğundan bu düzeltme her zaman pozitiftir ve en fazla \(1/9\) olabilir. Bu da
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}$$
eşitsizliğini verir. En büyük değer \(p=3\) için oluşur; daha büyük asallarda değer yukarıdan \(7/18\)'e yaklaşır.
Bu ayrışımı ortalamaya yerleştirince
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}$$
elde edilir. Bu kimlik, cevabın sabit bir taban değer olan \(7/18\) ile hızlı küçülen bir karşılık düzeltmesinin ortalamasından oluştuğunu gösterir. Bu nedenle toplam sonuç \(7/18\)'in biraz üstünde kalır.
Tam asal kümesi yerine geçici olarak \(\{3,5,7\}\) alınırsa
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
Bunların aritmetik ortalaması
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025$$
olur. Uygulamaların yaptığı işlem bunun aynısıdır; yalnızca kullanılan asal kümesi çok daha büyüktür.
C++, Python ve Java uygulamalarının hepsi aynı hesap akışını kullanır. İlk olarak \(10^6\)'ya kadar bir Eratosthenes eleği kurulur ve hangi sayıların asal olduğu işaretlenir.
Ardından geçerli tek asallar üzerinde dolaşılıp
$$\frac{7p+15}{18(p+1)}$$
hesaplanır, bu değer çalışan toplama eklenir ve sayaç artırılır. Döngü bittiğinde toplam, işlenen asal sayısına bölünerek ortalama elde edilir.
Uygulamalardan biri ayrıca \(p=3\) için formülün \(1/2\) verdiğini küçük bir kontrol olarak doğrular. Son aşamada sonuç ondalık noktadan sonra on basamakla yazdırılır.
\(n=10^6\) olmak üzere elek kurma maliyeti \(O(n\log\log n)\) zaman ve \(O(n)\) bellektir. Ortalama alma aşaması, ilgili asal başına sabit iş yaptığı için \(O(\pi(n))\) değerlendirme gerektirir. Kapalı formül sabit zamanda hesaplandığından toplam çalışma süresini elek belirler; bellek kullanımı da \(O(n)\) düzeyinde kalır.
Para cada primo impar \(p \lt 10^6\), el Problema 826 queda reducido a una sola cantidad propia del modelo de birds-on-a-wire. Las implementaciones en C++, Python y Java no simulan configuraciones del alambre; usan directamente la forma cerrada ya obtenida
$$B(p)=\frac{7p+15}{18(p+1)}.$$
La salida final es la media aritmética de \(B(p)\) sobre todos los primos impares menores que \(10^6\). Una vez conocida la fórmula, el trabajo restante es puramente computacional: generar los primos válidos, evaluar la expresión racional y promediar.
Sea
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ es primo}\}.$$
La cantidad pedida es
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
La matemática usada por la implementación consiste en reemplazar la cantidad combinatoria original por esta función racional indexada por primos.
Para cada primo permitido \(p\), la cantidad relevante del problema es exactamente
$$B(p)=\frac{7p+15}{18(p+1)}.$$
Esa es la simplificación decisiva. Ya no queda un espacio de estados por recorrer, ni una simulación probabilística que ejecutar. Todo se reduce a evaluar una función racional sencilla en muchos primos y luego tomar la media.
La media se toma solo sobre los primos impares estrictamente menores que \(10^6\). Por eso el conjunto empieza en \(3\) y por eso \(p=2\) queda fuera.
En consecuencia, la respuesta es la media aritmética ordinaria
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
donde \(p_1,p_2,\dots,p_k\) son exactamente los primos de \(\mathcal P\).
Conviene reescribir la fórmula como
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
Así la estructura queda clara: la mayor parte del valor proviene del término constante \(7/18\), mientras que toda la dependencia respecto de \(p\) vive en la corrección más pequeña \(4/(9(p+1))\).
Como \(p\ge 3\), esa corrección siempre es positiva y nunca supera \(1/9\). Por tanto,
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
El valor máximo aparece en \(p=3\), y cuando \(p\) crece la expresión baja hacia \(7/18\).
Al sustituir la descomposición en la media obtenemos
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
Esta identidad muestra que la respuesta es una base fija \(7/18\) más la media de una corrección recíproca decreciente. Por eso el valor final debe quedar solo un poco por encima de \(7/18\).
Si, solo como ejemplo, reemplazamos el conjunto completo de primos por \(\{3,5,7\}\), entonces
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
La media aritmética vale
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
Las implementaciones hacen exactamente este cálculo, pero sobre todo el conjunto de primos impares menor que \(10^6\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen una criba de Eratóstenes hasta \(10^6\), con lo que identifican cuáles enteros son primos.
Luego recorren los primos impares válidos, evalúan
$$\frac{7p+15}{18(p+1)}$$
para cada uno, suman ese valor a un acumulador y aumentan un contador. Al terminar el recorrido, dividen la suma total por la cantidad de primos procesados.
Una de las implementaciones también incorpora una comprobación pequeña en \(p=3\), verificando numéricamente que la fórmula produce \(1/2\). Al final, las tres versiones imprimen el resultado con diez cifras decimales.
Sea \(n=10^6\). Construir la criba cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. La fase de promedio requiere trabajo constante por primo relevante, es decir \(O(\pi(n))\) evaluaciones. Como la fórmula cerrada se calcula en tiempo constante, la criba domina el coste total y el uso de memoria permanece en \(O(n)\).
对于每个满足 \(p \lt 10^6\) 的奇素数，Problem 826 都会对应到 birds-on-a-wire 模型中的一个特定数值。C++、Python 和 Java 实现都没有去枚举电线上的具体排列状态，而是直接使用已经推导好的闭式公式
$$B(p)=\frac{7p+15}{18(p+1)}.$$
最终答案就是把这个数值在所有小于 \(10^6\) 的奇素数上取算术平均。也就是说，一旦闭式公式成立，剩下的工作就不再是组合状态分析，而只是高效筛素数、逐个代入公式并求平均。
设
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ is prime}\}.$$
题目要求的量为
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
因此，实现所依赖的核心数学事实，就是把原题中的目标量彻底化简成一个由素数 \(p\) 驱动的有理函数。
对每一个允许的素数 \(p\)，问题中的目标值都已经被写成精确表达式
$$B(p)=\frac{7p+15}{18(p+1)}.$$
这一步是决定性的。因为一旦有了这个公式，就不需要继续做状态搜索，也不需要对随机过程进行模拟，更不需要递推或动态规划。整个任务直接变成“对很多个素数代入同一个分式”。
平均并不是对所有整数取，也不是对所有素数取，而是只对严格小于 \(10^6\) 的奇素数取平均。所以集合从 \(3\) 开始，\(p=2\) 被显式排除。
因此最终结果就是普通的算术平均：
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
其中 \(p_1,p_2,\dots,p_k\) 正好是 \(\mathcal P\) 中的全部素数。
把公式改写成下面的形式非常有帮助：
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
这样结构就一目了然了。数值的主体是常数项 \(7/18\)，而与 \(p\) 有关的部分全部集中在较小的修正项 \(4/(9(p+1))\) 里。
由于 \(p\ge 3\)，修正项始终为正，而且最大不会超过 \(1/9\)。于是有
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
上界在最小允许素数 \(p=3\) 处取得；随着 \(p\) 变大，\(B(p)\) 会从上方逐渐逼近 \(7/18\)。
将上面的分解代入平均式，可得
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
这个恒等式说明，最终答案可以看成“固定基线 \(7/18\)”再加上“一个随素数增大而快速衰减的倒数修正项的平均值”。因此整体结果一定只会比 \(7/18\) 稍大一些，而不会偏离太远。
如果为了演示，把完整素数集合暂时换成 \(\{3,5,7\}\)，那么
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
它们的算术平均为
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
真正的实现所做的事情完全一样，只不过把这个演示集合换成了所有小于 \(10^6\) 的奇素数。
C++、Python 和 Java 实现遵循相同的计算流程。第一步是构建一个到 \(10^6\) 为止的埃拉托斯特尼筛，用它来标记哪些整数是素数。
接着遍历所有合法的奇素数，对每个 \(p\) 计算
$$\frac{7p+15}{18(p+1)}$$
并把结果加入累计和，同时把计数器加一。循环结束后，再用总和除以处理过的素数个数，就得到最终平均值。
其中一个实现还包含一个很小的数值校验：在 \(p=3\) 时确认公式确实给出 \(1/2\)。最后，三个实现都会把答案格式化为小数点后十位输出。
令 \(n=10^6\)。筛法的时间复杂度是 \(O(n\log\log n)\)，空间复杂度是 \(O(n)\)。之后的平均阶段对每个相关素数只做常数次运算，因此是 \(O(\pi(n))\)。由于闭式公式本身是常数时间求值，整体运行时间主要由筛法决定，总空间使用量保持在 \(O(n)\)。
Для каждого нечётного простого числа \(p \lt 10^6\) задача 826 сводится к одной специальной величине из модели birds-on-a-wire. Реализации на C++, Python и Java не перебирают конфигурации на проволоке напрямую, а сразу используют уже выведенную замкнутую формулу
$$B(p)=\frac{7p+15}{18(p+1)}.$$
Итоговый ответ равен среднему арифметическому значений \(B(p)\) по всем нечётным простым меньше \(10^6\). После получения этой формулы вся задача становится вычислительной: нужно быстро построить множество простых, подставить каждое число в дробно-рациональное выражение и усреднить результат.
Пусть
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ is prime}\}.$$
Тогда искомая величина равна
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
Следовательно, используемая в программе математика состоит в том, что исходная комбинаторная величина заменяется этой рациональной функцией от простого параметра \(p\).
Для каждого допустимого простого \(p\) нужная величина точно задаётся формулой
$$B(p)=\frac{7p+15}{18(p+1)}.$$
Именно это и даёт резкое упрощение. Не остаётся пространства состояний для перебора, не требуется моделирование случайного процесса и не нужна рекурсивная схема. Всё сводится к повторному вычислению одной рациональной функции.
Среднее берётся не по всем целым числам и не по всем простым, а только по нечётным простым, строго меньшим \(10^6\). Поэтому множество начинается с \(3\), а \(p=2\) исключается.
Значит, ответ есть обычное среднее арифметическое
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
где \(p_1,p_2,\dots,p_k\) — все простые из множества \(\mathcal P\).
Полезно переписать выражение так:
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
Теперь структура видна сразу. Основной вклад даёт константа \(7/18\), а вся зависимость от \(p\) сосредоточена в меньшей поправке \(4/(9(p+1))\).
Так как \(p\ge 3\), эта поправка всегда положительна и не превосходит \(1/9\). Поэтому
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
Максимум достигается при \(p=3\), а при росте \(p\) значение сверху стремится к \(7/18\).
Подстановка разложения в среднее даёт
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
Это тождество показывает, что ответ состоит из фиксированной базовой части \(7/18\) и среднего от быстро убывающей обратной поправки. Поэтому итоговое значение должно быть лишь немного больше \(7/18\).
Если для иллюстрации заменить полное множество простых на \(\{3,5,7\}\), то получаем
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
Их среднее арифметическое равно
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
В реализации выполняется точно та же операция, только по всем нечётным простым меньше \(10^6\).
Все три реализации используют один и тот же вычислительный конвейер. Сначала строится решето Эратосфена до \(10^6\), которое отмечает простые числа.
Затем программа проходит по допустимым нечётным простым, вычисляет
$$\frac{7p+15}{18(p+1)}$$
для каждого из них, добавляет это значение к накопленной сумме и увеличивает счётчик. После завершения прохода сумма делится на число обработанных простых.
Одна из реализаций также содержит небольшой контроль в точке \(p=3\), численно подтверждающий равенство \(B(3)=1/2\). После этого результат выводится с десятью знаками после запятой.
Пусть \(n=10^6\). Построение решета занимает \(O(n\log\log n)\) времени и \(O(n)\) памяти. Стадия усреднения требует постоянной работы на каждый релевантный простой, то есть \(O(\pi(n))\) вычислений. Поскольку сама замкнутая формула считается за константное время, решето доминирует по времени, а общий объём памяти остаётся \(O(n)\).
لكل عدد أولي فردي \(p \lt 10^6\)، تختزل المسألة 826 إلى كمية واحدة خاصة بنموذج birds-on-a-wire. لا تقوم تطبيقات ++C وPython وJava بمحاكاة الترتيبات على السلك مباشرة، بل تستخدم مباشرة الصيغة المغلقة المستنتجة مسبقًا
$$B(p)=\frac{7p+15}{18(p+1)}.$$
والناتج النهائي هو المتوسط الحسابي لهذه الكمية على جميع الأعداد الأولية الفردية الأصغر من \(10^6\). بعد معرفة هذه الصيغة، يصبح العمل كله حسابيًا: توليد الأعداد الأولية المطلوبة بكفاءة، ثم تقييم التعبير الكسري لكل عدد أولي، ثم أخذ المتوسط.
لنعرّف
$$\mathcal P=\{p: 3 \le p \lt 10^6,\ p \text{ is prime}\}.$$
إذن القيمة المطلوبة هي
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P} B(p).$$
وعليه فإن الجوهر الرياضي في التنفيذ هو أن الكمية التوافقية الأصلية قد اختُزلت إلى هذه الدالة الكسرية التي تعتمد على العدد الأولي \(p\).
لكل عدد أولي مسموح \(p\)، تكون الكمية المرتبطة بالمسألة مساوية تمامًا لـ
$$B(p)=\frac{7p+15}{18(p+1)}.$$
هذه هي النقلة الحاسمة. فلا يبقى فضاء حالات يحتاج إلى تعداد، ولا عملية عشوائية تحتاج إلى محاكاة، ولا بنية تكرارية معقدة. كل ما تبقّى هو تقييم دالة نسبية بسيطة على مجموعة كبيرة من الأعداد الأولية.
المتوسط لا يُؤخذ على جميع الأعداد الصحيحة، ولا حتى على جميع الأعداد الأولية، بل فقط على الأعداد الأولية الفردية الأصغر من \(10^6\). لهذا تبدأ المجموعة عند \(3\)، ولهذا يُستبعد \(p=2\).
إذن الجواب هو المتوسط الحسابي المعتاد
$$A=\frac{B(p_1)+B(p_2)+\cdots+B(p_k)}{k},$$
حيث تمثل \(p_1,p_2,\dots,p_k\) جميع عناصر المجموعة \(\mathcal P\).
من المفيد إعادة كتابة الصيغة على الصورة
$$B(p)=\frac{7p+15}{18(p+1)}=\frac{7(p+1)+8}{18(p+1)}=\frac{7}{18}+\frac{4}{9(p+1)}.$$
بهذه الصورة تصبح البنية أوضح. فمعظم القيمة يأتي من الحد الثابت \(7/18\)، أما اعتمادها على \(p\) كله فيظهر في حد التصحيح الأصغر \(4/(9(p+1))\).
وبما أن \(p\ge 3\)، فإن حد التصحيح موجب دائمًا ولا يزيد على \(1/9\). لذلك نحصل على
$$\frac{7}{18} \lt B(p)\le \frac{1}{2}.$$
وتتحقق القيمة العظمى عند \(p=3\)، ثم تنخفض القيم مع ازدياد \(p\) مقتربة من \(7/18\) من الأعلى.
بالتعويض عن هذا التفكيك داخل المتوسط نحصل على
$$A=\frac{1}{|\mathcal P|}\sum_{p\in\mathcal P}\left(\frac{7}{18}+\frac{4}{9(p+1)}\right)=\frac{7}{18}+\frac{4}{9|\mathcal P|}\sum_{p\in\mathcal P}\frac{1}{p+1}.$$
توضح هذه الهوية أن الجواب عبارة عن قيمة أساسية ثابتة مقدارها \(7/18\)، مضافًا إليها متوسط حد تصحيحي تناقصي من الشكل \(1/(p+1)\). ولذلك يجب أن تكون النتيجة النهائية أكبر قليلًا فقط من \(7/18\).
إذا استبدلنا مجموعة الأعداد الأولية الكاملة مؤقتًا بالمجموعة \(\{3,5,7\}\) من أجل التوضيح، فإن
$$B(3)=\frac{7\cdot 3+15}{18\cdot 4}=\frac{36}{72}=\frac{1}{2},$$
$$B(5)=\frac{7\cdot 5+15}{18\cdot 6}=\frac{50}{108}=\frac{25}{54},$$
$$B(7)=\frac{7\cdot 7+15}{18\cdot 8}=\frac{64}{144}=\frac{4}{9}.$$
ومن ثم يكون المتوسط الحسابي
$$\frac{1}{3}\left(\frac{1}{2}+\frac{25}{54}+\frac{4}{9}\right)=\frac{1}{3}\cdot\frac{76}{54}=\frac{38}{81}\approx 0.4691358025.$$
هذا هو بالضبط نوع الحساب الذي تنفذه التطبيقات، لكن على جميع الأعداد الأولية الفردية الأصغر من \(10^6\).
تتبع تطبيقات ++C وPython وJava المسار العددي نفسه. أولًا تُبنى غربال إراتوستينس حتى \(10^6\) لتحديد الأعداد الأولية.
بعد ذلك تمرّ الشيفرة على الأعداد الأولية الفردية المسموح بها، وتحسب
$$\frac{7p+15}{18(p+1)}$$
لكل واحد منها، ثم تضيف القيمة إلى مجموع تراكمي وتزيد العداد بمقدار واحد. وبعد انتهاء المرور، يُقسم المجموع على عدد الأعداد الأولية التي عولجت للحصول على المتوسط.
ويحتوي أحد التنفيذات أيضًا على فحص صغير عند \(p=3\) للتأكد عدديًا من أن الصيغة تعطي \(1/2\). وفي النهاية تُطبع النتيجة بعشرة منازل بعد الفاصلة العشرية.
إذا وضعنا \(n=10^6\)، فإن بناء الغربال يحتاج إلى زمن \(O(n\log\log n)\) وذاكرة \(O(n)\). أما مرحلة أخذ المتوسط فتستهلك عملًا ثابتًا لكل عدد أولي ذي صلة، أي \(O(\pi(n))\) من التقييمات. وبما أن حساب الصيغة المغلقة يتم في زمن ثابت، فإن الغربال هو العامل المسيطر على زمن التنفيذ الكلي، وتبقى الذاكرة الكلية من رتبة \(O(n)\).