Define
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
We must evaluate \(T_5(10^{18})\). A direct scan over all \(i\) is impossible, so the implemented solution turns the factorial inequality into a statement about carries in base \(5\), then counts the valid numbers with a memoized digit DP.
Because \((2i)! = 2i\,(2i-1)!\), we have
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
Subtracting \(2v_5(i!)\) gives
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
The middle part is exactly the \(5\)-adic valuation of the central binomial coefficient:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
Since \(v_5(2)=0\), we also have \(v_5(2i)=v_5(i)\). Therefore the original condition is equivalent to
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
Legendre's formula explains why factorial valuations are natural here, but the code uses the binomial rewrite because it exposes a carry-counting interpretation immediately.
Kummer's theorem states that \(v_5\left(\binom{2i}{i}\right)\) equals the number of carries when adding \(i+i\) in base \(5\). Write
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
Multiplying by \(5^a\) merely appends \(a\) trailing zeros in base \(5\), so it does not create or destroy carries; it only shifts their positions. Hence
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
The inequality becomes
$$\operatorname{carries}_5(m+m) \lt a,$$
and because the carry count is an integer, this is the same as
$$\operatorname{carries}_5(m+m)\le a-1.$$
Every positive integer \(i\) has a unique decomposition \(i=5^a m\) with \(5\nmid m\). For a fixed \(a\ge 1\), the admissible values of \(m\) satisfy
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m,$$
and they contribute exactly when \(\operatorname{carries}_5(m+m)\le a-1\). Define \(G(x,k)\) to be the number of positive integers \(m\le x\), not divisible by \(5\), whose doubling in base \(5\) produces at most \(k\) carries. Then
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
The sum stops as soon as \(5^a \gt N\). For \(N=10^{18}\), only \(25\) values of \(a\) need to be examined.
The programs process digits from least significant to most significant. Let \(F(x,k,c)\) denote the number of integers \(0\le n\le x\) such that, when doubling \(n\) in base \(5\), the still-unprocessed higher digits create at most \(k\) additional carries, assuming an incoming carry \(c\in\{0,1\}\) from the lower digits.
If the current digit is \(d\in\{0,1,2,3,4\}\), the outgoing carry is
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
Writing \(n=d+5q\) gives \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\), so the recurrence is
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
The base cases are exactly the ones in the source files:
$$F(x,k,c)=0\quad \text{if }x\lt 0\text{ or }k\lt 0,\qquad F(0,k,c)=1\quad \text{for }k\ge 0.$$
To enforce \(5\nmid m\), the least significant digit must be \(1,2,3,\) or \(4\). Therefore
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
This is precisely what the helper count_non_multiples_of_five computes.
If \(i=20=5\cdot 4\), then \(a=1\) and \(m=4\). In base \(5\),
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
so there is one carry. Since \(1 \nleq 0\), this \(i\) does not contribute. By contrast, \(i=35=5\cdot 7\) has \(m=\left(12\right)_5\), and
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
which creates no carries, so it does contribute for \(a=1\). This is exactly the local criterion used by the DP.
The C++, Python, and Java files all implement the same recurrence. carry_out returns \(c'=\lfloor(2d+c)/5\rfloor\). count_with_initial_carry is the memoized function \(F(x,k,c)\), keyed by \((x,k,\text{carry\_in})\). count_non_multiples_of_five handles the first digit separately so the counted number is positive and not divisible by \(5\). The outer loop iterates over \(a=1,2,\dots\) while \(5^a\le N\), accumulating \(G(\lfloor N/5^a\rfloor,a-1)\). The C++ implementation also validates the method with checkpoints \(T_5(10^3)=68\), \(T_5(10^9)=2408210\), and a brute-force comparison at \(N=20000\).
Let \(A=\lfloor\log_5 N\rfloor\). The outer sum has \(A\) terms, and each recursive step removes one base-\(5\) digit. Every memo state has only \(5\) outgoing transitions and is determined by a triple \((x,k,c)\) with \(c\in\{0,1\}\). Thus the cost is proportional to the number of reachable memo states rather than to \(N\) itself, and the memory usage is the same order as the memo table. For the actual target \(N=10^{18}\), the reachable state space is tiny, so the method is effectively instantaneous compared with brute force.
Definiert ist
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
Gesucht ist also \(T_5(10^{18})\). Ein direkter Durchlauf über alle \(i\) ist unmöglich, daher wandelt die Lösung die Fakultätsungleichung in eine Aussage über Überträge in Basis \(5\) um und zählt die gültigen Zahlen anschließend mit einer memoisierten Ziffern-DP.
Aus \((2i)! = 2i\,(2i-1)!\) folgt
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
Subtrahiert man \(2v_5(i!)\), erhält man
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
Der mittlere Ausdruck ist genau die \(5\)-adische Bewertung des zentralen Binomialkoeffizienten:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
Da \(v_5(2)=0\), gilt außerdem \(v_5(2i)=v_5(i)\). Damit ist die ursprüngliche Bedingung äquivalent zu
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
Die Legendre-Formel beschreibt dieselben Fakultätsbewertungen, aber für den Algorithmus ist diese Binomialform entscheidend, weil sie direkt zum Übertragsmodell führt.
Nach Kummer ist \(v_5\left(\binom{2i}{i}\right)\) gleich der Anzahl der Überträge beim Addieren von \(i+i\) in Basis \(5\). Schreibe
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
Die Multiplikation mit \(5^a\) hängt in Basis \(5\) nur \(a\) Nullen an und verschiebt die Überträge daher lediglich nach links; ihre Anzahl ändert sich nicht. Also
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
Die Ungleichung wird damit zu
$$\operatorname{carries}_5(m+m) \lt a,$$
beziehungsweise, da die Übertragszahl ganzzahlig ist, zu
$$\operatorname{carries}_5(m+m)\le a-1.$$
Jede positive ganze Zahl besitzt die eindeutige Zerlegung \(i=5^a m\) mit \(5\nmid m\). Für festes \(a\ge 1\) müssen die möglichen \(m\) die Bedingungen
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m$$
erfüllen und zusätzlich \(\operatorname{carries}_5(m+m)\le a-1\). Sei \(G(x,k)\) die Anzahl positiver Zahlen \(m\le x\), die nicht durch \(5\) teilbar sind und beim Verdoppeln in Basis \(5\) höchstens \(k\) Überträge erzeugen. Dann gilt
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
Die Summe endet automatisch, sobald \(5^a \gt N\). Für \(N=10^{18}\) gibt es nur \(25\) relevante Werte von \(a\).
Die Programme verarbeiten die Ziffern von der niederwertigsten zur höchstwertigen Stelle. Sei \(F(x,k,c)\) die Anzahl der Zahlen \(0\le n\le x\), für die das Verdoppeln von \(n\) in Basis \(5\) in den noch nicht bearbeiteten höheren Stellen höchstens \(k\) weitere Überträge erzeugt, wenn aus den bereits bearbeiteten niedrigeren Stellen ein Eingangstrag \(c\in\{0,1\}\) ankommt.
Ist \(d\in\{0,1,2,3,4\}\) die aktuelle Ziffer, dann lautet der Ausgangstrag
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
Mit \(n=d+5q\) folgt \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\), also die Rekursion
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
Die Basisfälle sind genau wie in den Quelldateien:
$$F(x,k,c)=0\quad \text{falls }x\lt 0\text{ oder }k\lt 0,\qquad F(0,k,c)=1\quad \text{für }k\ge 0.$$
Damit \(5\nmid m\) gilt, muss die niederwertigste Ziffer von \(m\) eine der Ziffern \(1,2,3,4\) sein. Deshalb ist
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
Genau diesen Schritt kapselt die Hilfsfunktion count_non_multiples_of_five.
Für \(i=20=5\cdot 4\) gilt \(a=1\) und \(m=4\). In Basis \(5\) ist
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
also entsteht ein Übertrag. Da \(1 \nleq 0\), trägt dieses \(i\) nicht bei. Dagegen hat \(i=35=5\cdot 7\) den Kern \(m=\left(12\right)_5\), und
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
was ohne Übertrag auskommt. Dieses \(i\) wird für \(a=1\) also gezählt. Genau dieses lokale Kriterium bildet die DP nach.
Die C++-, Python- und Java-Dateien implementieren dieselbe Rekursion. carry_out berechnet \(c'=\lfloor(2d+c)/5\rfloor\). count_with_initial_carry ist die memoisiert gespeicherte Funktion \(F(x,k,c)\) mit Schlüssel \((x,k,\text{carry\_in})\). count_non_multiples_of_five behandelt die erste Ziffer separat, damit die gezählte Zahl positiv und nicht durch \(5\) teilbar ist. Die äußere Schleife läuft über \(a=1,2,\dots\) mit \(5^a\le N\) und summiert \(G(\lfloor N/5^a\rfloor,a-1)\). Die C++-Version prüft die Methode zusätzlich mit den Kontrollwerten \(T_5(10^3)=68\), \(T_5(10^9)=2408210\) und einem Brute-Force-Abgleich bei \(N=20000\).
Sei \(A=\lfloor\log_5 N\rfloor\). Die äußere Summe besitzt \(A\) Terme, und jeder Rekursionsschritt entfernt genau eine Basis-\(5\)-Ziffer. Jeder Memo-Zustand hat nur \(5\) ausgehende Übergänge und wird durch ein Tripel \((x,k,c)\) mit \(c\in\{0,1\}\) beschrieben. Damit hängt der Aufwand von der Zahl der tatsächlich erreichbaren Zustände ab und nicht linear von \(N\). Der Speicherbedarf hat dieselbe Größenordnung wie die Memo-Tabelle. Für \(N=10^{18}\) ist dieser Zustandsraum sehr klein, sodass die Methode praktisch sofort läuft.
Şu fonksiyonu tanımlayalım:
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
Amaç \(T_5(10^{18})\) değerini hesaplamaktır. Tüm \(i\) değerlerini tek tek denemek imkansız olduğundan çözüm, faktöriyel eşitsizliğini taban \(5\)'teki taşıma sayısına çevirir ve ardından geçerli sayıları memoization kullanan bir basamak DP ile sayar.
\((2i)! = 2i\,(2i-1)!\) olduğundan
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
Buradan \(2v_5(i!)\) çıkarılırsa
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i)$$
elde edilir. Ortadaki ifade merkezi binom katsayısının \(5\)-adik değerlemesidir:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
Ayrıca \(v_5(2)=0\) olduğu için \(v_5(2i)=v_5(i)\). Böylece başlangıç koşulu
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i)$$
şekline dönüşür. Legendre formülü aynı değerlemeleri açıklasa da kod için belirleyici olan bu binom dönüşümüdür; çünkü taşıma yorumuna doğrudan gider.
Kummer teoremine göre \(v_5\left(\binom{2i}{i}\right)\), taban \(5\)'te \(i+i\) toplanırken oluşan taşıma sayısına eşittir. Şimdi
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m$$
yazalım. \(5^a\) ile çarpmak taban \(5\)'te sadece sona \(a\) tane sıfır ekler; bu yüzden taşıma sayısını değiştirmez, yalnızca taşımanın konumlarını kaydırır. Dolayısıyla
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
Eşitsizlik artık
$$\operatorname{carries}_5(m+m) \lt a$$
olur; taşıma sayısı tam sayı olduğundan bu,
$$\operatorname{carries}_5(m+m)\le a-1$$
ile aynıdır.
Her pozitif \(i\) sayısı \(i=5^a m\), \(5\nmid m\) biçiminde tekil olarak yazılır. Sabit bir \(a\ge 1\) için uygun \(m\) değerleri
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m$$
koşullarını sağlar ve yalnızca \(\operatorname{carries}_5(m+m)\le a-1\) ise katkı verir. \(G(x,k)\), \(x\)'ten büyük olmayan, \(5\)'e bölünmeyen ve taban \(5\)'te ikiyle çarpılınca en fazla \(k\) taşıma üreten pozitif tamsayı sayısı olsun. O zaman
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
\(5^a \gt N\) olduğunda toplam kendiliğinden biter. \(N=10^{18}\) için yalnızca \(25\) farklı \(a\) değeri gerekir.
Çözüm dosyaları basamakları sağdan sola işler. \(F(x,k,c)\), \(0\le n\le x\) aralığındaki sayılardan, taban \(5\)'te \(n+n\) işleminin henüz işlenmemiş daha yüksek basamaklarında en fazla \(k\) ek taşıma üretenlerin sayısı olsun; burada \(c\in\{0,1\}\), daha düşük basamaklardan gelen başlangıç taşımasını gösterir.
Geçerli basamak \(d\in\{0,1,2,3,4\}\) ise yeni taşıma
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor$$
olur. \(n=d+5q\) yazıldığında \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\) olduğu için özyineleme
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right)$$
şeklindedir. Taban durumları kaynak kodla birebir aynıdır:
$$F(x,k,c)=0\quad \text{eğer }x\lt 0\text{ veya }k\lt 0,\qquad F(0,k,c)=1\quad \text{eğer }k\ge 0.$$
\(5\nmid m\) koşulu için en düşük basamak \(1,2,3\) veya \(4\) olmalıdır. Bu yüzden
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right)$$
olur. Kodda bu sarıcı işlevi count_non_multiples_of_five üstlenir.
\(i=20=5\cdot 4\) için \(a=1\) ve \(m=4\) olur. Taban \(5\)'te
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
yani bir taşıma vardır. \(1 \nleq 0\) olduğundan bu \(i\) sayılmaz. Buna karşılık \(i=35=5\cdot 7\) için \(m=\left(12\right)_5\) ve
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
burada hiç taşıma oluşmaz. Bu nedenle bu \(i\), \(a=1\) katmanında sayılır. DP tam olarak bu yerel koşulu kodlar.
C++, Python ve Java çözümleri aynı özyinelemeyi uygular. carry_out, \(c'=\lfloor(2d+c)/5\rfloor\) değerini hesaplar. count_with_initial_carry, \((x,k,\text{carry\_in})\) anahtarıyla saklanan memoize \(F(x,k,c)\) fonksiyonudur. count_non_multiples_of_five ilk basamağı ayrı ele alarak sayının hem pozitif olmasını hem de \(5\)'e bölünmemesini garanti eder. Dış döngü \(a=1,2,\dots\) boyunca \(5^a\le N\) oldukça ilerler ve \(G(\lfloor N/5^a\rfloor,a-1)\) terimlerini toplar. C++ dosyası ayrıca yöntemi \(T_5(10^3)=68\), \(T_5(10^9)=2408210\) kontrol noktaları ve \(N=20000\) için brute-force karşılaştırmasıyla doğrular.
\(A=\lfloor\log_5 N\rfloor\) olsun. Dış toplam \(A\) terimden oluşur ve her özyineleme adımı bir taban-\(5\) basamağını kaldırır. Her memo durumu sadece \(5\) geçişe sahiptir ve \((x,k,c)\) üçlüsü ile tanımlanır; burada \(c\in\{0,1\}\). Bu nedenle çalışma süresi \(N\)'in kendisine değil, erişilebilir memo durumlarının sayısına bağlıdır. Bellek kullanımı da aynı büyüklüktedir. \(N=10^{18}\) için durum uzayı çok küçük kaldığından yöntem brute-force'a göre son derece hızlıdır.
Definimos
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
Debemos calcular \(T_5(10^{18})\). Recorrer todos los \(i\) es inviable, así que la solución transforma la desigualdad entre factoriales en una condición sobre acarreos en base \(5\), y luego cuenta los enteros válidos mediante una digit-DP con memoización.
Como \((2i)! = 2i\,(2i-1)!\), se tiene
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
Al restar \(2v_5(i!)\) obtenemos
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
La parte central es exactamente la valuación \(5\)-ádica del coeficiente binomial central:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
Además, \(v_5(2)=0\), así que \(v_5(2i)=v_5(i)\). Por tanto, la condición original equivale a
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
La fórmula de Legendre describe las mismas valuaciones factoriales, pero la implementación usa esta reescritura binomial porque conecta de forma directa con el conteo de acarreos.
El teorema de Kummer afirma que \(v_5\left(\binom{2i}{i}\right)\) coincide con el número de acarreos al sumar \(i+i\) en base \(5\). Escribimos
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
Multiplicar por \(5^a\) solo añade \(a\) ceros finales en base \(5\), así que no cambia cuántos acarreos aparecen; únicamente desplaza su posición. Luego
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
La desigualdad pasa a ser
$$\operatorname{carries}_5(m+m) \lt a,$$
o, como el número de acarreos es entero,
$$\operatorname{carries}_5(m+m)\le a-1.$$
Cada entero positivo se descompone de manera única como \(i=5^a m\) con \(5\nmid m\). Para un \(a\ge 1\) fijo, los posibles valores de \(m\) cumplen
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m,$$
y contribuyen exactamente cuando \(\operatorname{carries}_5(m+m)\le a-1\). Sea \(G(x,k)\) el número de enteros positivos \(m\le x\), no divisibles por \(5\), cuyo doblado en base \(5\) produce a lo sumo \(k\) acarreos. Entonces
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
La suma termina en cuanto \(5^a \gt N\). Para \(N=10^{18}\) solo aparecen \(25\) valores relevantes de \(a\).
Los programas procesan primero el dígito menos significativo. Sea \(F(x,k,c)\) el número de enteros \(0\le n\le x\) tales que, al doblar \(n\) en base \(5\), las cifras superiores aún no procesadas generan como mucho \(k\) acarreos adicionales, suponiendo que llega un acarreo de entrada \(c\in\{0,1\}\) desde las cifras inferiores.
Si el dígito actual es \(d\in\{0,1,2,3,4\}\), el acarreo de salida es
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
Al escribir \(n=d+5q\), se obtiene \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\), de modo que la recurrencia es
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
Los casos base son exactamente los del código fuente:
$$F(x,k,c)=0\quad \text{si }x\lt 0\text{ o }k\lt 0,\qquad F(0,k,c)=1\quad \text{si }k\ge 0.$$
Para imponer \(5\nmid m\), la cifra menos significativa debe ser \(1,2,3\) o \(4\). Así,
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
Eso es exactamente lo que implementa la función auxiliar count_non_multiples_of_five.
Si \(i=20=5\cdot 4\), entonces \(a=1\) y \(m=4\). En base \(5\),
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
así que aparece un acarreo. Como \(1 \nleq 0\), ese \(i\) no cuenta. En cambio, \(i=35=5\cdot 7\) tiene \(m=\left(12\right)_5\), y
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
lo que no produce acarreos, de modo que sí contribuye para \(a=1\). Ese es exactamente el criterio local que usa la DP.
Los archivos en C++, Python y Java implementan la misma recurrencia. carry_out calcula \(c'=\lfloor(2d+c)/5\rfloor\). count_with_initial_carry es la función memoizada \(F(x,k,c)\), indexada por \((x,k,\text{carry\_in})\). count_non_multiples_of_five trata aparte el primer dígito para garantizar que el número contado sea positivo y no múltiplo de \(5\). El bucle exterior recorre \(a=1,2,\dots\) mientras \(5^a\le N\) y acumula \(G(\lfloor N/5^a\rfloor,a-1)\). El archivo C++ además verifica el método con los puntos de control \(T_5(10^3)=68\), \(T_5(10^9)=2408210\) y una comparación por fuerza bruta en \(N=20000\).
Sea \(A=\lfloor\log_5 N\rfloor\). La suma exterior tiene \(A\) términos, y cada paso recursivo elimina una cifra en base \(5\). Cada estado memoizado tiene solo \(5\) transiciones salientes y viene determinado por un triple \((x,k,c)\) con \(c\in\{0,1\}\). Por eso el coste depende del número de estados realmente alcanzables, no de recorrer todos los enteros hasta \(N\). La memoria tiene el mismo orden que la tabla de memoización. Para \(N=10^{18}\), el espacio de estados es minúsculo y el método resulta muy rápido.
定义
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
目标是计算 \(T_5(10^{18})\)。如果对所有 \(i\) 暴力检查，规模完全不可接受，所以程序先把阶乘不等式改写成一个关于五进制进位次数的条件，再用带记忆化的数位 DP 进行统计。
由 \((2i)! = 2i\,(2i-1)!\) 可得
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
于是
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
中间那一项正好就是中心二项式系数的 \(5\)-进估值：
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
又因为 \(v_5(2)=0\)，所以 \(v_5(2i)=v_5(i)\)。原条件因此等价于
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
Legendre 公式同样可以描述阶乘中的 \(5\)-进指数，但代码采用这一步改写，是因为它能直接引出进位解释。
Kummer 定理说明，\(v_5\left(\binom{2i}{i}\right)\) 恰好等于在五进制下做 \(i+i\) 时产生的进位次数。写成
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
乘以 \(5^a\) 只会在五进制末尾附加 \(a\) 个零，不会改变进位总数，只会把进位位置整体向高位平移。因此
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
于是原不等式变成
$$\operatorname{carries}_5(m+m) \lt a,$$
由于进位次数是整数，也就是
$$\operatorname{carries}_5(m+m)\le a-1.$$
每个正整数都能唯一写成 \(i=5^a m\) 且 \(5\nmid m\)。对于固定的 \(a\ge 1\)，可选的 \(m\) 必须满足
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m,$$
并且只有在 \(\operatorname{carries}_5(m+m)\le a-1\) 时才会被计入。设 \(G(x,k)\) 表示满足 \(m\le x\)、\(5\nmid m\)、并且在五进制下做 \(m+m\) 至多产生 \(k\) 次进位的正整数个数，则
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
一旦 \(5^a \gt N\)，外层求和自然停止。对 \(N=10^{18}\) 来说，只有 \(25\) 个 \(a\) 需要考虑。
程序从最低位向高位递归。定义 \(F(x,k,c)\) 为：在所有 \(0\le n\le x\) 的整数中，把 \(n\) 在五进制下加倍时，尚未处理的高位部分最多再产生 \(k\) 次进位，且低位已经传来一个进位 \(c\in\{0,1\}\) 的方案数。
如果当前位数字是 \(d\in\{0,1,2,3,4\}\)，那么传向更高位的进位为
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
写成 \(n=d+5q\) 后，有 \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\)，因此递推式是
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
边界条件与源代码完全一致：
$$F(x,k,c)=0\quad \text{若 }x\lt 0\text{ 或 }k\lt 0,\qquad F(0,k,c)=1\quad \text{若 }k\ge 0.$$
为了保证 \(5\nmid m\)，最低位只能取 \(1,2,3,4\)。于是
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
这正是辅助函数 count_non_multiples_of_five 的数学含义。
若 \(i=20=5\cdot 4\)，则 \(a=1\)，\(m=4\)。在五进制中
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
会产生一次进位。因为 \(1 \nleq 0\)，所以这个 \(i\) 不计入。相反，\(i=35=5\cdot 7\) 时 \(m=\left(12\right)_5\)，且
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
完全没有进位，所以它会在 \(a=1\) 这一层被计入。DP 正是在逐位编码这个局部判据。
C++、Python 和 Java 三个版本实现的是同一套递推。carry_out 计算 \(c'=\lfloor(2d+c)/5\rfloor\)。count_with_initial_carry 就是带记忆化的 \(F(x,k,c)\)，键为 \((x,k,\text{carry\_in})\)。count_non_multiples_of_five 单独处理最低位，从而保证被统计的数是正数且不被 \(5\) 整除。外层循环遍历 \(a=1,2,\dots\)，只要 \(5^a\le N\) 就把 \(G(\lfloor N/5^a\rfloor,a-1)\) 加入答案。C++ 文件还用 \(T_5(10^3)=68\)、\(T_5(10^9)=2408210\) 和 \(N=20000\) 的暴力校验来验证实现。
设 \(A=\lfloor\log_5 N\rfloor\)。外层求和有 \(A\) 项，而每次递归都会去掉一个五进制数字。每个记忆化状态只有 \(5\) 条转移，状态由三元组 \((x,k,c)\) 唯一确定，其中 \(c\in\{0,1\}\)。因此，算法的代价取决于实际能到达的状态数，而不是与 \(N\) 成线性关系。空间复杂度与记忆化表同阶。对于目标 \(N=10^{18}\)，可达状态非常少，所以运行速度远快于暴力枚举。
Определим
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
Нужно вычислить \(T_5(10^{18})\). Полный перебор всех \(i\) нереален, поэтому решение переводит неравенство для факториалов в условие на число переносов при сложении в системе счисления по основанию \(5\), а затем считает подходящие числа с помощью memoized digit-DP.
Из равенства \((2i)! = 2i\,(2i-1)!\) следует
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
После вычитания \(2v_5(i!)\) получаем
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
Средняя часть в точности равна \(5\)-адической оценке центрального биномиального коэффициента:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
Так как \(v_5(2)=0\), имеем \(v_5(2i)=v_5(i)\). Значит, исходное условие эквивалентно
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
Формула Лежандра описывает те же факториальные оценки, но для алгоритма важнее именно биномиальная форма, поскольку она сразу открывает интерпретацию через переносы.
Теорема Куммера утверждает, что \(v_5\left(\binom{2i}{i}\right)\) равно числу переносов при сложении \(i+i\) в системе счисления по основанию \(5\). Запишем
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
Умножение на \(5^a\) лишь дописывает \(a\) нулей справа в записи по основанию \(5\), поэтому число переносов не меняется, а только сдвигается по разрядам. Следовательно,
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
Неравенство превращается в
$$\operatorname{carries}_5(m+m) \lt a,$$
или, поскольку число переносов целое, в
$$\operatorname{carries}_5(m+m)\le a-1.$$
Каждое положительное число единственным образом представимо как \(i=5^a m\) при \(5\nmid m\). Для фиксированного \(a\ge 1\) возможные значения \(m\) должны удовлетворять условиям
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m,$$
и вносить вклад только тогда, когда \(\operatorname{carries}_5(m+m)\le a-1\). Пусть \(G(x,k)\) обозначает число положительных \(m\le x\), не делящихся на \(5\), для которых удвоение в записи по основанию \(5\) создает не более \(k\) переносов. Тогда
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
Как только \(5^a \gt N\), внешняя сумма обрывается. Для \(N=10^{18}\) достаточно рассмотреть лишь \(25\) значений \(a\).
Программы обрабатывают число справа налево, то есть от младшего разряда к старшему. Пусть \(F(x,k,c)\) равно числу целых \(0\le n\le x\), для которых при удвоении \(n\) в базе \(5\) еще не обработанные старшие разряды создают не более \(k\) дополнительных переносов, если из младших разрядов уже пришел входной перенос \(c\in\{0,1\}\).
Если текущая цифра равна \(d\in\{0,1,2,3,4\}\), то перенос в следующий разряд равен
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
При разложении \(n=d+5q\) получаем ограничение \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\), а значит, рекурсия имеет вид
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
Базовые случаи в точности совпадают с исходниками:
$$F(x,k,c)=0\quad \text{если }x\lt 0\text{ или }k\lt 0,\qquad F(0,k,c)=1\quad \text{при }k\ge 0.$$
Чтобы гарантировать условие \(5\nmid m\), младший разряд числа \(m\) должен быть одним из \(1,2,3,4\). Поэтому
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
Именно эту обертку реализует функция count_non_multiples_of_five.
Если \(i=20=5\cdot 4\), то \(a=1\) и \(m=4\). В записи по основанию \(5\)
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
то есть возникает один перенос. Поскольку \(1 \nleq 0\), такое \(i\) не подходит. А вот для \(i=35=5\cdot 7\) имеем \(m=\left(12\right)_5\), и
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
что не дает переносов, поэтому это \(i\) учитывается на уровне \(a=1\). Именно такой локальный критерий и кодирует DP.
Файлы на C++, Python и Java реализуют одну и ту же рекурсию. carry_out вычисляет \(c'=\lfloor(2d+c)/5\rfloor\). count_with_initial_carry есть memoized версия функции \(F(x,k,c)\) с ключом \((x,k,\text{carry\_in})\). count_non_multiples_of_five обрабатывает первый разряд отдельно, чтобы считались только положительные числа, не кратные \(5\). Внешний цикл перебирает \(a=1,2,\dots\) при \(5^a\le N\) и накапливает \(G(\lfloor N/5^a\rfloor,a-1)\). В C++-файле также есть проверки: \(T_5(10^3)=68\), \(T_5(10^9)=2408210\) и сравнение с полным перебором для \(N=20000\).
Пусть \(A=\lfloor\log_5 N\rfloor\). Во внешней сумме \(A\) слагаемых, а каждый рекурсивный шаг удаляет один разряд в записи по основанию \(5\). У каждого memo-состояния только \(5\) переходов, и состояние задается тройкой \((x,k,c)\), где \(c\in\{0,1\}\). Поэтому время работы определяется числом реально достижимых состояний, а не линейным обходом до \(N\). Память имеет тот же порядок, что и таблица мемоизации. Для \(N=10^{18}\) пространство состояний очень мало, так что метод работает практически мгновенно.
نعرّف
$$T_5(N)=\#\left\{1\le i\le N: v_5((2i-1)!) \lt 2v_5(i!)\right\}.$$
المطلوب هو حساب \(T_5(10^{18})\). الفحص المباشر لكل القيم \(i\) غير عملي إطلاقًا، لذلك يحوّل الحل المتباينة الخاصة بالعوامل إلى شرط على عدد النقلات عند الجمع في الأساس \(5\)، ثم يعدّ القيم الصحيحة المناسبة باستعمال digit-DP مع memoization.
بما أن \((2i)! = 2i\,(2i-1)!\)، فنحصل على
$$v_5((2i-1)!) = v_5((2i)!)-v_5(2i).$$
وبطرح \(2v_5(i!)\) من الطرفين يظهر
$$v_5((2i-1)!)-2v_5(i!)=v_5((2i)!)-2v_5(i!)-v_5(2i).$$
والحد الأوسط هو بالضبط قيمة \(5\)-أديّة لمعامل ثنائي الحدين المركزي:
$$v_5((2i)!)-2v_5(i!)=v_5\left(\binom{2i}{i}\right).$$
ولأن \(v_5(2)=0\)، فإن \(v_5(2i)=v_5(i)\). وهكذا تصبح المتباينة الأصلية مكافئة لـ
$$v_5\left(\binom{2i}{i}\right) \lt v_5(i).$$
صيغة لوجندر تصف تقييمات العوامل أيضًا، لكن هذه الصياغة الثنائية هي الأنسب برمجيًا لأنها تقود مباشرة إلى تفسير يعتمد على النقلات.
تنص مبرهنة كومر على أن \(v_5\left(\binom{2i}{i}\right)\) يساوي عدد النقلات عند جمع \(i+i\) في الأساس \(5\). نكتب
$$i=5^a m,\qquad a=v_5(i),\qquad 5\nmid m.$$
الضرب في \(5^a\) لا يفعل سوى إضافة \(a\) أصفار في النهاية في التمثيل الخماسي، ولذلك لا يغيّر عدد النقلات بل يزيح مواضعها فقط. ومن ثم
$$\operatorname{carries}_5(i+i)=\operatorname{carries}_5(m+m).$$
فتصبح المتباينة
$$\operatorname{carries}_5(m+m) \lt a,$$
وبما أن عدد النقلات عدد صحيح فهذا يكافئ
$$\operatorname{carries}_5(m+m)\le a-1.$$
كل عدد صحيح موجب يكتب بشكل وحيد على صورة \(i=5^a m\) مع \(5\nmid m\). وعند تثبيت \(a\ge 1\)، يجب أن تحقق القيم الممكنة لـ \(m\)
$$1\le m\le \left\lfloor\frac{N}{5^a}\right\rfloor,\qquad 5\nmid m,$$
ولا تسهم إلا إذا كان \(\operatorname{carries}_5(m+m)\le a-1\). لنعرّف \(G(x,k)\) بأنه عدد الأعداد الصحيحة الموجبة \(m\le x\) غير القابلة للقسمة على \(5\)، والتي يولد فيها التضعيف في الأساس \(5\) ما لا يزيد على \(k\) نقلات. عندئذ
$$\boxed{T_5(N)=\sum_{a\ge 1} G\left(\left\lfloor\frac{N}{5^a}\right\rfloor,a-1\right).}$$
ويتوقف هذا المجموع تلقائيًا عندما يصبح \(5^a \gt N\). وبالنسبة إلى \(N=10^{18}\) لا نحتاج إلا إلى \(25\) قيمة مختلفة لـ \(a\).
تعالج الملفات البرمجية الخانات من اليمين إلى اليسار. نرمز بـ \(F(x,k,c)\) إلى عدد الأعداد \(0\le n\le x\) التي لا ينتج من خاناتها العليا غير المعالجة أكثر من \(k\) نقلات إضافية عند حساب \(n+n\) في الأساس \(5\)، وذلك بافتراض وجود نقلة داخلة \(c\in\{0,1\}\) قادمة من الخانات الأدنى.
إذا كانت الخانة الحالية هي \(d\in\{0,1,2,3,4\}\)، فإن النقلة الخارجة تساوي
$$c'=\left\lfloor\frac{2d+c}{5}\right\rfloor.$$
وبكتابة \(n=d+5q\) نحصل على \(q\le \left\lfloor\frac{x-d}{5}\right\rfloor\)، ولذلك تكون العلاقة العودية
$$F(x,k,c)=\sum_{\substack{0\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-c',c'\right).$$
أما الحالتان الأساسيتان فمطابقتان تمامًا لما في الشيفرة:
$$F(x,k,c)=0\quad \text{if }x\lt 0\text{ or }k\lt 0,\qquad F(0,k,c)=1\quad \text{if }k\ge 0.$$
ولكي نضمن الشرط \(5\nmid m\)، يجب أن تكون الخانة الأقل أهمية إحدى القيم \(1,2,3,4\). لذلك
$$G(x,k)=\sum_{\substack{1\le d\le 4\\ d\le x}} F\left(\left\lfloor\frac{x-d}{5}\right\rfloor,k-\left\lfloor\frac{2d}{5}\right\rfloor,\left\lfloor\frac{2d}{5}\right\rfloor\right).$$
وهذا هو بالضبط ما تنفذه الدالة المساعدة count_non_multiples_of_five.
إذا أخذنا \(i=20=5\cdot 4\)، فلدينا \(a=1\) و\(m=4\). وفي الأساس \(5\)
$$\left(4\right)_5+\left(4\right)_5=\left(13\right)_5,$$
أي توجد نقلة واحدة. وبما أن \(1 \nleq 0\)، فإن هذا العدد لا يُحسب. أما \(i=35=5\cdot 7\) فله \(m=\left(12\right)_5\)، و
$$\left(12\right)_5+\left(12\right)_5=\left(24\right)_5,$$
ولا تظهر هنا أي نقلة، لذلك يُحسب هذا العدد عند المستوى \(a=1\). هذا هو الشرط المحلي نفسه الذي تبنيه الـ DP.
الملفات في C++ وPython وJava تطبق جميعها العودية نفسها. الدالة carry_out تحسب \(c'=\lfloor(2d+c)/5\rfloor\). والدالة count_with_initial_carry هي النسخة ذات الذاكرة من \(F(x,k,c)\)، ومفتاحها هو \((x,k,\text{carry\_in})\). أما count_non_multiples_of_five فتعالج أول خانة على نحو منفصل كي يكون العدد المحسوب موجبًا وغير قابل للقسمة على \(5\). وتتحرك الحلقة الخارجية على القيم \(a=1,2,\dots\) ما دام \(5^a\le N\)، ثم تجمع الحدود \(G(\lfloor N/5^a\rfloor,a-1)\). كما يحتوي ملف C++ على نقاط تحقق هي \(T_5(10^3)=68\) و\(T_5(10^9)=2408210\)، إضافة إلى مقارنة brute-force عند \(N=20000\).
لنضع \(A=\lfloor\log_5 N\rfloor\). يتكون المجموع الخارجي من \(A\) حدود، وكل خطوة عودية تزيل خانة واحدة في التمثيل الخماسي. لكل حالة memoized خمس انتقالات فقط، والحالة توصف بالثلاثي \((x,k,c)\) حيث \(c\in\{0,1\}\). لذلك فالزمن يعتمد على عدد الحالات القابلة للوصول فعليًا، لا على المرور الخطي على جميع الأعداد حتى \(N\). واستهلاك الذاكرة من نفس رتبة حجم جدول الحفظ. بالنسبة إلى \(N=10^{18}\)، يكون فضاء الحالات صغيرًا جدًا، ولذلك تعمل الطريقة بسرعة كبيرة جدًا.