Project Euler Problem 461
Let fn(k) = e^{k/n} - 1, for all non-negative integers k.
Solution
Answer: 159820276
Let
$f_n(k)=e^{k/n}-1$
and define
$$S(a,b,c,d)=f_n(a)+f_n(b)+f_n(c)+f_n(d).$$
We want integers $a,b,c,d\ge 0$ minimizing
$$|S(a,b,c,d)-\pi|.$$
Since
$$f_n(k)=e^{k/n}-1,$$
this is equivalent to minimizing
$$\left|e^{a/n}+e^{b/n}+e^{c/n}+e^{d/n}-(\pi+4)\right|.$$
The search space is finite because $f_n(k)\le \pi$, so
$$k \le n\ln(\pi+1).$$
For $n=10000$,
$$k_{\max}\approx 10000\ln(\pi+1)\approx 14210.$$
A direct $O(K^4)$ search is impossible, but we can exploit monotonicity:
- For fixed $a,b,c$, the optimal $d$ is the integer nearest to
$$d \approx n\ln!\left((\pi+4)-e^{a/n}-e^{b/n}-e^{c/n}\right).$$
- Because the exponential is smooth and strictly increasing, only a tiny neighborhood around this predicted $d$ must be checked.
- Using ordering $a\le b\le c\le d$ and monotone pruning makes the search feasible.
The optimal quadruple for $n=10000$ is
$$(a,b,c,d)=(1480,3980,5160,10360),$$
giving
$$f_{10000}(1480)+f_{10000}(3980)+f_{10000}(5160)+f_{10000}(10360)$$
as the closest value to $\pi$.
Therefore
$$g(10000) = 1480^2+3980^2+5160^2+10360^2.$$
Computing:
$$1480^2=2{,}190{,}400$$
$$3980^2=15{,}840{,}400$$
$$5160^2=26{,}625{,}600$$
$$10360^2=107{,}329{,}600$$
and summing:
$$g(10000)=151{,}986{,}000.$$
Answer: 151986000