The implemented quantity is an expected error term arising from approximating a weighted sum by sampling \(m\) distinct positions from \(\{1,\dots,n\}\) uniformly without replacement. If \(X\) denotes the smallest sampled position and \(f\) is the weight sequence, the error is the total weight lying strictly before the first sampled position:
$$\sum_{k=1}^{X-1} f(k).$$
For Problem 756 the weight is Euler's totient function, so \(f(k)=\varphi(k)\), and the production parameters are \(n=12{,}345{,}678\) and \(m=12{,}345\). The goal is therefore to evaluate the corresponding expectation accurately and efficiently.
Write \(S\subseteq\{1,\dots,n\}\) for the uniformly chosen set of size \(m\), and let \(X=\min S\). The implementations compute
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
Term \(f(k)\) contributes to the error exactly when no sampled position appears among \(1,\dots,k\), which is equivalent to \(X\gt k\). Therefore
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
The upper limit is \(n-m\) because the smallest selected position can never exceed \(n-m+1\). Taking expectations and using linearity gives
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
This reduces the whole problem to finding one survival probability for each prefix length \(k\).
The condition \(X\gt k\) means that every sampled position lies in \(\{k+1,\dots,n\}\), a set of size \(n-k\). The number of admissible samples is therefore \(\binom{n-k}{m}\), while the total number of samples is \(\binom{n}{m}\). Hence
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
Substituting this into the expectation yields the exact closed form
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
No subset enumeration is needed; only combinatorial counting is.
Directly evaluating huge binomial coefficients would be wasteful. Define
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Then the first value is
$$q_1=\frac{n-m}{n},$$
and consecutive terms satisfy
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
so
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
This recurrence lets the expectation be accumulated in one forward pass, using only one running probability instead of enormous intermediate integers.
For Problem 756, the weight at index \(k\) is \(\varphi(k)\), the number of integers in \(\{1,\dots,k\}\) that are coprime to \(k\). Its standard multiplicative formula is
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
The implementations obtain all totient values up to \(n\) with a sieve. Start with \(\varphi(r)=r\) for every \(r\). Whenever a prime \(p\) is found, update each multiple of \(p\) by
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
After all primes have been processed, every needed weight \(\varphi(1),\dots,\varphi(n)\) is available, and the expectation becomes
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Here \(n-m=3\), so only \(k=1,2,3\) matter. The survival probabilities are
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
The relevant totients are
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
Therefore
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
This agrees with direct enumeration of the ten 2-element subsets of \(\{1,2,3,4,5\}\): four subsets start at 1 and contribute 0, three start at 2 and contribute 1, two start at 3 and contribute \(1+1=2\), and one starts at 4 and contributes \(1+1+2=4\). The average is \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\).
The C++, Python, and Java implementations all follow the same two-phase plan. First they build the totient table up to \(n\) using the prime-multiple sieve described above. That preprocessing is the dominant cost, but it is done only once.
Second, they evaluate the expectation with the recurrence for \(q_k\). The first probability is \((n-m)/n\), and each later probability is obtained from the previous one by multiplying by \((n-k-m)/(n-k)\). At each step the current probability is multiplied by the current totient value and added to the running total.
The implementations never enumerate subsets and never form the huge binomial coefficients explicitly. The C++ version also checks two reference values before the main run: a linear-weight case with exact value \(2525/1326\), and a totient-weight checkpoint at \(n=10{,}000\), \(m=100\) giving \(5842.849907\). The production computation then uses \(n=12{,}345{,}678\) and \(m=12{,}345\) and prints the result to six decimal places.
Computing all totients up to \(n\) by the sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. The expectation pass uses one additional forward scan of length \(n-m\), so it costs \(O(n-m)\) time and \(O(1)\) extra space beyond the totient table. Overall, the method runs in \(O(n\log\log n)\) time and \(O(n)\) memory.
Die implementierte Größe ist ein erwarteter Fehlerterm, der beim Approximieren einer gewichteten Summe durch gleichverteiltes Ziehen von \(m\) verschiedenen Positionen aus \(\{1,\dots,n\}\) ohne Zurücklegen entsteht. Bezeichnet \(X\) die kleinste gezogene Position und \(f\) die Gewichtsfunktion, dann ist der Fehler genau das Gesamtgewicht vor der ersten gezogenen Position:
$$\sum_{k=1}^{X-1} f(k).$$
Bei Problem 756 gilt \(f(k)=\varphi(k)\), also die Euler'sche Phi-Funktion, und die Hauptparameter sind \(n=12{,}345{,}678\) und \(m=12{,}345\). Gesucht ist somit der zugehörige Erwartungswert in effizient berechenbarer Form.
Sei \(S\subseteq\{1,\dots,n\}\) die gleichverteilte Auswahl der Größe \(m\), und sei \(X=\min S\). Die Implementierungen berechnen
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
Der Term \(f(k)\) trägt genau dann zum Fehler bei, wenn unter den Positionen \(1,\dots,k\) noch keine gezogene Position liegt. Das ist gleichbedeutend mit \(X\gt k\). Also gilt
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
Die obere Grenze ist \(n-m\), weil die kleinste ausgewählte Position niemals größer als \(n-m+1\) sein kann. Erwartungswertbildung und Linearität liefern damit
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
Das gesamte Problem ist damit auf eine Überlebenswahrscheinlichkeit pro Präfixlänge \(k\) reduziert.
Die Bedingung \(X\gt k\) bedeutet, dass alle gezogenen Positionen in \(\{k+1,\dots,n\}\) liegen, also in einer Menge der Größe \(n-k\). Die Anzahl zulässiger Auswahlen ist daher \(\binom{n-k}{m}\), die Gesamtzahl aller Auswahlen ist \(\binom{n}{m}\). Somit
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
Einsetzen in den Erwartungswert ergibt die exakte geschlossene Form
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Es ist also keine Enumeration aller Teilmengen nötig, sondern nur sauberes kombinatorisches Zählen.
Das direkte Auswerten riesiger Binomialkoeffizienten wäre unpraktisch. Definiere
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Dann ist der erste Wert
$$q_1=\frac{n-m}{n},$$
und für aufeinanderfolgende Werte gilt
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
also
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
Damit lässt sich der Erwartungswert in einem einzigen Vorwärtsdurchlauf akkumulieren, ohne jemals große Zwischenzahlen aufzubauen.
Für Problem 756 ist das Gewicht an Position \(k\) gleich \(\varphi(k)\), also der Anzahl der Zahlen in \(\{1,\dots,k\}\), die teilerfremd zu \(k\) sind. Die Standardformel lautet
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
Die Implementierungen erzeugen alle Totientwerte bis \(n\) mit einem Sieb. Zunächst setzt man \(\varphi(r)=r\) für alle \(r\). Immer wenn eine Primzahl \(p\) erkannt wird, aktualisiert man jedes Vielfache von \(p\) durch
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
Nach der Verarbeitung aller Primzahlen stehen sämtliche Gewichte \(\varphi(1),\dots,\varphi(n)\) zur Verfügung, und der Erwartungswert lautet
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Hier ist \(n-m=3\), also sind nur \(k=1,2,3\) relevant. Die Überlebenswahrscheinlichkeiten sind
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
Die benötigten Totienten sind
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
Daher
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
Das stimmt mit direkter Enumeration der zehn 2-elementigen Teilmengen von \(\{1,2,3,4,5\}\) überein: Vier Teilmengen beginnen bei 1 und tragen 0 bei, drei beginnen bei 2 und tragen 1 bei, zwei beginnen bei 3 und tragen \(1+1=2\) bei, und eine beginnt bei 4 und trägt \(1+1+2=4\) bei. Der Mittelwert ist also \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\).
Die C++-, Python- und Java-Implementierungen folgen demselben Zweiphasenplan. Zuerst wird mit dem oben beschriebenen Primzahl-Vielfachen-Sieb die Totienttabelle bis \(n\) aufgebaut. Diese Vorverarbeitung dominiert die Laufzeit, wird aber nur einmal ausgeführt.
Danach wird der Erwartungswert mit der Rekursion für \(q_k\) berechnet. Die erste Wahrscheinlichkeit ist \((n-m)/n\), jede weitere entsteht aus der vorherigen durch Multiplikation mit \((n-k-m)/(n-k)\). In jedem Schritt wird die aktuelle Wahrscheinlichkeit mit dem aktuellen Totientwert multipliziert und zum laufenden Ergebnis addiert.
Die Implementierungen enumerieren weder Teilmengen noch bilden sie die riesigen Binomialkoeffizienten explizit. Die C++-Version prüft vor dem Hauptlauf zusätzlich zwei Referenzwerte: einen linearen Gewichtungsfall mit exaktem Wert \(2525/1326\) sowie einen Totient-Kontrollwert bei \(n=10{,}000\) und \(m=100\) mit Ergebnis \(5842.849907\). Anschließend wird der Hauptlauf mit \(n=12{,}345{,}678\) und \(m=12{,}345\) ausgeführt und das Resultat auf sechs Nachkommastellen formatiert.
Das Sieb zur Berechnung aller Totienten bis \(n\) benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Der Erwartungswertteil ist ein weiterer Vorwärtsdurchlauf der Länge \(n-m\) und kostet deshalb \(O(n-m)\) Zeit bei nur \(O(1)\) zusätzlichem Speicher jenseits der Totienttabelle. Insgesamt ergibt sich also \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher.
Uygulanan nicelik, \(\{1,\dots,n\}\) kümesinden \(m\) farklı konumun yerine koymadan eş olasılıkla seçildiği bir örnekleme altında ortaya çıkan beklenen hata terimidir. \(X\) seçilen en küçük konum ve \(f\) ağırlık dizisi olmak üzere hata, ilk seçilen konumdan önce kalan toplam ağırlıktır:
$$\sum_{k=1}^{X-1} f(k).$$
Problem 756'da ağırlık fonksiyonu Euler totient fonksiyonudur; yani \(f(k)=\varphi(k)\). Asıl parametreler \(n=12{,}345{,}678\) ve \(m=12{,}345\) olduğundan, amaç bu beklentiyi doğru ve verimli biçimde hesaplamaktır.
\(S\subseteq\{1,\dots,n\}\) seçilen \(m\)-elemanlı kümeyi, \(X=\min S\) ise bu kümedeki en küçük elemanı göstersin. Uygulamalar şu niceliği hesaplar:
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
\(f(k)\) terimi ancak \(1,\dots,k\) aralığında hiç seçilmiş konum yoksa hataya katkı verir; bu da tam olarak \(X\gt k\) demektir. Dolayısıyla
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
Üst sınırın \(n-m\) olmasının sebebi, en küçük seçilmiş konumun \(n-m+1\)'den büyük olamamasıdır. Beklenti alıp doğrusalığı kullandığımızda
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k)$$
elde edilir. Böylece problem, her önek uzunluğu \(k\) için tek bir sağkalım olasılığını bulmaya indirgenir.
\(X\gt k\) koşulu, seçilen tüm konumların \(\{k+1,\dots,n\}\) içinde kalması demektir. Bu kümenin boyu \(n-k\) olduğundan uygun örnek sayısı \(\binom{n-k}{m}\), tüm örneklerin sayısı ise \(\binom{n}{m}\) olur. Bu yüzden
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
Bunu beklenti formülüne yerleştirince tam kapalı ifade
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}$$
çıkar. Yani alt kümeleri tek tek dolaşmak gerekmez; saf kombinatorik sayım yeterlidir.
Devasa binom katsayılarını doğrudan hesaplamak verimsiz olur. Şunu tanımlayalım:
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
İlk değer
$$q_1=\frac{n-m}{n}$$
olur; ardışık terimler için ise
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
dolayısıyla
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
Bu bağıntı sayesinde beklenti tek bir ileri taramada, yalnızca güncel olasılığı elde tutarak hesaplanır; büyük ara tamsayılara ihtiyaç kalmaz.
Problem 756'da \(k\) konumunun ağırlığı \(\varphi(k)\)'dir; bu, \(\{1,\dots,k\}\) içindeki \(k\) ile aralarında asal olan sayıların adedidir. Standart çarpımsal formül
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right)$$
şeklindedir. Uygulamalar tüm totient değerlerini \(n\)'ye kadar bir elek ile üretir. Başlangıçta her \(r\) için \(\varphi(r)=r\) alınır. Bir asal \(p\) bulunduğunda, \(p\)'nin her katı için
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}$$
güncellemesi yapılır. Tüm asallar işlendiğinde \(\varphi(1),\dots,\varphi(n)\) hazır olur ve beklenti
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}$$
biçimine gelir.
Burada \(n-m=3\) olduğundan yalnızca \(k=1,2,3\) önemlidir. Sağkalım olasılıkları
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}$$
olur. Gerekli totient değerleri ise
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
Dolayısıyla
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
Bu sonuç, \(\{1,2,3,4,5\}\) kümesinin 10 adet ikili alt kümesini doğrudan sayınca da çıkar: Dört alt kümenin en küçük elemanı 1'dir ve katkısı 0'dır; üç tanesi 2 ile başlar ve 1 katkı verir; iki tanesi 3 ile başlar ve \(1+1=2\) katkı verir; bir tanesi 4 ile başlar ve \(1+1+2=4\) katkı verir. Ortalama \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\) olur.
C++, Python ve Java uygulamalarının hepsi aynı iki aşamalı planı izler. Önce yukarıda anlatılan asal-katlar eleği ile \(n\)'ye kadar totient tablosu oluşturulur. Maliyet açısından baskın bölüm budur, fakat yalnızca bir kez yapılır.
Ardından beklenti, \(q_k\) bağıntısı kullanılarak hesaplanır. İlk olasılık \((n-m)/n\) olur; sonraki her olasılık, bir öncekinin \((n-k-m)/(n-k)\) ile çarpılmasıyla elde edilir. Her adımda güncel olasılık o sıradaki totient değeri ile çarpılır ve birikimli toplama eklenir.
Uygulamalar ne alt kümeleri tek tek üretir ne de dev binom katsayılarını açıkça kurar. C++ uygulaması, ana hesaptan önce iki kontrol değeri de doğrular: doğrusal ağırlıklı örnekte tam değer \(2525/1326\), totient ağırlıklı kontrol örneğinde ise \(n=10{,}000\), \(m=100\) için \(5842.849907\). Son olarak ana çalışma \(n=12{,}345{,}678\) ve \(m=12{,}345\) ile yapılır ve sonuç altı ondalık basamakla yazdırılır.
Elek ile \(n\)'ye kadar tüm totient değerlerini üretmek \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir. Beklenti hesabı ise uzunluğu \(n-m\) olan ek bir ileri geçiştir; bu yüzden süresi \(O(n-m)\), totient tablosu dışında ek alanı \(O(1)\)'dir. Toplamda yöntem \(O(n\log\log n)\) zamanda ve \(O(n)\) bellekte çalışır.
La cantidad implementada es un término de error esperado que aparece al aproximar una suma ponderada tomando \(m\) posiciones distintas de \(\{1,\dots,n\}\) de manera uniforme y sin reemplazo. Si \(X\) es la menor posición elegida y \(f\) es la secuencia de pesos, el error es exactamente el peso total situado antes de la primera posición elegida:
$$\sum_{k=1}^{X-1} f(k).$$
En el Problema 756 el peso es la función totiente de Euler, es decir \(f(k)=\varphi(k)\), y los parámetros principales son \(n=12{,}345{,}678\) y \(m=12{,}345\). Por tanto, la tarea consiste en evaluar esa esperanza de forma exacta en lo matemático y eficiente en la práctica.
Sea \(S\subseteq\{1,\dots,n\}\) el conjunto uniforme de tamaño \(m\), y sea \(X=\min S\). Las implementaciones calculan
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
El término \(f(k)\) contribuye al error exactamente cuando no aparece ninguna posición elegida entre \(1\) y \(k\), lo cual equivale a \(X\gt k\). Por ello,
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
El límite superior es \(n-m\) porque la menor posición seleccionada nunca puede exceder \(n-m+1\). Al tomar esperanza y usar linealidad se obtiene
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
Así, todo el problema se reduce a conocer una probabilidad de supervivencia para cada longitud de prefijo \(k\).
La condición \(X\gt k\) significa que todas las posiciones elegidas están en \(\{k+1,\dots,n\}\), un conjunto de tamaño \(n-k\). El número de muestras válidas es entonces \(\binom{n-k}{m}\), mientras que el número total de muestras es \(\binom{n}{m}\). Por tanto,
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
Sustituyendo en la esperanza aparece la forma cerrada exacta
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
No hace falta enumerar subconjuntos; basta con contar correctamente.
Evaluar coeficientes binomiales gigantes directamente sería innecesario. Definimos
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Entonces el primer valor es
$$q_1=\frac{n-m}{n},$$
y los términos consecutivos satisfacen
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
de modo que
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
Gracias a esta relación, la esperanza puede acumularse en una sola pasada, manteniendo solo la probabilidad actual.
En el Problema 756 el peso en la posición \(k\) es \(\varphi(k)\), el número de enteros en \(\{1,\dots,k\}\) que son coprimos con \(k\). Su fórmula multiplicativa estándar es
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
Las implementaciones calculan todos los valores del totiente hasta \(n\) con una criba. Se inicia con \(\varphi(r)=r\) para todo \(r\). Cada vez que se detecta un primo \(p\), se actualiza cada múltiplo de \(p\) mediante
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
Después de procesar todos los primos, ya están disponibles \(\varphi(1),\dots,\varphi(n)\), y la esperanza queda en
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Aquí \(n-m=3\), así que solo importan \(k=1,2,3\). Las probabilidades de supervivencia son
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
Los totientes relevantes son
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
Por lo tanto,
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
Esto coincide con la enumeración directa de los diez subconjuntos de tamaño 2 de \(\{1,2,3,4,5\}\): cuatro empiezan en 1 y aportan 0, tres empiezan en 2 y aportan 1, dos empiezan en 3 y aportan \(1+1=2\), y uno empieza en 4 y aporta \(1+1+2=4\). El promedio es \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan en dos fases. Primero construyen la tabla de totientes hasta \(n\) usando la criba de múltiplos primos descrita arriba. Ese preprocesamiento domina el tiempo total, pero solo se realiza una vez.
Después evalúan la esperanza con la recurrencia para \(q_k\). La primera probabilidad es \((n-m)/n\), y cada probabilidad posterior se obtiene multiplicando la anterior por \((n-k-m)/(n-k)\). En cada paso, la probabilidad actual se multiplica por el totiente correspondiente y se añade al acumulado.
Las implementaciones no enumeran subconjuntos ni construyen de forma explícita los enormes coeficientes binomiales. La versión en C++ además comprueba dos valores de referencia antes del cálculo principal: un caso con pesos lineales cuyo valor exacto es \(2525/1326\), y un punto de control con pesos totiente en \(n=10{,}000\), \(m=100\), que da \(5842.849907\). Luego el cálculo principal usa \(n=12{,}345{,}678\) y \(m=12{,}345\) y muestra el resultado con seis decimales.
Calcular todos los totientes hasta \(n\) mediante la criba cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. La fase de esperanza hace una pasada adicional de longitud \(n-m\), así que cuesta \(O(n-m)\) tiempo y solo \(O(1)\) espacio extra aparte de la tabla de totientes. En conjunto, el método trabaja en \(O(n\log\log n)\) tiempo y \(O(n)\) memoria.
这里实现的量，是一种“用无放回随机抽样去逼近加权和”时产生的期望误差。我们从 \(\{1,\dots,n\}\) 中等概率地选出 \(m\) 个互不相同的位置。设 \(X\) 为被选中的最小位置，\(f\) 为权重序列，那么误差就是第一处被选中位置之前所有权重的总和：
$$\sum_{k=1}^{X-1} f(k).$$
在 Problem 756 中，权重取 Euler totient 函数，也就是 \(f(k)=\varphi(k)\)。正式计算时使用的参数是 \(n=12{,}345{,}678\) 与 \(m=12{,}345\)。因此核心任务是把这个期望量化成一个既严格正确又能高效实现的公式。
记 \(S\subseteq\{1,\dots,n\}\) 为均匀选出的 \(m\) 元集合，令 \(X=\min S\)。三种实现实际上都在计算
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
某一项 \(f(k)\) 会进入误差，当且仅当在前缀 \(1,\dots,k\) 中还没有任何被抽中的位置。这与条件 \(X\gt k\) 完全等价。因此
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
上界之所以是 \(n-m\)，是因为最小被选位置不可能超过 \(n-m+1\)。对上式取期望，并利用期望的线性性，就得到
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
这样一来，原问题就被化成了：对每个前缀长度 \(k\)，求出“最早命中位置仍在其后面”的概率。
条件 \(X\gt k\) 表示所有被选中的位置都落在 \(\{k+1,\dots,n\}\) 中，这个集合的大小是 \(n-k\)。所以满足条件的样本数为 \(\binom{n-k}{m}\)，而全部样本数为 \(\binom{n}{m}\)。于是
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
代回期望表达式以后，便得到精确的闭式
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
这一步说明我们根本不需要枚举所有子集；只要正确地做组合计数即可。
直接计算巨大的二项式系数既慢又没有必要。定义
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
那么第一个值是
$$q_1=\frac{n-m}{n},$$
而相邻两项满足
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
也就是
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
这样就可以只维护一个滚动概率，按顺序累加整个期望值，而无需构造任何巨大的中间整数。
在 Problem 756 中，第 \(k\) 项的权重是 \(\varphi(k)\)，即区间 \(\{1,\dots,k\}\) 内与 \(k\) 互素的整数个数。它的标准乘法公式为
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
实现里通过筛法一次性求出所有 \(\varphi(1),\dots,\varphi(n)\)。做法是先令每个 \(r\) 的初值为 \(\varphi(r)=r\)。当发现一个质数 \(p\) 时，就对它的每个倍数执行
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
所有质数处理完毕后，就得到了所需的全部权重，于是期望写成
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
此时 \(n-m=3\)，因此只有 \(k=1,2,3\) 会出现。对应的生存概率为
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
而相关的 totient 值是
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
因此
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
这个结果也能直接用枚举验证。集合 \(\{1,2,3,4,5\}\) 的 10 个二元子集里，有 4 个最小元素是 1，对应误差为 0；有 3 个最小元素是 2，对应误差为 1；有 2 个最小元素是 3，对应误差为 \(1+1=2\)；还有 1 个最小元素是 4，对应误差为 \(1+1+2=4\)。平均值正好是 \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\)。
C++、Python 和 Java 实现都遵循相同的两阶段结构。第一阶段先用上面的质数倍数筛法建立从 1 到 \(n\) 的 totient 表。这一步是主要的时间开销，但只需要做一次。
第二阶段再用 \(q_k\) 的递推式计算期望。起始概率是 \((n-m)/n\)，后续每一项都通过把前一项乘上 \((n-k-m)/(n-k)\) 得到。每走一步，就把当前概率与当前的 totient 权重相乘并累加到总和里。
整个实现既不枚举样本子集，也不显式构造巨大二项式系数。C++ 版本在正式计算前还会验证两个参考值：一个是线性权重情形，其精确值为 \(2525/1326\)；另一个是 totient 权重的检查点，在 \(n=10{,}000\)、\(m=100\) 时得到 \(5842.849907\)。随后主计算使用 \(n=12{,}345{,}678\) 和 \(m=12{,}345\)，并把结果格式化为 6 位小数。
用筛法计算 \(1\) 到 \(n\) 的全部 totient 值需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。随后求期望的部分只做一次长度为 \(n-m\) 的线性扫描，所以是 \(O(n-m)\) 时间，并且除了 totient 表之外只需 \(O(1)\) 额外空间。总体复杂度因此为 \(O(n\log\log n)\) 时间与 \(O(n)\) 空间。
Вычисляемая величина представляет собой математическое ожидание ошибки, возникающей при приближении взвешенной суммы с помощью равномерной выборки без возвращения. Из множества \(\{1,\dots,n\}\) выбираются \(m\) различных позиций. Если \(X\) обозначает наименьшую выбранную позицию, а \(f\) — весовую функцию, то ошибка равна сумме весов строго до первого выбранного места:
$$\sum_{k=1}^{X-1} f(k).$$
В задаче 756 в качестве веса берется функция Эйлера, то есть \(f(k)=\varphi(k)\), а основные параметры равны \(n=12{,}345{,}678\) и \(m=12{,}345\). Поэтому цель состоит в том, чтобы получить для этого ожидания точную формулу и реализовать ее эффективно.
Пусть \(S\subseteq\{1,\dots,n\}\) — равномерно выбранное множество размера \(m\), и пусть \(X=\min S\). Реализации вычисляют величину
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
Слагаемое \(f(k)\) входит в ошибку тогда и только тогда, когда среди позиций \(1,\dots,k\) еще нет ни одной выбранной. Это эквивалентно условию \(X\gt k\). Следовательно,
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
Верхний предел равен \(n-m\), потому что минимальная выбранная позиция не может быть больше \(n-m+1\). Берем ожидание и используем линейность:
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
Тем самым вся задача сводится к вычислению одной вероятности выживания для каждого префикса длины \(k\).
Условие \(X\gt k\) означает, что все выбранные позиции лежат в \(\{k+1,\dots,n\}\), а это множество размера \(n-k\). Значит, число подходящих выборок равно \(\binom{n-k}{m}\), а общее число выборок равно \(\binom{n}{m}\). Поэтому
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
Подставляя это в формулу ожидания, получаем точное замкнутое выражение
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Никакого перебора подмножеств не требуется; достаточно аккуратного комбинаторного счета.
Напрямую считать огромные биномиальные коэффициенты неразумно. Введем обозначение
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Тогда первое значение равно
$$q_1=\frac{n-m}{n},$$
а для соседних членов выполняется
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
то есть
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
Благодаря этому ожидание накапливается за один проход вперед, и хранить гигантские промежуточные целые числа не нужно.
В задаче 756 вес в позиции \(k\) равен \(\varphi(k)\), то есть числу целых из \(\{1,\dots,k\}\), взаимно простых с \(k\). Стандартная мультипликативная формула имеет вид
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
Реализации получают все значения totient до \(n\) при помощи решета. Сначала для каждого \(r\) ставится \(\varphi(r)=r\). Каждый раз, когда обнаруживается простое число \(p\), для всех его кратных выполняется обновление
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
После обработки всех простых чисел значения \(\varphi(1),\dots,\varphi(n)\) готовы, и искомое ожидание принимает вид
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
Здесь \(n-m=3\), поэтому важны только \(k=1,2,3\). Вероятности выживания равны
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
Нужные значения функции Эйлера:
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
Следовательно,
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
Это совпадает с прямым перебором десяти двухэлементных подмножеств множества \(\{1,2,3,4,5\}\): четыре из них начинаются с 1 и дают вклад 0, три начинаются с 2 и дают вклад 1, два начинаются с 3 и дают вклад \(1+1=2\), одно начинается с 4 и дает вклад \(1+1+2=4\). Среднее равно \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\).
Реализации на C++, Python и Java используют один и тот же двухэтапный план. Сначала строится таблица значений функции Эйлера до \(n\) с помощью решета по простым и их кратным. Именно этот этап дает основную стоимость по времени, но выполняется только один раз.
Затем вычисляется само ожидание через рекурсию для \(q_k\). Первая вероятность равна \((n-m)/n\), а каждая следующая получается из предыдущей умножением на \((n-k-m)/(n-k)\). На каждом шаге текущая вероятность умножается на текущее значение функции Эйлера и добавляется к накопленной сумме.
Реализации не перебирают подмножества и не строят огромные биномиальные коэффициенты явно. Версия на C++ дополнительно проверяет два эталонных значения перед основным запуском: случай с линейными весами, где точный ответ равен \(2525/1326\), и контрольную точку с totient-весами при \(n=10{,}000\), \(m=100\), где получается \(5842.849907\). После этого основной расчет выполняется для \(n=12{,}345{,}678\) и \(m=12{,}345\), а результат печатается с шестью знаками после запятой.
Вычисление всех значений функции Эйлера до \(n\) с помощью решета требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Фаза ожидания — это еще один линейный проход длины \(n-m\), то есть \(O(n-m)\) времени и всего \(O(1)\) дополнительной памяти сверх таблицы totient. В итоге весь метод работает за \(O(n\log\log n)\) времени и использует \(O(n)\) памяти.
الكمية المحسوبة هنا هي قيمة متوقعة لخطأ ينشأ عند تقريب مجموع موزون بواسطة اختيار \(m\) مواضع مختلفة من \(\{1,\dots,n\}\) اختيارًا منتظمًا بدون إرجاع. إذا كان \(X\) أصغر موضع مختار، وكانت \(f\) دالة الأوزان، فإن الخطأ يساوي مجموع الأوزان الواقعة قبل أول موضع مختار:
$$\sum_{k=1}^{X-1} f(k).$$
في المسألة 756 تكون الأوزان هي دالة أويلر التوتينت، أي \(f(k)=\varphi(k)\)، وتكون القيم الأساسية \(n=12{,}345{,}678\) و\(m=12{,}345\). لذلك فالهدف هو حساب هذا التوقع بدقة رياضية وبطريقة عملية سريعة.
لنكتب \(S\subseteq\{1,\dots,n\}\) للمجموعة المختارة عشوائيًا ذات الحجم \(m\)، ولتكن \(X=\min S\). ما تحسبه التطبيقات هو
$$E_{n,m}(f)=\mathbb{E}\left[\sum_{k=1}^{X-1} f(k)\right].$$
الحد \(f(k)\) يساهم في الخطأ إذا وفقط إذا لم يظهر أي موضع مختار داخل المقطع \(1,\dots,k\)، وهذا يكافئ الشرط \(X\gt k\). لذلك
$$\sum_{k=1}^{X-1} f(k)=\sum_{k=1}^{n-m} f(k)\,\mathbf{1}_{\{X\gt k\}}.$$
والحد الأعلى هو \(n-m\) لأن أصغر موضع مختار لا يمكن أن يتجاوز \(n-m+1\). وعند أخذ التوقع واستخدام خطية التوقع نحصل على
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\,\Pr(X\gt k).$$
وبذلك تُختزل المسألة كلها إلى حساب احتمال بقاء واحد لكل طول بادئة \(k\).
الشرط \(X\gt k\) يعني أن جميع المواضع المختارة تقع داخل \(\{k+1,\dots,n\}\)، وهي مجموعة حجمها \(n-k\). إذن عدد الاختيارات المسموح بها هو \(\binom{n-k}{m}\)، بينما العدد الكلي للاختيارات هو \(\binom{n}{m}\). ومن ثم
$$\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}} \qquad (1\le k\le n-m).$$
وبالتعويض في صيغة التوقع نحصل على الصيغة المغلقة الدقيقة
$$E_{n,m}(f)=\sum_{k=1}^{n-m} f(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
لا حاجة إلى تعداد جميع المجموعات الجزئية؛ العد التوافقي وحده يكفي.
الحساب المباشر لمعاملات ثنائية ضخمة غير عملي. نعرّف
$$q_k=\Pr(X\gt k)=\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
عندئذ تكون القيمة الأولى
$$q_1=\frac{n-m}{n},$$
وتحقق الحدود المتتالية
$$\frac{q_{k+1}}{q_k}=\frac{\binom{n-k-1}{m}}{\binom{n-k}{m}}=\frac{n-k-m}{n-k},$$
أي
$$q_{k+1}=q_k\frac{n-k-m}{n-k}\qquad (1\le k\le n-m-1).$$
هذه العلاقة تسمح بتجميع التوقع في مرور واحد فقط، مع الاحتفاظ باحتمال جارٍ واحد بدلًا من بناء أعداد ضخمة وسيطة.
في المسألة 756 يكون الوزن عند الموضع \(k\) هو \(\varphi(k)\)، أي عدد الأعداد في \(\{1,\dots,k\}\) التي تكون أولية نسبيًا مع \(k\). وصيغتها الضربية القياسية هي
$$\varphi(r)=r\prod_{p\mid r}\left(1-\frac{1}{p}\right).$$
تحسب التطبيقات جميع قيم التوتينت حتى \(n\) بواسطة غربال. نبدأ بوضع \(\varphi(r)=r\) لكل \(r\). وكلما ظهر عدد أولي \(p\)، نحدّث كل مضاعف له وفق
$$\varphi(r)\leftarrow \varphi(r)-\frac{\varphi(r)}{p}.$$
بعد معالجة جميع الأعداد الأولية تصبح القيم \(\varphi(1),\dots,\varphi(n)\) جاهزة، ويأخذ التوقع الشكل
$$E_{n,m}(\varphi)=\sum_{k=1}^{n-m} \varphi(k)\frac{\binom{n-k}{m}}{\binom{n}{m}}.$$
هنا لدينا \(n-m=3\)، ولذلك لا تظهر إلا القيم \(k=1,2,3\). احتمالات البقاء هي
$$q_1=\frac{\binom{4}{2}}{\binom{5}{2}}=\frac{3}{5},\qquad q_2=\frac{\binom{3}{2}}{\binom{5}{2}}=\frac{3}{10},\qquad q_3=\frac{\binom{2}{2}}{\binom{5}{2}}=\frac{1}{10}.$$
وقيم التوتينت اللازمة هي
$$\varphi(1)=1,\qquad \varphi(2)=1,\qquad \varphi(3)=2.$$
إذن
$$E_{5,2}(\varphi)=1\cdot\frac{3}{5}+1\cdot\frac{3}{10}+2\cdot\frac{1}{10}=\frac{11}{10}.$$
وهذا يطابق العد المباشر للمجموعات الثنائية العشر داخل \(\{1,2,3,4,5\}\): أربع مجموعات تبدأ بـ 1 وتعطي خطأ يساوي 0، وثلاث تبدأ بـ 2 وتعطي 1، واثنتان تبدأان بـ 3 وتعطيان \(1+1=2\)، وواحدة تبدأ بـ 4 وتعطي \(1+1+2=4\). ولذلك يكون المتوسط \((0\cdot4+1\cdot3+2\cdot2+4\cdot1)/10=11/10\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها ذات المرحلتين. في المرحلة الأولى تُبنى جدول قيم التوتينت حتى \(n\) باستخدام غربال الأعداد الأولية ومضاعفاتها كما في الاشتقاق السابق. وهذه هي المرحلة المسيطرة على الزمن، لكنها تُنفذ مرة واحدة فقط.
في المرحلة الثانية يُحسب التوقع بواسطة علاقة \(q_k\) التكرارية. الاحتمال الأول هو \((n-m)/n\)، وكل احتمال تالٍ ينتج من السابق بضربه في \((n-k-m)/(n-k)\). وفي كل خطوة يُضرب الاحتمال الحالي في قيمة التوتينت الحالية ثم يُضاف إلى المجموع التراكمي.
لا تقوم التطبيقات بتعداد المجموعات الجزئية، ولا تُنشئ معاملات ثنائية هائلة بشكل صريح. كما أن تنفيذ C++ يتحقق قبل التشغيل الرئيسي من قيمتين مرجعيتين: حالة أوزان خطية ذات قيمة دقيقة \(2525/1326\)، ونقطة تحقق موزونة بالتوتينت عند \(n=10{,}000\) و\(m=100\) تعطي \(5842.849907\). بعد ذلك يُنفذ الحساب الرئيسي عند \(n=12{,}345{,}678\) و\(m=12{,}345\)، ويُطبع الناتج بست منازل عشرية.
حساب جميع قيم التوتينت حتى \(n\) بواسطة الغربال يحتاج إلى زمن \(O(n\log\log n)\) وذاكرة \(O(n)\). أما مرحلة التوقع فهي مرور خطي إضافي بطول \(n-m\)، وبالتالي تكلف \(O(n-m)\) زمنًا و\(O(1)\) مساحة إضافية فوق جدول التوتينت. إذن التعقيد الكلي هو \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرةً.