Project Euler Problem 438 – Integer Part of Polynomial Equation - Solutions

Table of Contents

Test Data
Polynomials for n=4
One of the Polynomials for n=7

Spoiler Alert! This blog entry contains content that might help you solve problem 438 of Project Euler. Please don’t read any further if you have yet to attempt to solve the problem on your own. The information is intended for those who failed to solve the problem and are looking for hints.

Test Data

Polynomials for n=4

Those are the 12 polynomials for n =4 mentioned in the problem statement:

$$ \begin{align} x^4 -12x^3+ 50x^2 -84x^1+ 46 \\ x^4 -12x^3+ 50x^2 -84x^1+ 47\\ x^4 -12x^3+ 51x^2 -91x^1+ 57\\ x^4 -12x^3+ 51x^2 -91x^1+ 58\\ x^4 -12x^3+ 51x^2 -90x^1+ 55\\ x^4 -11x^3+ 42x^2 -66x^1+ 36\\ x^4 -11x^3+ 42x^2 -65x^1+ 33\\ x^4 -11x^3+ 42x^2 -65x^1+ 34\\ x^4 -11x^3+ 43x^2 -71x^1+ 42\\ x^4 -11x^3+ 43x^2 -70x^1+ 39\\ x^4 -11x^3+ 43x^2 -70x^1+ 40\\ x^4 -10x^3+ 35x^2 -50x^1+ 24 \end{align} $$

One of the Polynomials for n=7

$$ \begin{equation} x^7 -30x^6 + 371x^5 -2449x^4 + 9307x^3 -20334x^2 + 23617x -11236 \end{equation} $$

Archived Comments

Note: I removed the Disqus integration in an effort to cut down on bloat. The following comments were retrieved with the export functionality of Disqus. If you have comments, please reach out to me by Twitter or email.

nobody Dec 21, 2014 01:39:29 UTC

There is no useful hint here. A dumb straighforward brute-force search allow to find the twelve polynomials.
But the same dumb approach isn't enough to solve this problem.

Moreover your polynomial of degree 7 isn't even irreducible.
Irreducible ones are harder to find.

nobody Dec 21, 2014 01:51:26 UTC

If you want twelve more of such polynomials of degree 7, take one by one the above polynomials and multiply by (x-5)(x-6)(x-7)

nobody Dec 21, 2014 01:55:40 UTC

You can build much more of such polynomials from the first twelve above if you think two minits.
The trick will not work to find some irreducible polynomials of degree 7 compliant.

Nobody2015 Dec 31, 2014 21:42:58 UTC

For polynomial of degree $4$ a dumb approach is as follow:

Since $\leq x_1<2,2 \leq x_2<3,3 \leq x_3<4 ,4\leq x_4<5$ are roots. The corresponding symetric functions are such that:

$-14\leq-\sigma_1\leq -10$
$35\leq\sigma_2\leq 71$
$-154\leq-\sigma_3\leq -50$
$24\leq\sigma_4\leq 120$

and:
$x^4-\sigma_1x^3+\sigma_2x^2-\sigma_3x+\sigma_4=(x-x_1)(x-x_2)(x-x_3)(x-x_4)$
(values are obtained in developping of $(x-1)(x-2)(x-3)(x-4)$ and $(x-2)(x-3)(x-4)(x-5)$)

It makes possible the computation.

BUT, the same approach with degree 7 is dumb.