Detailed mathematical approach

Problem Summary

For each nonnegative integer \(k\), define

$f_n(k)=e^{k/n}-1,\qquad k\in \mathbb{Z}_{\ge 0}.$

The task is to choose a nondecreasing quadruple

$0\le a\le b\le c\le d$

so that

$\left|f_n(a)+f_n(b)+f_n(c)+f_n(d)-\pi\right|$

is as small as possible. Once such a quadruple is found, the required output is

$g(n)=a^2+b^2+c^2+d^2.$

A direct four-loop search is far too expensive for the target input, so the implementation turns the problem into a structured closest-sum search on pair sums.

Mathematical Approach

The C++, Python, and Java implementations all use the same numerical strategy. They work with a small tolerance

$\delta=10^{-3}$

to build candidate regions around \(\pi\), then perform an exact closest search inside those regions.

Step 1: Build a Finite Working Range

The sequence \(f_n(k)=e^{k/n}-1\) is strictly increasing, so larger indices always produce larger terms. The implementation therefore samples only

$0\le k\le B,\qquad B=\left\lfloor n\log(\pi+0.1)\right\rfloor.$

This gives a finite array of candidate values in the relevant numerical window for the search. For the checkpoint \(n=200\), this bound is

$B=\left\lfloor 200\log(\pi+0.1)\right\rfloor=235.$

The algorithm does not search arbitrary four-tuples beyond that working range; instead it relies on the monotonic growth of \(f_n\) together with the pruning rules below.

Step 2: Replace a 4-Sum Search by a 2-Sum Search

If we split the quadruple into two ordered pairs, then we may write

$s_{a,b}=f_n(a)+f_n(b),\qquad t_{c,d}=f_n(c)+f_n(d).$

The original objective becomes

$\left|s_{a,b}+t_{c,d}-\pi\right| \to \min.$

This is the standard meet-in-the-middle idea: instead of scanning all quadruples, build two collections of pair sums and then search for one value from each collection whose total is closest to \(\pi\).

Conceptually, one collection stores pair sums from the lower side of the target and the other stores pair sums from the upper side. After sorting both collections, the four-dimensional search collapses to a one-pass closest-pair sweep.

Step 3: Prune the Lower-Side Pair Sums

For the smaller pair sums the implementation enumerates pairs with \(a\le b\) and keeps only combinations that can still belong to a quadruple near \(\pi\). Two monotone inequalities drive the pruning:

$4f_n(a)\le \pi+\delta,$

$f_n(a)+3f_n(b)\le \pi+\delta.$

The first inequality says that if even the quadruple \((a,a,a,a)\) already exceeds the admissible band, then every larger \(a\) is hopeless and the outer loop can stop.

The second inequality says that once \(a\) is fixed, if replacing the two missing entries by the largest currently allowed term \(f_n(b)\) already pushes the total above \(\pi+\delta\), then every larger \(b\) is also impossible. Because \(f_n\) is increasing, this justifies an early break in the inner loop.

Step 4: Prune the Upper-Side Pair Sums

The second collection is generated from the top down, using pairs with \(c\le d\). Here the implementation keeps only sums that lie in the opposite feasible band:

$f_n(c)+f_n(d)\le \pi+\delta,$

$4f_n(d)\ge \pi-\delta,$

$f_n(d)+3f_n(c)\ge \pi-\delta.$

The middle inequality means that if even four copies of the current largest term stay below \(\pi-\delta\), then every smaller \(d\) will also stay too small, so the downward scan may stop.

The last inequality handles the inner loop: once \(d\) is fixed, if even the most optimistic completion with three copies of \(f_n(c)\) cannot reach the lower edge of the band, then decreasing \(c\) further only makes things worse, so the loop can break.

These inequalities do not solve the problem by themselves, but they dramatically shrink the lists before sorting.

Step 5: Search the Two Sorted Lists for the Closest Total

After sorting both pair-sum lists in ascending order, the implementation performs a monotone sweep. One pointer moves through the lower list from left to right, while the other starts at the right end of the upper list and moves only leftward.

For each lower-side value \(x\), the algorithm adjusts the upper pointer until the sum crosses \(\pi\). At that crossing, only two neighboring candidates can matter: the last one below the target and the first one above it. Comparing those two possibilities is enough to update the best error

$\left|x+y-\pi\right|.$

Because neither pointer ever reverses direction, this stage is linear once the sorting is finished.

Step 6: Recover the Actual Indices and Compute \(g(n)\)

The pair-sum lists store only floating-point sums, not the contributing index pairs. That keeps memory usage manageable, but it means the indices must be reconstructed after the best two sums are found.

To do that, the implementation runs the same closest-two-sum procedure again on the base value array \(\{f_n(0),f_n(1),\dots,f_n(B)\}\): once with target equal to the selected lower pair sum, and once with target equal to the selected upper pair sum. This yields one ordered pair for each chosen sum.

The four recovered indices are then sorted, and the final quantity

$g(n)=a^2+b^2+c^2+d^2$

is computed directly.

Worked Example: The Checkpoint \(n=200\)

For \(n=200\), the implementation uses the bound \(B=235\). The closest quadruple found by the algorithm is

$\left(a,b,c,d\right)=\left(6,75,89,226\right).$

The corresponding function values are approximately

$f_{200}(6)\approx 0.03045453395,\qquad f_{200}(75)\approx 0.45499141462,$

$f_{200}(89)\approx 0.56049019583,\qquad f_{200}(226)\approx 2.09565650012.$

Grouping them into two pairs gives

$f_{200}(6)+f_{200}(75)\approx 0.48544594857,$

$f_{200}(89)+f_{200}(226)\approx 2.65614669596.$

Their total is

$0.48544594857+2.65614669596\approx 3.14159264453,$

which differs from \(\pi\) by about

$9.06\times 10^{-9}.$

Therefore

$g(200)=6^2+75^2+89^2+226^2=64658,$

matching the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline.

First they precompute the monotone array \(f_n(0),f_n(1),\dots,f_n(B)\). Next they build two lists of pair sums: a lower-side list created by increasing indices from the left, and an upper-side list created by decreasing indices from the right. In both cases, monotonicity lets the loops stop early as soon as the pruning inequalities fail.

After sorting the two lists, the implementation performs a closest-sum sweep to find one value from each list whose total is nearest to \(\pi\). Because the lists contain only sums, the code then reconstructs the actual pairs by solving two additional closest-two-sum problems on the original one-dimensional value array. Finally it sorts the four recovered indices and returns the sum of their squares.

The entire method is numerical but tightly controlled: the same tolerance band is used while building candidate sums and while reconstructing the chosen pairs, and the checkpoint \(g(200)=64658\) verifies that the three language versions agree.

Complexity Analysis

Let

$B=\left\lfloor n\log(\pi+0.1)\right\rfloor,$

and let \(P_-\) and \(P_+\) be the numbers of retained lower-side and upper-side pair sums. Computing the base array costs \(O(B)\) time and \(O(B)\) memory.

The pair-generation loops have a worst-case \(O(B^2)\) envelope, but the monotone breaks ensure that only the numerically relevant region is materialized. The dominant explicit work after pruning is sorting, which costs

$O(P_-\log P_- + P_+\log P_+).$

The closest-sum sweep is linear in the two list sizes, and the final index reconstruction adds only \(O(B)\) work. Hence the practical memory usage is

$O(B+P_-+P_+),$

and the dominant practical running time is the construction and sorting of the retained pair sums rather than an infeasible \(O(B^4)\) quadruple search.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=461
2. Exponential function: Wikipedia — Exponential function
3. Meet-in-the-middle: Wikipedia — Meet-in-the-middle
4. Two-pointer technique: Wikipedia — Two-pointer technique