For Problem 664, the quantity coming from the infinite game is not evaluated by simulating positions directly. The C++, Python, and Java implementations all use an equivalent closed form built from the golden ratio
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
Once this series is known, the required answer is
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
The challenge is numerical rather than combinatorial. For large \(n\), the dominant terms of the series are enormous, the tails are tiny, and a naive evaluation would overflow or waste work on irrelevant terms. The solution therefore works in the logarithmic domain and keeps only the narrow peak region that materially contributes to the sum.
Let
$$a_d=\frac{d^n}{\varphi^d}.$$
Instead of forming \(a_d\) directly, take logarithms:
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
Then the infinite series becomes
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
This removes the overflow risk from the dominant terms and turns the problem into computing a stable logarithm of a sum.
The mass of the series is concentrated near the maximum of \(L(d)\). Treating the index as a real variable \(x\), define
$$f(x)=n\log x-x\log\varphi.$$
Its derivative is
$$f'(x)=\frac{n}{x}-\log\varphi,$$
so the stationary point satisfies
$$x_*=\frac{n}{\log\varphi}.$$
Because
$$f''(x)=-\frac{n}{x^2}\lt 0,$$
this point is a strict maximum. The best integer \(d\) must therefore lie very close to \(n/\log\varphi\), which is why the implementation only needs a tiny local scan around that estimate to find the true peak term.
Once the peak value \(L_{\max}\) is known, terms far away from it are numerically irrelevant. The implementations expand left and right from the peak until
$$L_{\max}-L(d)\gt 120.$$
At that point the term is smaller than the peak term by a factor of \(e^{-120}\), and the remaining tail only shrinks further because the profile is already descending on that side. This gives a practical finite window
$$d\in[L,R]$$
that contains all numerically significant contributions.
Directly summing \(e^{L(d)}\) would still be unsafe near the peak. The stable reformulation is
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
Now every exponent \(L(d)-L_{\max}\) is non-positive, so the largest rescaled term is exactly \(1\) and all others lie in \((0,1]\). This is the central numerical device used by all three implementations.
After \(\log A_n\) has been computed, convert from base \(e\) to base \(\varphi\):
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
The answer is then
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
A tiny negative epsilon is subtracted before the ceiling is taken. This protects against a floating-point boundary case where the true value is an integer but the computed value lands infinitesimally above it.
For \(n=2\), the series can be checked exactly. Set
$$x=\frac{1}{\varphi}.$$
Then
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
The classical generating-function identity gives
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
Since \(x=1/\varphi\), we have \(x+1=\varphi\) and \(1-x=1/\varphi^2\). Therefore
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
So
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
which matches the checkpoint verified by the implementation.
The implementation first computes \(\log\varphi\) once and reuses it everywhere. It estimates the peak position by \(n/\log\varphi\), inspects a very small neighborhood to choose the best integer index, and then expands outward until the 120-log-unit cutoff is reached on both sides.
Next it accumulates the rescaled sum
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
The C++ version can split this interval into chunks and sum them in parallel. The Python and Java versions follow the same mathematics in a sequential pass, with Python using high-precision decimal logarithms and exponentials and Java using floating-point arithmetic. All three then take the logarithm of the scaled total, divide by \(\log\varphi\), apply the guarded ceiling, and add \(3\).
If the retained window has width
$$W=R-L+1,$$
then building the window and summing its terms both cost \(O(W)\) time. The extra memory is \(O(1)\) in the sequential versions and \(O(T)\) partial accumulators in the threaded C++ version, where \(T\) is the number of worker threads.
Near the maximum, a quadratic expansion gives
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
so a fixed drop threshold produces a window whose width is on the order of \(\sqrt{n}\). In practice the retained band is therefore far smaller than the peak index itself.
Bei Problem 664 wird die gesuchte Größe aus dem unendlichen Spiel nicht durch direkte Simulation der Spielzustände bestimmt. Die C++-, Python- und Java-Implementierungen verwenden stattdessen eine äquivalente geschlossene Darstellung mit dem goldenen Schnitt
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
Ist diese Reihe bekannt, dann lautet die gesuchte Antwort
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
Die Schwierigkeit ist vor allem numerisch. Für große \(n\) werden die dominanten Reihenterme riesig, während die entfernten Ausläufer praktisch nichts mehr beitragen. Deshalb arbeitet die Lösung vollständig im Logarithmus-Bereich und summiert nur das schmale Fenster um das Maximum.
Setze
$$a_d=\frac{d^n}{\varphi^d}.$$
Statt \(a_d\) direkt zu bilden, betrachten wir
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
Damit wird die gesamte Reihe zu
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
So vermeidet man Überläufe und reduziert das Problem auf die stabile Berechnung eines Logarithmus einer Summe.
Die Reihensumme wird von den Termen nahe dem Maximum von \(L(d)\) getragen. Behandle den Index zunächst als reelle Variable \(x\) und definiere
$$f(x)=n\log x-x\log\varphi.$$
Dann gilt
$$f'(x)=\frac{n}{x}-\log\varphi,$$
also liegt der stationäre Punkt bei
$$x_*=\frac{n}{\log\varphi}.$$
Wegen
$$f''(x)=-\frac{n}{x^2}\lt 0$$
ist das tatsächlich ein strenges Maximum. Der beste ganzzahlige Index liegt daher sehr nahe bei \(n/\log\varphi\), weshalb eine kleine lokale Suche genügt.
Ist der Spitzenwert \(L_{\max}\) bekannt, werden weit entfernte Terme numerisch bedeutungslos. Die Implementierungen erweitern das Intervall nach links und rechts, bis
$$L_{\max}-L(d)\gt 120$$
gilt. Dann ist der betreffende Term um den Faktor \(e^{-120}\) kleiner als der Spitzenterm, und der restliche Schwanz fällt wegen der konkaven Form weiter ab. So erhält man ein endliches Fenster
$$d\in[L,R]$$
mit allen numerisch relevanten Beiträgen.
Eine direkte Summe der Werte \(e^{L(d)}\) wäre in der Nähe des Maximums weiterhin instabil. Daher nutzt man
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
Jetzt sind alle Exponenten \(L(d)-L_{\max}\) nichtpositiv. Der größte skalierte Term ist also genau \(1\), alle übrigen liegen in \((0,1]\). Das ist der zentrale numerische Trick der drei Implementierungen.
Nach der Berechnung von \(\log A_n\) wird die Basis von \(e\) auf \(\varphi\) umgerechnet:
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
Damit folgt
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
Vor dem Aufrunden wird ein winziges negatives Epsilon abgezogen. Das verhindert, dass Rundungsfehler einen eigentlich ganzzahligen Wert knapp über die nächste Grenze schieben.
Für \(n=2\) lässt sich die Reihe exakt auswerten. Setze
$$x=\frac{1}{\varphi}.$$
Dann ist
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
Mit der klassischen Erzeugendenfunktion gilt
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
Da \(x=1/\varphi\), haben wir \(x+1=\varphi\) und \(1-x=1/\varphi^2\). Also
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
Folglich
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
genau der Kontrollwert aus der Implementierung.
Die Implementierung berechnet zuerst \(\log\varphi\) einmalig und verwendet diesen Wert anschließend durchgehend. Danach wird die Lage des Maximums durch \(n/\log\varphi\) abgeschätzt, in einer sehr kleinen Umgebung zum besten ganzzahligen Index verfeinert und anschließend so lange nach links und rechts erweitert, bis auf beiden Seiten die 120-Log-Einheiten-Grenze erreicht ist.
Danach summiert der Code die skalierten Terme
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
Die C++-Version kann dieses Fenster in Teilstücke zerlegen und parallel summieren. Die Python- und Java-Versionen verwenden dieselbe Mathematik sequentiell; Python nutzt dabei hochpräzise Dezimallogarithmen und -exponentialfunktionen, Java gewöhnliche Gleitkommaarithmetik. Anschließend wird der Logarithmus der skalierten Summe genommen, durch \(\log\varphi\) geteilt, mit geschützter Ceiling-Funktion aufgerundet und \(3\) addiert.
Hat das beibehaltene Fenster die Breite
$$W=R-L+1,$$
dann kosten sowohl der Fensteraufbau als auch die Summation \(O(W)\) Zeit. Der Zusatzspeicher beträgt \(O(1)\) in den sequentiellen Varianten und \(O(T)\) partielle Summen in der parallelen C++-Variante mit \(T\) Threads.
In der Nähe des Maximums liefert eine quadratische Entwicklung
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
sodass eine feste Abfallschwelle zu einer Fensterbreite der Größenordnung \(O(\sqrt{n})\) führt. Praktisch ist das Fenster daher deutlich kleiner als der Index der Spitze selbst.
Problem 664 için aranan büyüklük, oyun durumlarını tek tek simüle ederek hesaplanmıyor. C++, Python ve Java implementasyonlarının ortak kullandığı eşdeğer kapalı form, altın oran üzerinden şu seriye dayanıyor:
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
Bu seri hesaplandıktan sonra istenen cevap
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil$$
oluyor. Zorluk daha çok sayısal kararlılıkta yatıyor. Büyük \(n\) değerlerinde baskın terimler çok büyürken, kuyruk kısmı ihmal edilebilir hale geliyor. Bu nedenle çözüm, tamamen logaritmik alanda çalışıp toplamın yalnızca gerçekten katkı yapan dar tepe bölgesini tutuyor.
Şunu tanımlayalım:
$$a_d=\frac{d^n}{\varphi^d}.$$
\(a_d\) değerlerini doğrudan üretmek yerine logaritmasını alırız:
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
Böylece seri
$$A_n=\sum_{d\ge 1} e^{L(d)}$$
şekline dönüşür. Bu dönüşüm, baskın terimlerde taşmayı engeller ve problemi kararlı bir log-toplam hesaplamasına çevirir.
Toplamın ana katkısı, \(L(d)\) fonksiyonunun maksimum olduğu civardan gelir. İndeksi önce reel değişken \(x\) gibi düşünelim ve
$$f(x)=n\log x-x\log\varphi$$
tanımını yapalım. Türev
$$f'(x)=\frac{n}{x}-\log\varphi$$
olduğuna göre durağan nokta
$$x_*=\frac{n}{\log\varphi}$$
eşitliğiyle bulunur. Ayrıca
$$f''(x)=-\frac{n}{x^2}\lt 0$$
olduğu için bu nokta kesin bir maksimumdur. Dolayısıyla en iyi tam sayı \(d\), \(n/\log\varphi\) değerinin çok yakınında bulunur; kodun küçük bir yerel tarama yapması bunun içindir.
Tepe değeri \(L_{\max}\) bulunduktan sonra, ondan çok uzak terimler sayısal olarak önemsizdir. Implementasyonlar tepe noktasından sola ve sağa doğru açılarak
$$L_{\max}-L(d)\gt 120$$
koşulu sağlanana kadar ilerler. Bu noktada ilgili terim, tepe teriminden \(e^{-120}\) kat daha küçüktür ve kuyruk kısmı o tarafta zaten azalmaya devam eder. Böylece
$$d\in[L,R]$$
şeklinde, tüm anlamlı katkıları içeren pratik bir sonlu pencere elde edilir.
\(e^{L(d)}\) terimlerini doğrudan toplamak yine kararsız olurdu. Bunun yerine
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right)$$
yazılır. Artık tüm üsler \(L(d)-L_{\max}\le 0\) olduğundan en büyük ölçeklenmiş terim tam olarak \(1\), diğerleri ise \((0,1]\) aralığındadır. Üç implementasyonun ortak sayısal numarası budur.
\(\log A_n\) hesaplandıktan sonra taban dönüşümü yapılır:
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
Sonra cevap
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil$$
olur. Tavan alma öncesinde çok küçük bir negatif epsilon çıkarılır. Bunun amacı, gerçek değer tam sayıya çok yakın olduğunda kayan nokta hatasının sonucu yanlışlıkla bir üst tam sayıya itmesini önlemektir.
\(n=2\) için seri tam olarak kontrol edilebilir. Şunu alalım:
$$x=\frac{1}{\varphi}.$$
O zaman
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
Klasik üreteç fonksiyonu özdeşliği
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}$$
şeklindedir. \(x=1/\varphi\) olduğundan \(x+1=\varphi\) ve \(1-x=1/\varphi^2\) elde edilir. Böylece
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
Sonuç olarak
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
ve bu değer implementasyondaki kontrol noktasıyla birebir örtüşür.
Implementasyon önce \(\log\varphi\) değerini bir kez hesaplar ve her yerde onu kullanır. Ardından \(n/\log\varphi\) ile tepe konumunu tahmin eder, çok dar bir komşulukta en iyi tam sayı indeksi seçer ve her iki tarafta da 120 log-birimlik kesme eşiğine ulaşana kadar pencereyi genişletir.
Daha sonra ölçeklenmiş toplam
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}$$
biriktirilir. C++ sürümü bu aralığı parçalara ayırıp paralel toplayabilir. Python ve Java sürümleri aynı matematiği sıralı biçimde uygular; Python yüksek hassasiyetli ondalık logaritma ve üstel fonksiyonlar kullanırken Java kayan nokta aritmetiğiyle ilerler. Son aşamada ölçeklenmiş toplamın logaritması alınır, \(\log\varphi\)'ye bölünür, korumalı tavan uygulanır ve \(3\) eklenir.
Tutulan pencerenin genişliği
$$W=R-L+1$$
olsun. Hem pencereyi kurmak hem de bu pencere üzerindeki toplamı almak \(O(W)\) zaman ister. Ek bellek sıralı sürümlerde \(O(1)\), iş parçacıklı C++ sürümünde ise \(T\) iş parçacığı için \(O(T)\) kısmi toplamdır.
Maksimum civarında kuadratik yaklaşım
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2$$
şeklindedir. Bu da sabit bir düşüş eşiğinin yaklaşık \(O(\sqrt{n})\) genişliğinde bir pencere verdiğini gösterir. Pratikte bu bant, tepe indeksinin kendisinden çok daha dardır.
En el Problema 664, la cantidad pedida no se obtiene simulando directamente las posiciones del juego infinito. Las implementaciones en C++, Python y Java usan en cambio una forma cerrada equivalente basada en la razón áurea
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
Una vez evaluada esa serie, la respuesta requerida es
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
La dificultad es sobre todo numérica. Cuando \(n\) es grande, los términos dominantes de la serie son gigantescos, mientras que las colas son despreciables. Por eso la solución trabaja por completo en el dominio logarítmico y conserva solo la estrecha región alrededor del máximo.
Definimos
$$a_d=\frac{d^n}{\varphi^d}.$$
En vez de construir \(a_d\) directamente, tomamos su logaritmo:
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
Así la serie completa pasa a ser
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
Este cambio evita desbordamientos y transforma el problema en el cálculo estable del logaritmo de una suma.
La mayor parte de la masa de la serie está cerca del máximo de \(L(d)\). Si tratamos el índice como variable real \(x\), definimos
$$f(x)=n\log x-x\log\varphi.$$
Entonces
$$f'(x)=\frac{n}{x}-\log\varphi,$$
de modo que el punto estacionario está en
$$x_*=\frac{n}{\log\varphi}.$$
Además,
$$f''(x)=-\frac{n}{x^2}\lt 0,$$
así que ese punto es un máximo estricto. Por ello, el mejor índice entero queda muy cerca de \(n/\log\varphi\), y basta una búsqueda local muy pequeña para encontrar el verdadero pico discreto.
Conocido el valor máximo \(L_{\max}\), los términos lejanos dejan de importar numéricamente. Las implementaciones expanden a izquierda y derecha hasta que
$$L_{\max}-L(d)\gt 120.$$
En ese momento el término es menor que el pico por un factor \(e^{-120}\), y la cola restante sigue decayendo porque el perfil ya está descendiendo en ese lado. Esto produce una ventana práctica
$$d\in[L,R]$$
que contiene toda la contribución relevante.
Sumar directamente \(e^{L(d)}\) sigue siendo inseguro cerca del máximo. La forma estable es
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
Ahora todos los exponentes \(L(d)-L_{\max}\) son no positivos, así que el término reescalado más grande vale exactamente \(1\) y todos los demás quedan en \((0,1]\). Este es el truco numérico central usado por las tres implementaciones.
Una vez calculado \(\log A_n\), hacemos el cambio de base de \(e\) a \(\varphi\):
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
La respuesta buscada es
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
Antes de aplicar el techo se resta un epsilon negativo diminuto. Sirve para evitar que un error de redondeo empuje un valor esencialmente entero al siguiente entero por arriba.
Para \(n=2\), la serie se puede verificar exactamente. Tomemos
$$x=\frac{1}{\varphi}.$$
Entonces
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
La identidad clásica de funciones generadoras dice
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
Como \(x=1/\varphi\), tenemos \(x+1=\varphi\) y \(1-x=1/\varphi^2\). Por tanto
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
Así,
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
que coincide con el punto de control verificado por la implementación.
La implementación calcula primero \(\log\varphi\) una sola vez y reutiliza ese valor. Después estima la posición del pico con \(n/\log\varphi\), examina un vecindario muy pequeño para escoger el mejor índice entero y amplía la ventana hasta alcanzar el corte de 120 unidades logarítmicas a ambos lados.
Luego acumula la suma reescalada
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
La versión en C++ puede dividir ese intervalo en bloques y sumarlos en paralelo. Las versiones en Python y Java siguen la misma matemática de forma secuencial; Python usa logaritmos y exponenciales decimales de alta precisión, mientras que Java usa aritmética de coma flotante. Finalmente se toma el logaritmo del total escalado, se divide por \(\log\varphi\), se aplica el techo protegido y se suma \(3\).
Si la ventana retenida tiene anchura
$$W=R-L+1,$$
entonces tanto la construcción de la ventana como la suma cuestan \(O(W)\) tiempo. La memoria extra es \(O(1)\) en las versiones secuenciales y \(O(T)\) acumuladores parciales en la versión paralela de C++, donde \(T\) es el número de hilos.
Cerca del máximo, una expansión cuadrática da
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
de modo que un umbral fijo de caída produce una ventana de orden \(O(\sqrt{n})\). En la práctica, la banda retenida es mucho más pequeña que la posición del pico.
在第 664 题中，最终要求的量并不是通过直接模拟这个“无限游戏”的局面来得到的。C++、Python 和 Java 三个实现都使用了同一个等价闭式，它建立在黄金比例上：
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
只要把这个级数算出来，答案就变成
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
真正的难点主要是数值问题。对于很大的 \(n\)，峰值附近的项会大得惊人，而远离峰值的尾部又几乎没有贡献。于是程序不去直接处理原始项，而是完全转到对数域中，只保留对总和有实质影响的那一小段峰值窗口。
定义单项
$$a_d=\frac{d^n}{\varphi^d}.$$
如果直接构造 \(a_d\)，在峰值附近很容易出现数值溢出。因此先写它的对数：
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
这样原来的无穷级数可以写成
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
这个改写把“巨大数字求和”的问题，转化成“稳定地求一个对数和”的问题。
级数的主要质量集中在 \(L(d)\) 取得最大值的附近。先把离散指标 \(d\) 视为实变量 \(x\)，考虑
$$f(x)=n\log x-x\log\varphi.$$
它的导数是
$$f'(x)=\frac{n}{x}-\log\varphi,$$
所以驻点满足
$$x_*=\frac{n}{\log\varphi}.$$
又因为
$$f''(x)=-\frac{n}{x^2}\lt 0,$$
这个驻点一定是严格最大值。也就是说，真正的离散峰值一定落在 \(n/\log\varphi\) 附近，只需要在这个估计点附近做一个很小的整数扫描，就能找到最优的峰值项。
一旦峰值 \(L_{\max}\) 找到，离它很远的项就没有数值意义了。实现方式是从峰值位置向左右扩展，直到满足
$$L_{\max}-L(d)\gt 120.$$
这意味着该项至少比峰值项小 \(e^{-120}\) 倍，而且由于曲线在这一侧已经持续下降，后面的尾项只会更小。因此可以把真正需要计算的部分限制在有限区间
$$d\in[L,R]$$
内，而不必对整个无穷级数逐项求和。
即使已经截断到有限窗口，如果直接去加 \(e^{L(d)}\)，峰值附近仍然可能非常大。标准的稳定写法是
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
这样一来，所有指数 \(L(d)-L_{\max}\) 都不大于 \(0\)。最大的那一项恰好变成 \(1\)，其余项全部落在 \((0,1]\) 之间。三个实现真正执行的就是这个重标定后的求和。
求得 \(\log A_n\) 以后，只需把底从 \(e\) 换成 \(\varphi\)：
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
于是最终答案为
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
在做上取整之前，代码会先减去一个极小的负 epsilon。这样可以避免“理论上刚好是整数，但浮点结果略微偏大”时被错误地推到下一个整数。
当 \(n=2\) 时，这个级数可以精确化简。令
$$x=\frac{1}{\varphi}.$$
则
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
经典生成函数恒等式告诉我们
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
而 \(x=1/\varphi\) 时，有 \(x+1=\varphi\)，同时 \(1-x=1/\varphi^2\)。代入后得到
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
因此
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
这与实现中验证的小检查点完全一致。
实现首先只计算一次 \(\log\varphi\)，随后重复使用。接着用 \(n/\log\varphi\) 作为峰值位置的初始估计，在附近很小的一段整数范围内挑出真正最优的峰值索引，然后向左右扩展窗口，直到两边都达到“比峰值低 120 个对数单位”的截断标准。
随后程序累加重标定后的和
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
C++ 实现可以把这个区间分块后并行累加。Python 和 Java 实现则按相同的数学步骤顺序执行；其中 Python 使用高精度十进制对数与指数，Java 使用浮点运算。最后，再取这个缩放后总和的对数，除以 \(\log\varphi\)，做带保护的上取整，并加上 \(3\)。
若保留下来的窗口宽度为
$$W=R-L+1,$$
那么构造窗口和求和都需要 \(O(W)\) 时间。顺序版本的额外空间是 \(O(1)\)，并行的 C++ 版本则需要 \(O(T)\) 个部分累加器，其中 \(T\) 是工作线程数。
在峰值附近，对 \(f(x)\) 做二次展开可得
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
这说明在固定的截断阈值下，窗口宽度大致只有 \(O(\sqrt{n})\) 量级。换句话说，真正需要处理的区间远小于峰值索引本身。
В задаче 664 искомая величина не вычисляется прямой симуляцией состояний бесконечной игры. Реализации на C++, Python и Java используют эквивалентную замкнутую форму через золотое сечение:
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
После вычисления этого ряда ответ имеет вид
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
Основная трудность здесь численная. При больших \(n\) ведущие члены ряда становятся колоссальными, а дальние хвосты практически ничего не добавляют. Поэтому решение полностью переходит в логарифмическую область и суммирует только узкое окно вокруг максимума.
Положим
$$a_d=\frac{d^n}{\varphi^d}.$$
Вместо прямого вычисления \(a_d\) рассмотрим его логарифм:
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
Тогда весь ряд можно записать как
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
Такой переход устраняет риск переполнения и сводит задачу к устойчивому вычислению логарифма суммы.
Основной вклад в ряд дают члены рядом с максимумом функции \(L(d)\). Если временно считать индекс вещественной переменной \(x\), получаем
$$f(x)=n\log x-x\log\varphi.$$
Тогда
$$f'(x)=\frac{n}{x}-\log\varphi,$$
и стационарная точка равна
$$x_*=\frac{n}{\log\varphi}.$$
Поскольку
$$f''(x)=-\frac{n}{x^2}\lt 0,$$
это строгий максимум. Следовательно, лучший целый индекс лежит очень близко к \(n/\log\varphi\), и достаточно короткого локального просмотра вокруг этой оценки.
Когда найдено значение вершины \(L_{\max}\), далёкие члены становятся численно несущественными. Реализации расширяют окно влево и вправо, пока не выполнится условие
$$L_{\max}-L(d)\gt 120.$$
В этот момент соответствующий член меньше пикового в \(e^{-120}\) раз, а оставшийся хвост убывает ещё сильнее, потому что профиль уже идёт вниз. Тем самым бесконечная сумма заменяется конечным диапазоном
$$d\in[L,R]$$
со всеми численно значимыми вкладами.
Даже в конечном окне напрямую складывать \(e^{L(d)}\) опасно. Устойчивая формула имеет вид
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
Теперь все показатели \(L(d)-L_{\max}\) не положительны, так что самый большой перенормированный член равен ровно \(1\), а остальные лежат в интервале \((0,1]\). Это и есть главный численный приём всех трёх реализаций.
После вычисления \(\log A_n\) остаётся перейти от натурального логарифма к основанию \(\varphi\):
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
Тогда ответ равен
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
Перед применением потолка вычитается крошечный отрицательный epsilon. Это защищает от ситуации, когда истинное значение целое, а погрешность округления делает его едва заметно больше.
Для \(n=2\) ряд можно посчитать точно. Возьмём
$$x=\frac{1}{\varphi}.$$
Тогда
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
Классическая формула производящей функции даёт
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
Так как \(x=1/\varphi\), имеем \(x+1=\varphi\) и \(1-x=1/\varphi^2\). Следовательно,
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
Поэтому
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
что совпадает с контрольным значением реализации.
Сначала реализация один раз вычисляет \(\log\varphi\) и дальше использует его повсюду. Затем по формуле \(n/\log\varphi\) оценивается положение пика, в очень маленькой окрестности выбирается лучший целый индекс, и окно расширяется в обе стороны до достижения порога в 120 логарифмических единиц.
После этого суммируется перенормированный ряд
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
Версия на C++ может разбивать этот диапазон на блоки и считать их параллельно. Версии на Python и Java используют ту же математику последовательно; Python опирается на высокоточную десятичную арифметику для логарифмов и экспонент, а Java работает с числами с плавающей точкой. В конце берётся логарифм полученной суммы, выполняется деление на \(\log\varphi\), затем защищённое округление вверх и прибавление \(3\).
Если ширина сохранённого окна равна
$$W=R-L+1,$$
то и построение окна, и суммирование требуют \(O(W)\) времени. Дополнительная память равна \(O(1)\) в последовательных версиях и \(O(T)\) частичных сумм в параллельной версии на C++, где \(T\) обозначает число потоков.
Вблизи максимума квадратичное приближение даёт
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
поэтому фиксированный порог отсечения приводит к ширине окна порядка \(O(\sqrt{n})\). На практике это означает, что рассматриваемый диапазон намного уже, чем сама позиция пика.
في المسألة 664 لا تُحسب الكمية المطلوبة من خلال محاكاة حالات اللعبة اللانهائية مباشرة. تعتمد تطبيقات C++ وPython وJava على صيغة مكافئة مغلقة مبنية على النسبة الذهبية:
$$\varphi=\frac{1+\sqrt5}{2}, \qquad A_n=\sum_{d=1}^{\infty}\frac{d^n}{\varphi^d}.$$
وبعد حساب هذه السلسلة تصبح الإجابة المطلوبة
$$F(n)=3+\left\lceil \log_{\varphi}(A_n)\right\rceil.$$
الصعوبة هنا عددية بالدرجة الأولى. عندما تكون \(n\) كبيرة تصبح الحدود القريبة من الذروة هائلة جداً، بينما تصبح الذيول البعيدة شبه معدومة الأثر. لذلك يعمل الحل كله في المجال اللوغاريتمي، ويحتفظ فقط بالنافذة الضيقة المحيطة بالحدود ذات الأثر الحقيقي في المجموع.
لنعرّف
$$a_d=\frac{d^n}{\varphi^d}.$$
بدلاً من حساب \(a_d\) مباشرة نأخذ لوغاريتمه:
$$L(d)=\log a_d=n\log d-d\log\varphi.$$
وعندئذ تصبح السلسلة اللانهائية
$$A_n=\sum_{d\ge 1} e^{L(d)}.$$
هذا التحويل يمنع فيضان الأعداد عند الحدود الكبرى، ويحوّل المسألة إلى حساب مستقر للوغاريتم الخاص بمجموع.
أغلب كتلة السلسلة تتمركز قرب القيمة التي تجعل \(L(d)\) أعظمياً. إذا اعتبرنا الفهرس متغيراً حقيقياً \(x\)، فنعرّف
$$f(x)=n\log x-x\log\varphi.$$
مشتقته هي
$$f'(x)=\frac{n}{x}-\log\varphi,$$
ومنها تكون النقطة الحرجة عند
$$x_*=\frac{n}{\log\varphi}.$$
ولأن
$$f''(x)=-\frac{n}{x^2}\lt 0,$$
فإن هذه النقطة تمثل قيمة عظمى حقيقية. لذلك يقع أفضل فهرس صحيح قريباً جداً من \(n/\log\varphi\)، ولهذا يكفي مسح محلي صغير حول هذا التقدير.
بعد معرفة قيمة الذروة \(L_{\max}\)، تصبح الحدود البعيدة عنها غير مهمة عددياً. تقوم التطبيقات بتوسيع النافذة يميناً ويساراً حتى يتحقق
$$L_{\max}-L(d)\gt 120.$$
عندها يكون هذا الحد أصغر من حد الذروة بعامل \(e^{-120}\)، كما أن بقية الذيل تستمر في التناقص لأن المنحنى صار هابطاً في تلك الجهة. وهكذا نحصل على نافذة عملية منتهية
$$d\in[L,R]$$
تحتوي كل المساهمات العددية المهمة.
حتى بعد القطع إلى نافذة منتهية، يبقى جمع \(e^{L(d)}\) مباشرة غير آمن قرب الذروة. الصيغة المستقرة هي
$$\log A_n=L_{\max}+\log\left(\sum_{d=L}^{R} e^{L(d)-L_{\max}}\right).$$
الآن تصبح جميع الأسس \(L(d)-L_{\max}\) غير موجبة، فيكون أكبر حد بعد إعادة القياس مساوياً تماماً لـ \(1\)، وتقع بقية الحدود في المجال \((0,1]\). هذه هي الحيلة العددية الأساسية المشتركة بين التطبيقات الثلاثة.
بعد حساب \(\log A_n\)، نغيّر الأساس من \(e\) إلى \(\varphi\):
$$\log_{\varphi}(A_n)=\frac{\log A_n}{\log\varphi}.$$
ومن ثم يكون الجواب
$$F(n)=3+\left\lceil \frac{\log A_n}{\log\varphi}\right\rceil.$$
قبل تطبيق دالة السقف يُطرح مقدار صغير جداً سالب من القيمة. الهدف من ذلك منع أخطاء التقريب العائم من دفع قيمة يفترض أنها عدد صحيح إلى العدد الصحيح التالي الأعلى.
عندما \(n=2\) يمكن التحقق من السلسلة بدقة تامة. لنضع
$$x=\frac{1}{\varphi}.$$
فنحصل على
$$A_2=\sum_{d=1}^{\infty} d^2 x^d.$$
وتعطي هوية الدوال المولدة الكلاسيكية
$$\sum_{d=1}^{\infty} d^2 x^d=\frac{x(x+1)}{(1-x)^3}.$$
وبما أن \(x=1/\varphi\)، فإن \(x+1=\varphi\) و\(1-x=1/\varphi^2\). بالتعويض ينتج
$$A_2=\frac{(1/\varphi)\varphi}{(1/\varphi^2)^3}=\varphi^6.$$
لذلك
$$F(2)=3+\left\lceil \log_{\varphi}(\varphi^6)\right\rceil=3+6=9,$$
وهو تماماً نفس مقدار التحقق الذي تستخدمه التطبيقات.
تبدأ الشيفرة بحساب \(\log\varphi\) مرة واحدة ثم تعيد استخدامه في جميع الخطوات. بعد ذلك تقدّر موضع الذروة بواسطة \(n/\log\varphi\)، وتفحص جواراً صغيراً جداً لاختيار أفضل فهرس صحيح، ثم توسع النافذة حتى تصل على الجانبين إلى حد القطع البالغ 120 وحدة لوغاريتمية.
بعدها تجمع الشيفرة المجموع المعاد قياسه
$$\sum_{d=L}^{R} e^{L(d)-L_{\max}}.$$
يمكن لنسخة C++ تقسيم هذا المجال إلى أجزاء وجمعها بالتوازي. أما نسختا Python وJava فتتبِعان الرياضيات نفسها على نحو تسلسلي؛ تستخدم Python لوغاريتمات وأسيات عشرية عالية الدقة، بينما تستخدم Java الحساب العشري العائم. وفي النهاية يُؤخذ لوغاريتم المجموع المعاد قياسه، ثم يُقسَم على \(\log\varphi\)، ثم يُطبَّق السقف المحمي وتُضاف \(3\).
إذا كان عرض النافذة المحتفظ بها هو
$$W=R-L+1,$$
فإن بناء النافذة وجمع حدودها يكلفان زمناً مقداره \(O(W)\). أما الذاكرة الإضافية فهي \(O(1)\) في النسخ التسلسلية، و\(O(T)\) مجاميع جزئية في نسخة C++ المتوازية حيث \(T\) هو عدد الخيوط العاملة.
وقرب الذروة يعطي التقريب التربيعي
$$f(x)\approx f(x_*)-\frac{(\log\varphi)^2}{2n}(x-x_*)^2,$$
مما يعني أن حد القطع الثابت يولد نافذة عرضها من رتبة \(O(\sqrt{n})\). عملياً تكون هذه الحزمة أضيق بكثير من موضع الذروة نفسه.