Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

Step 1: Rewrite the series in logarithmic form

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.

Step 2: Locate the dominant index

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.

Step 3: Truncate the infinite sum to a finite window

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.

Step 4: Apply the log-sum-exp identity

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.

Step 5: Recover the required integer answer

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.

Worked Example: \(n=2\)

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.

How the Code Works

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\).

Complexity Analysis

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.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=664
2. Golden ratio: Wikipedia — Golden ratio
3. LogSumExp: Wikipedia — LogSumExp
4. Polylogarithm: Wikipedia — Polylogarithm
5. Generating function: Wikipedia — Generating function