Project Euler Problem 489

Solution

Answer: 1791954757162

Let

$$f(n)=n^3+b,\qquad g(n)=(n+a)^3+b.$$

We want the smallest non-negative $n$ for which

$$\gcd(f(n),g(n))$$

is maximized.

The key observation is that any common divisor must divide the resultant of the two cubic polynomials.

We have

$$g(n)-f(n) =(n+a)^3-n^3 =a(3n^2+3an+a^2).$$

So any common divisor $d$ satisfies

$$d \mid a(3n^2+3an+a^2).$$

Now perform Euclidean reduction of the cubic by the quadratic:

$$n^3+b \equiv \frac{2a^2n+a^3+3b}{3} \pmod{3n^2+3an+a^2}.$$

Thus any common root modulo $d$ must satisfy the linear congruence

$$2a^2n+a^3+3b\equiv 0 \pmod d.$$

Substituting this back into the quadratic yields

$$a^6+27b^2 \equiv 0 \pmod d.$$

Hence every possible gcd divides

$$a^3(a^6+27b^2),$$

which is exactly the resultant:

$$\operatorname{Res}(x^3+b,(x+a)^3+b) = a^3(a^6+27b^2).$$

For primes $p\nmid 2a$, the congruence has a unique solution

$$n \equiv -\frac{a^3+3b}{2a^2} \pmod{p^k},$$

so the full $p$-adic exponent from the resultant is attainable.

Only primes dividing $2a$ need special lifting checks; since $a\le 18$, this is tiny and fast.

Using CRT to combine the local congruences and choosing the smallest nonnegative solution gives $G(a,b)$.

The method reproduces the supplied checks:

Applying it to

$$H(18,1900) = \sum_{1\le a\le 18} \sum_{1\le b\le 1900} G(a,b)$$

gives:

Answer: 1791954757162