For each integer \(n\) with \(1 \le n \le 100\), and each \(r\) with \(0 \le r \le n\), consider the binomial coefficient \(\binom{n}{r}\). The task is to count how many pairs \((n,r)\) satisfy \(\binom{n}{r} \gt 10^6\).
The key point is that we do not need to evaluate every coefficient with factorials. The implementations sweep through each row from left to right, stop as soon as the row crosses one million, and count the rest of that row from symmetry.
Let \(T=10^6\). The useful structure comes from comparing consecutive binomial coefficients in the same row.
The definition $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$ is mathematically correct, but it is not the most convenient way to compute many values in one row. If we divide consecutive coefficients, we get $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ so $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ Starting from \(\binom{n}{0}=1\), this recurrence generates the row one entry at a time.
This is exactly the invariant used in the code: after the update for a given \(r\), the running value is the exact integer \(\binom{n}{r}\). No Pascal triangle table and no factorial array are required.
Two standard facts control the whole row: $$\binom{n}{r}=\binom{n}{n-r}$$ and $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ For every \(1 \le r \le \lfloor n/2 \rfloor\), that ratio is greater than 1, so the coefficients strictly increase as we move from the left edge toward the middle. After the midpoint, symmetry forces the same values to reappear in reverse order.
Therefore the first coefficient above the threshold in the left half completely determines every coefficient above the threshold in that row.
Suppose \(r_0\) is the smallest index such that $$\binom{n}{r_0} \gt T.$$ By monotonicity up to the midpoint and symmetry afterward, every index $$r_0 \le r \le n-r_0$$ also satisfies \(\binom{n}{r} \gt T\). The number of such indices is $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ This is the row contribution added by the implementations as soon as the first crossing is found.
If the scan reaches \(\lfloor n/2 \rfloor\) without exceeding \(T\), then the entire row stays at or below the threshold and contributes 0.
For \(n=23\), the recurrence produces $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ The first value above one million appears at \(r_0=10\). Symmetry then gives the matching values at \(r=11,12,13\), so the exceeding block is $$r=10,11,12,13.$$ Its size is $$23+1-2\cdot 10=4.$$ This is the same reasoning used for every row from 1 through 100.
The C++, Python, and Java implementations all work with two mathematical parameters: an upper row bound \(n_{\max}\) and a threshold \(T\). For the Project Euler problem they default to \(n_{\max}=100\) and \(T=10^6\). Each implementation also contains a small checkpoint: when \(n_{\max}=10\) and \(T=10\), the correct count is 25.
For a fixed \(n\), the implementation starts with the coefficient \(1\) at \(r=0\). It then advances through $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor,$$ updating the running coefficient by $$c \leftarrow c\frac{n-r+1}{r}.$$ Because the update always lands on the exact next binomial coefficient, the loop never needs floating-point arithmetic or a precomputed table.
As soon as the running value exceeds the threshold, the implementation adds $$n+1-2r$$ to the total and immediately stops processing that row. This is correct because the first crossing identifies the entire central block above the threshold. For Problem 53, this also keeps the intermediate values modest: the computation breaks right after the first value above one million, so ordinary integer arithmetic is sufficient in all three languages.
With upper bound \(N\), the loop performs at most $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ coefficient updates. For \(N=100\), that worst-case total is only 2500 updates, and the real total is smaller because many rows stop before the midpoint.
The memory usage is \(O(1)\): the implementation stores only the current coefficient, the running answer, and a few counters and parameters. That matches the lightweight structure of the actual solution.
Für jedes ganze \(n\) mit \(1 \le n \le 100\) und jedes \(r\) mit \(0 \le r \le n\) betrachten wir den Binomialkoeffizienten \(\binom{n}{r}\). Gesucht ist die Anzahl der Paare \((n,r)\), für die \(\binom{n}{r} \gt 10^6\) gilt.
Der entscheidende Punkt ist, dass man nicht jeden Wert mit Fakultäten ausrechnen muss. Die Implementierungen laufen jede Zeile von links nach rechts ab, stoppen beim ersten Überschreiten von einer Million und zählen den Rest der Zeile dann über die Symmetrie.
Setze \(T=10^6\). Die nützliche Struktur entsteht aus dem Verhältnis aufeinanderfolgender Binomialkoeffizienten innerhalb derselben Zeile.
Die Definition $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$ ist mathematisch korrekt, aber nicht die praktischste Form für viele Werte derselben Zeile. Teilt man zwei benachbarte Koeffizienten, erhält man $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ also $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ Ausgehend von \(\binom{n}{0}=1\) lässt sich die gesamte linke Zeilenhälfte damit Schritt für Schritt aufbauen.
Genau das ist die Invariante im Code: Nach dem Update für ein bestimmtes \(r\) ist der laufende Wert exakt \(\binom{n}{r}\). Weder ein komplettes Pascalsches Dreieck noch ein Fakultätsarray werden benötigt.
Zwei bekannte Tatsachen kontrollieren die ganze Zeile: $$\binom{n}{r}=\binom{n}{n-r}$$ und $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ Für jedes \(1 \le r \le \lfloor n/2 \rfloor\) ist dieses Verhältnis größer als 1, also steigen die Koeffizienten streng an, solange wir uns vom linken Rand zur Mitte bewegen. Nach dem Mittelpunkt erscheinen dieselben Werte wegen der Symmetrie in umgekehrter Reihenfolge.
Deshalb bestimmt der erste Wert über dem Schwellwert in der linken Hälfte sofort alle weiteren Werte derselben Zeile, die ebenfalls über dem Schwellwert liegen.
Sei \(r_0\) der kleinste Index mit $$\binom{n}{r_0} \gt T.$$ Wegen der Monotonie bis zur Mitte und der Symmetrie danach gilt dann auch $$\binom{n}{r} \gt T \quad \text{für alle } r_0 \le r \le n-r_0.$$ Die Anzahl dieser Indizes ist $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ Genau dieser Ausdruck wird von den Implementierungen addiert, sobald das erste Überschreiten gefunden wurde.
Falls die Suche bis \(\lfloor n/2 \rfloor\) reicht, ohne \(T\) zu übertreffen, trägt die gesamte Zeile 0 bei.
Für \(n=23\) liefert die Rekurrenz $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ Der erste Wert über einer Million erscheint also bei \(r_0=10\). Durch Symmetrie kommen die Spiegelwerte bei \(r=11,12,13\) dazu, also ist der Block der gültigen Indizes $$r=10,11,12,13.$$ Seine Größe ist $$23+1-2\cdot 10=4.$$ Genau so wird jede Zeile von 1 bis 100 behandelt.
Die C++-, Python- und Java-Implementierungen arbeiten mit zwei mathematischen Parametern: einer oberen Zeilengrenze \(n_{\max}\) und einem Schwellwert \(T\). Für die Project-Euler-Aufgabe sind die Standardwerte \(n_{\max}=100\) und \(T=10^6\). Zusätzlich enthält jede Implementierung einen kleinen Testfall: Für \(n_{\max}=10\) und \(T=10\) muss das Ergebnis 25 sein.
Für festes \(n\) startet die Implementierung bei \(r=0\) mit dem Koeffizienten \(1\). Danach läuft sie durch $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ und aktualisiert den laufenden Koeffizienten mit $$c \leftarrow c\frac{n-r+1}{r}.$$ Weil dieses Update immer exakt den nächsten Binomialkoeffizienten liefert, braucht die Schleife weder Gleitkommaarithmetik noch eine vorgerechnete Tabelle.
Sobald der laufende Wert den Schwellwert überschreitet, addiert die Implementierung $$n+1-2r$$ zur Gesamtsumme und beendet die Bearbeitung dieser Zeile sofort. Das ist korrekt, weil das erste Überschreiten den gesamten mittleren Block oberhalb des Schwellwerts festlegt. Für Problem 53 hält diese Strategie auch die Zwischenwerte klein: Direkt nach dem ersten Wert über einer Million wird abgebrochen, sodass gewöhnliche Ganzzahlarithmetik in allen drei Sprachen ausreicht.
Bei einer Obergrenze \(N\) werden höchstens $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ Koeffizientenaktualisierungen durchgeführt. Für \(N=100\) sind das im schlimmsten Fall nur 2500 Updates, und tatsächlich noch weniger, weil viele Zeilen vor der Mitte enden.
Der Speicherverbrauch ist \(O(1)\): Gespeichert werden nur der aktuelle Koeffizient, die laufende Antwort sowie einige Zähler und Parameter. Das entspricht der schlanken Struktur der tatsächlichen Lösung.
\(1 \le n \le 100\) ve \(0 \le r \le n\) için \(\binom{n}{r}\) binom katsayılarını ele alıyoruz. Amaç, \(\binom{n}{r} \gt 10^6\) koşulunu sağlayan \((n,r)\) çiftlerinin sayısını bulmaktır.
Asıl fikir, her değeri faktöriyel üzerinden ayrı ayrı hesaplamamaktır. Uygulamalar her satırı soldan sağa tarar, bir milyon eşiği ilk kez aşıldığında durur ve satırın geri kalan katkısını simetriden çıkarır.
\(T=10^6\) olsun. İşe yarayan yapı, aynı satırdaki ardışık binom katsayıları arasındaki orandır.
Tanım olarak $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$ yazılır; fakat aynı satırdaki birçok değeri hesaplamak için daha verimli ifade $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}$$ oranıdır. Buradan $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}$$ elde edilir. Başlangıç değeri \(\binom{n}{0}=1\) olduğundan, satır soldan sağa tek bir değişkenle üretilebilir.
Koddaki temel değişmez de budur: belirli bir \(r\) adımından sonra eldeki yürüyen değer tam olarak \(\binom{n}{r}\) olur. Böylece ne tam bir Pascal üçgeni ne de faktöriyel dizisi gerekir.
Bütün satırı belirleyen iki gerçek vardır: $$\binom{n}{r}=\binom{n}{n-r}$$ ve $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ \(1 \le r \le \lfloor n/2 \rfloor\) için bu oran 1'den büyüktür; yani katsayılar sol uçtan merkeze kadar sıkı biçimde artar. Orta noktadan sonra ise aynı değerler simetri nedeniyle ters sırayla tekrar eder.
Bu yüzden sol yarıda eşiği aşan ilk terimi bulmak, o satırdaki bütün büyük terimlerin yerini tek seferde belirler.
\(r_0\), şu koşulu sağlayan en küçük indis olsun: $$\binom{n}{r_0} \gt T.$$ Merkeze kadar artış ve sonrasındaki simetri nedeniyle $$r_0 \le r \le n-r_0$$ aralığındaki bütün indisler için de \(\binom{n}{r} \gt T\) olur. Bu indislerin sayısı $$ (n-r_0)-r_0+1 = n+1-2r_0$$ değeridir. Uygulamalar, ilk aşımı görür görmez tam olarak bu miktarı toplama ekler.
Eğer tarama \(\lfloor n/2 \rfloor\) noktasına kadar gidip de eşiği aşmazsa, o satırın katkısı 0'dır.
\(n=23\) için yineleme şu değerleri verir: $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ Bir milyonu aşan ilk değer \(r_0=10\) konumunda gelir. Simetri yüzünden eşleşen değerler \(r=11,12,13\) konumlarındadır; dolayısıyla eşiği aşan blok $$r=10,11,12,13$$ olur. Blok uzunluğu da $$23+1-2\cdot 10=4$$ eder. 1 ile 100 arasındaki tüm satırlarda yapılan mantık tam olarak budur.
C++, Python ve Java uygulamalarının hepsi iki matematiksel parametre kullanır: üst satır sınırı \(n_{\max}\) ve eşik \(T\). Project Euler görevi için varsayılan değerler \(n_{\max}=100\) ve \(T=10^6\) olur. Ayrıca her uygulamada küçük bir doğrulama testi vardır: \(n_{\max}=10\) ve \(T=10\) için doğru sonuç 25'tir.
Sabit bir \(n\) için uygulama, \(r=0\) noktasında katsayıyı \(1\) alarak başlar. Sonra $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ boyunca ilerler ve yürüyen katsayıyı $$c \leftarrow c\frac{n-r+1}{r}$$ güncellemesiyle hesaplar. Bu güncelleme her adımda tam olarak bir sonraki binom katsayısını verdiği için kayan noktalı aritmetiğe ya da önceden kurulmuş tabloya ihtiyaç yoktur.
Yürüyen değer eşiği aşar aşmaz uygulama $$n+1-2r$$ miktarını toplama ekler ve o satırı anında bitirir. Bunun doğru olmasının sebebi, ilk aşımın orta bölgedeki tüm büyük terimleri zaten belirlemesidir. Problem 53 için bu yaklaşım ara değerleri de küçük tutar: bir milyonun üstündeki ilk değer görülür görülmez döngü bittiği için üç dilde de sıradan tam sayı aritmetiği yeterlidir.
Üst sınır \(N\) ise en fazla $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ adet katsayı güncellemesi yapılır. \(N=100\) için bu en kötü durumda yalnızca 2500 güncellemedir; pratikte ise birçok satır orta noktaya gelmeden durduğu için sayı daha da küçüktür.
Bellek kullanımı \(O(1)\)'dir. Uygulama yalnızca güncel katsayıyı, biriken cevabı ve birkaç sayaç ile parametreyi tutar. Bu da gerçek çözümün sade yapısıyla tam uyumludur.
Para cada entero \(n\) con \(1 \le n \le 100\), y para cada \(r\) con \(0 \le r \le n\), consideramos el coeficiente binomial \(\binom{n}{r}\). El objetivo es contar cuántos pares \((n,r)\) cumplen \(\binom{n}{r} \gt 10^6\).
La idea decisiva es que no hace falta calcular todos los valores con factoriales. Las implementaciones recorren cada fila de izquierda a derecha, se detienen en cuanto la fila supera un millón y cuentan el resto de la fila usando la simetría.
Sea \(T=10^6\). La estructura útil aparece al comparar coeficientes binomiales consecutivos dentro de una misma fila.
La definición $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$ es correcta, pero no es la forma más cómoda de producir muchos valores en la misma fila. Si dividimos dos coeficientes consecutivos, obtenemos $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ y por tanto $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ Empezando desde \(\binom{n}{0}=1\), esta recurrencia genera la fila de izquierda a derecha.
Esa es exactamente la invariante utilizada por el código: después de actualizar para un valor de \(r\), el acumulador contiene el entero exacto \(\binom{n}{r}\). No hace falta construir el triángulo de Pascal completo ni almacenar factoriales.
Dos hechos clásicos controlan toda la fila: $$\binom{n}{r}=\binom{n}{n-r}$$ y $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ Para todo \(1 \le r \le \lfloor n/2 \rfloor\), ese cociente es mayor que 1, así que los coeficientes crecen estrictamente desde el borde izquierdo hasta el centro. Después del punto medio, la simetría obliga a repetir los mismos valores en orden inverso.
Por eso, el primer coeficiente que supera el umbral en la mitad izquierda determina de inmediato todos los coeficientes de esa fila que también superan el umbral.
Sea \(r_0\) el menor índice tal que $$\binom{n}{r_0} \gt T.$$ Por la monotonía hasta el centro y la simetría después, también se cumple $$\binom{n}{r} \gt T \quad \text{para todo } r_0 \le r \le n-r_0.$$ El número de índices de ese bloque es $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ Esa es exactamente la cantidad que las implementaciones añaden cuando detectan el primer cruce.
Si la exploración llega hasta \(\lfloor n/2 \rfloor\) sin superar \(T\), entonces toda la fila permanece en o por debajo del umbral y aporta 0.
Para \(n=23\), la recurrencia produce $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ El primer valor por encima de un millón aparece en \(r_0=10\). La simetría añade sus reflejos en \(r=11,12,13\), de modo que el bloque que excede el umbral es $$r=10,11,12,13.$$ Su tamaño es $$23+1-2\cdot 10=4.$$ Ese mismo razonamiento se aplica a cada fila entre 1 y 100.
Las implementaciones en C++, Python y Java trabajan con dos parámetros matemáticos: una cota superior \(n_{\max}\) y un umbral \(T\). Para el problema de Project Euler usan por defecto \(n_{\max}=100\) y \(T=10^6\). Además, todas incluyen una comprobación pequeña: cuando \(n_{\max}=10\) y \(T=10\), la respuesta correcta es 25.
Para un \(n\) fijo, la implementación comienza con el coeficiente \(1\) en \(r=0\). Después avanza por $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ y actualiza el valor acumulado mediante $$c \leftarrow c\frac{n-r+1}{r}.$$ Como esa operación produce siempre el siguiente coeficiente binomial exacto, no se necesitan números en coma flotante ni una tabla precomputada.
En cuanto el valor acumulado supera el umbral, la implementación añade $$n+1-2r$$ al total y termina inmediatamente esa fila. Esto es correcto porque el primer cruce identifica todo el bloque central que está por encima del umbral. Para el Problema 53, además, los valores intermedios siguen siendo pequeños: el bucle se corta justo después del primer valor mayor que un millón, así que la aritmética entera ordinaria basta en los tres lenguajes.
Con límite superior \(N\), el algoritmo realiza como máximo $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ actualizaciones de coeficientes. Para \(N=100\), ese máximo es solo 2500, y en la práctica es menor porque muchas filas se detienen antes de alcanzar el centro.
El uso de memoria es \(O(1)\): la implementación solo guarda el coeficiente actual, la respuesta acumulada y unos pocos contadores y parámetros. Eso refleja la estructura compacta de la solución real.
对每个满足 \(1 \le n \le 100\) 的整数 \(n\)，以及每个满足 \(0 \le r \le n\) 的整数 \(r\)，考虑二项式系数 \(\binom{n}{r}\)。题目要求统计满足 \(\binom{n}{r} \gt 10^6\) 的所有 \((n,r)\) 对。
真正重要的地方在于，不必用阶乘把每个系数都单独算出来。实现采用的是逐行扫描：从每一行的左端开始向中间推进，一旦第一次超过一百万，就利用对称性直接算出这一整行剩余的贡献。
记阈值为 \(T=10^6\)。这个问题最有用的结构，是同一行中相邻二项式系数之间的关系。
二项式系数的定义是 $$\binom{n}{r}=\frac{n!}{r!(n-r)!}.$$ 但如果要在固定的 \(n\) 下连续计算很多个 \(r\)，更方便的是比较相邻两项： $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ 因而 $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ 从 \(\binom{n}{0}=1\) 出发，就能把这一行从左到右逐项生成出来。
代码依赖的核心不变量正是这一点：处理到某个 \(r\) 时，手里的当前值始终精确等于 \(\binom{n}{r}\)。因此既不需要完整存储帕斯卡三角形，也不需要预先准备阶乘数组。
整行的结构由两个事实决定： $$\binom{n}{r}=\binom{n}{n-r}$$ 以及 $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ 对所有 \(1 \le r \le \lfloor n/2 \rfloor\)，这个比值都大于 1，所以系数从左边界走向中点时会严格递增。过了中点以后，由于对称性，相同的数值会按相反顺序重新出现。
因此，只要在左半边找到第一个超过阈值的位置，就已经知道这一行中所有超过阈值的项落在什么区间里。
设 \(r_0\) 是满足 $$\binom{n}{r_0} \gt T$$ 的最小下标。由于到中点之前单调递增，而过中点之后又完全对称，所以所有 $$r_0 \le r \le n-r_0$$ 都会满足 \(\binom{n}{r} \gt T\)。这个区间中的整数个数是 $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ 这正是实现里在发现第一次越界后加入总答案的数量。
如果扫描一直走到 \(\lfloor n/2 \rfloor\) 仍然没有超过 \(T\)，那么这一整行都不贡献任何计数。
当 \(n=23\) 时，递推依次得到 $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ 第一个超过一百万的值出现在 \(r_0=10\)。由对称性可知，与它对应的右半边位置是 \(r=11,12,13\)，因此这一行中超过阈值的下标恰好是 $$r=10,11,12,13.$$ 它们的个数为 $$23+1-2\cdot 10=4.$$ 从 1 到 100 的每一行，代码用的都是同样的逻辑。
C++、Python 和 Java 三个实现都围绕两个数学参数运行：最大行数 \(n_{\max}\) 和阈值 \(T\)。对于题目本身，默认设置是 \(n_{\max}=100\) 与 \(T=10^6\)。另外，三个实现都包含一个很小的校验点：当 \(n_{\max}=10\) 且 \(T=10\) 时，正确答案应为 25。
固定某个 \(n\) 后，实现先把 \(r=0\) 处的系数设为 \(1\)。然后沿着 $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ 向前推进，并用 $$c \leftarrow c\frac{n-r+1}{r}$$ 更新当前值。由于这一步始终得到精确的下一个二项式系数，所以根本不需要浮点数，也不需要额外的二维表。
一旦当前值首次超过阈值，实现就把 $$n+1-2r$$ 加入总数，并立即结束这一行。这样做是正确的，因为第一次越界已经确定了整段居中的超阈值区间。对于第 53 题，这样还有一个直接好处：中间值始终不大，因为循环在刚超过一百万后就停止了，所以三种语言都可以安全地使用普通整数运算。
若上界为 \(N\)，算法最多进行 $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ 次系数更新。对 \(N=100\) 而言，最坏情况下也只有 2500 次更新，而实际次数还要更少，因为很多行在到达中点之前就已经停止。
空间复杂度是 \(O(1)\)。实现只保存当前系数、累计答案以及少量循环变量和参数。这与实际解法的精简结构完全一致。
Для каждого целого \(n\) от 1 до 100 и каждого \(r\) с \(0 \le r \le n\) рассматривается биномиальный коэффициент \(\binom{n}{r}\). Нужно подсчитать, сколько пар \((n,r)\) удовлетворяют неравенству \(\binom{n}{r} \gt 10^6\).
Суть решения в том, что не нужно вычислять каждый коэффициент через факториалы. Реализации идут по каждой строке слева направо, останавливаются при первом превышении миллиона и затем по симметрии сразу подсчитывают оставшийся вклад этой строки.
Обозначим порог через \(T=10^6\). Главная структура задачи возникает из связи соседних биномиальных коэффициентов в одной и той же строке.
Определение $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$ корректно, но для последовательного прохода по строке удобнее сравнить соседние элементы: $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ откуда $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ Начиная с \(\binom{n}{0}=1\), мы можем строить строку слева направо по одному значению за шаг.
Именно это и поддерживает код: после очередного обновления текущая переменная равна точному целому значению \(\binom{n}{r}\). Не нужен ни полный треугольник Паскаля, ни массив факториалов.
Всю строку определяют два факта: $$\binom{n}{r}=\binom{n}{n-r}$$ и $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ Для всех \(1 \le r \le \lfloor n/2 \rfloor\) это отношение больше 1, значит коэффициенты строго возрастают от левого края к середине. После середины те же значения повторяются в обратном порядке из-за симметрии.
Следовательно, как только в левой половине найден первый коэффициент выше порога, положение всех остальных коэффициентов выше порога в этой строке уже известно.
Пусть \(r_0\) есть наименьший индекс, для которого $$\binom{n}{r_0} \gt T.$$ Тогда из возрастания до середины и симметрии после середины следует, что для всех $$r_0 \le r \le n-r_0$$ также верно \(\binom{n}{r} \gt T\). Число таких индексов равно $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ Именно это число реализации добавляют к ответу, как только находят первое превышение.
Если проход дошел до \(\lfloor n/2 \rfloor\), но порог так и не был превышен, то строка дает вклад 0.
Для \(n=23\) рекуррентное вычисление дает $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ Первое значение выше миллиона появляется при \(r_0=10\). По симметрии к нему добавляются отраженные индексы \(r=11,12,13\), поэтому блок превышений равен $$r=10,11,12,13.$$ Его размер равен $$23+1-2\cdot 10=4.$$ Тот же механизм применяется к каждой строке от 1 до 100.
Реализации на C++, Python и Java используют два математических параметра: верхнюю границу \(n_{\max}\) и порог \(T\). Для задачи Project Euler значения по умолчанию равны \(n_{\max}=100\) и \(T=10^6\). Кроме того, во всех трех версиях есть маленькая проверка: при \(n_{\max}=10\) и \(T=10\) правильный ответ равен 25.
Для фиксированного \(n\) реализация начинает с коэффициента \(1\) при \(r=0\). Затем она проходит по значениям $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ и обновляет текущий коэффициент формулой $$c \leftarrow c\frac{n-r+1}{r}.$$ Поскольку на каждом шаге получается точный следующий биномиальный коэффициент, не требуются ни числа с плавающей точкой, ни заранее построенная таблица.
Как только текущий коэффициент превышает порог, реализация прибавляет $$n+1-2r$$ к общему ответу и немедленно заканчивает обработку этой строки. Это корректно, потому что первое превышение уже определяет весь центральный блок значений выше порога. Для задачи 53 такой подход еще и удерживает промежуточные числа маленькими: цикл прекращается сразу после первого значения больше миллиона, поэтому обычной целочисленной арифметики достаточно во всех трех языках.
При верхней границе \(N\) алгоритм выполняет не более $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ обновлений коэффициента. Для \(N=100\) это максимум 2500 шагов, а на практике меньше, потому что многие строки завершаются до достижения середины.
Память имеет порядок \(O(1)\): хранятся только текущий коэффициент, накопленный ответ и несколько счетчиков с параметрами. Это полностью соответствует компактной структуре реального решения.
لكل عدد صحيح \(n\) بحيث \(1 \le n \le 100\)، ولكل \(r\) بحيث \(0 \le r \le n\)، ننظر إلى معامل ذات الحدين \(\binom{n}{r}\). المطلوب هو عد جميع الأزواج \((n,r)\) التي تحقق \(\binom{n}{r} \gt 10^6\).
الفكرة الأساسية هي أن الحل لا يحتاج إلى حساب كل قيمة عبر العوامل. التنفيذات تسير عبر كل صف من اليسار إلى اليمين، وتتوقف عند أول قيمة تتجاوز المليون، ثم تستنتج بقية مساهمة الصف مباشرة من خاصية التناظر.
لنكتب العتبة على صورة \(T=10^6\). البنية المفيدة هنا تأتي من العلاقة بين معاملات ذات الحدين المتتالية داخل الصف نفسه.
التعريف المباشر هو $$\binom{n}{r}=\frac{n!}{r!(n-r)!},$$ لكنه ليس الشكل الأنسب إذا كنا نريد المرور على قيم كثيرة في الصف نفسه. بقسمة حدين متتاليين نحصل على $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r},$$ ومنه $$\binom{n}{r}=\binom{n}{r-1}\frac{n-r+1}{r}.$$ وبالبدء من \(\binom{n}{0}=1\)، يمكننا توليد الصف من اليسار إلى اليمين قيمة بعد أخرى.
هذا هو الثابت الأساسي في الكود: بعد كل تحديث عند قيمة معينة لـ \(r\)، تكون القيمة الجارية مساوية تمامًا لـ \(\binom{n}{r}\). لذلك لا حاجة إلى بناء مثلث باسكال كامل ولا إلى تخزين مصفوفة للعوامل.
يتحكم في الصف كاملًا حقيقتان معروفتان: $$\binom{n}{r}=\binom{n}{n-r}$$ و $$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n-r+1}{r}.$$ لكل \(1 \le r \le \lfloor n/2 \rfloor\) يكون هذا الكسر أكبر من 1، ولذلك تزداد المعاملات زيادة صارمة كلما انتقلنا من الطرف الأيسر نحو الوسط. وبعد نقطة المنتصف تعيد خاصية التناظر القيم نفسها ولكن بترتيب معكوس.
إذن يكفي العثور على أول قيمة تتجاوز العتبة في النصف الأيسر، لأن ذلك يحدد مباشرة جميع القيم الأخرى في الصف التي تتجاوز العتبة أيضًا.
ليكن \(r_0\) أصغر فهرس يحقق $$\binom{n}{r_0} \gt T.$$ عندئذ، وبسبب الزيادة حتى الوسط والتناظر بعده، نحصل على أن جميع القيم ذات الفهارس $$r_0 \le r \le n-r_0$$ تحقق كذلك \(\binom{n}{r} \gt T\). وعدد هذه الفهارس يساوي $$ (n-r_0)-r_0+1 = n+1-2r_0.$$ وهذه هي بالضبط الكمية التي تضيفها التنفيذات إلى المجموع عندما تكتشف أول تجاوز.
أما إذا وصل المسح إلى \(\lfloor n/2 \rfloor\) من دون أن تتجاوز أي قيمة العتبة، فمساهمة ذلك الصف تساوي 0.
عندما \(n=23\)، تعطي العلاقة التكرارية القيم $$\binom{23}{1}=23,\ \binom{23}{2}=253,\ \binom{23}{3}=1771,\ \binom{23}{4}=8855,\ \binom{23}{5}=33649,$$ $$\binom{23}{6}=100947,\ \binom{23}{7}=245157,\ \binom{23}{8}=490314,\ \binom{23}{9}=817190,\ \binom{23}{10}=1144066.$$ أول قيمة تتجاوز المليون تظهر عند \(r_0=10\). وبسبب التناظر تظهر القيم المناظرة عند \(r=11,12,13\)، ولذلك تكون كتلة القيم التي تتجاوز العتبة هي $$r=10,11,12,13.$$ وحجم هذه الكتلة يساوي $$23+1-2\cdot 10=4.$$ وهذا هو المنطق نفسه المستخدم في كل صف من 1 إلى 100.
تنفيذات C++ وPython وJava كلها تعمل باستخدام معاملين رياضيين: الحد الأعلى للصفوف \(n_{\max}\) والعتبة \(T\). في مهمة Project Euler تكون القيم الافتراضية \(n_{\max}=100\) و\(T=10^6\). كما أن كل تنفيذ يحتوي على اختبار تحقق صغير: عندما \(n_{\max}=10\) و\(T=10\)، يجب أن تكون النتيجة الصحيحة هي 25.
لكل \(n\) ثابت، يبدأ التنفيذ من المعامل \(1\) عند \(r=0\). ثم يتقدم عبر $$r=1,2,\dots,\left\lfloor \frac{n}{2}\right\rfloor$$ ويحدّث القيمة الجارية وفق العلاقة $$c \leftarrow c\frac{n-r+1}{r}.$$ وبما أن هذه الخطوة تعطي دائمًا معامل ذات الحدين التالي بدقة تامة، فلا حاجة إلى أعداد فاصلة ولا إلى جدول محسوب مسبقًا.
ما إن تتجاوز القيمة الجارية العتبة حتى يضيف التنفيذ $$n+1-2r$$ إلى المجموع النهائي، ثم يتوقف فورًا عن معالجة ذلك الصف. وهذا صحيح لأن أول تجاوز يحدد كامل الكتلة الوسطى الواقعة فوق العتبة. وفي المسألة 53 يحافظ هذا أيضًا على صغر القيم الوسيطة: فالحل يتوقف مباشرة بعد أول قيمة أكبر من مليون، ولذلك تكفي الحسابات الصحيحة العادية في اللغات الثلاث.
إذا كان الحد الأعلى هو \(N\)، فإن الخوارزمية تنفذ في أسوأ الأحوال $$\sum_{n=1}^{N}\left\lfloor \frac{n}{2}\right\rfloor = O(N^2)$$ من تحديثات المعاملات. وعند \(N=100\) لا يتجاوز هذا الحد 2500 تحديث، وفي الواقع يكون أقل لأن كثيرًا من الصفوف ينتهي قبل الوصول إلى المنتصف.
استهلاك الذاكرة هو \(O(1)\) فقط، لأن التنفيذ يحتفظ بالمعامل الحالي، والنتيجة التراكمية، وبعض العدادات والمعاملات لا أكثر. وهذا يطابق الطبيعة الخفيفة للحل الفعلي.