Project Euler Problem 438
For an n-tuple of integers t = (a1, dots, an), let (x1, dots, xn) be the solutions of the polynomial equation x^n + a1 x
Solution
Answer: 2046409616809
Let
$$P(x)=x^n+a_1x^{n-1}+\cdots+a_n$$
with integer coefficients, and let its real roots be
$$x_1<x_2<\cdots<x_n, \qquad \lfloor x_i\rfloor=i.$$
So each root lies in the interval
$$i\le x_i < i+1.$$
The key observation is that this condition is equivalent to a very rigid alternating-sign pattern near the integers.
For a tiny positive infinitesimal $\varepsilon>0$,
$$P(1-\varepsilon),P(2-\varepsilon),\dots,P(n+1-\varepsilon)$$
must alternate in sign:
$$(-1)^nP(1-\varepsilon)>0,$$
$$(-1)^{n-1}P(2-\varepsilon)>0,$$
$$\cdots$$
$$P(n+1-\varepsilon)>0.$$
Applying forward differences repeatedly,
$$\Delta P(x)=P(x+1)-P(x),$$
eliminates coefficients one by one. After applying $\Delta^{n-k}$, the inequalities become linear inequalities in $a_k$.
The crucial fact is:
$$(-1)^{k+1-m}\Delta^{,n-k}P(m-\varepsilon)>0 \qquad (m=1,\dots,k+1),$$
and the coefficient of $a_k$ is exactly $(n-k)!$, a nonzero constant. Therefore each stage yields a finite interval of admissible integers for $a_k$.
Using exact lexicographic comparison of the $\varepsilon$-polynomials (rather than floating point), one can recursively enumerate all valid tuples.
A reference implementation verifies the problem’s check:
- for $n=4$, there are exactly $12$ tuples,
- and
$$\sum S(t)=2087.$$
Running the same exact enumeration for $n=7$ gives the required total.
Answer: 7420738134810