Detailed mathematical approach

Problem Summary

For fixed positive integers \(a\) and \(b\), consider the two sequences

$u_n=n^3+b,\qquad v_n=(n+a)^3+b.$

Define

$M(a,b)=\max_{n\ge 0}\gcd(u_n,v_n).$

Then \(G(a,b)\) is the smallest nonnegative integer \(n\) for which \(\gcd(u_n,v_n)=M(a,b)\). The final target is

$H(m,n)=\sum_{a=1}^{m}\sum_{b=1}^{n}G(a,b).$

The C++, Python, and Java implementations do not search \(n\) directly. Instead, they determine the largest prime-power contribution that can occur in the gcd, then reconstruct the smallest index that realizes all of those local maxima simultaneously.

Mathematical Approach

Step 1: A common divisor is a simultaneous congruence condition

For any prime power \(p^k\), the statement \(p^k\mid \gcd(u_n,v_n)\) is equivalent to the pair of congruences

$n^3+b\equiv 0\pmod{p^k},\qquad (n+a)^3+b\equiv 0\pmod{p^k}.$

So the problem is local at each prime: we need to know for which primes and exponents the two cubics have a common residue class.

Step 2: The resultant restricts the relevant primes

If two integer polynomials have a common root modulo a prime \(p\), then \(p\) must divide their resultant. For

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

a direct Sylvester-determinant computation gives

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

Therefore every prime that can appear in the maximal gcd must divide \(a^3(a^6+27b^2)\). This is why the implementation factors \(a^6+27b^2\) for each pair \((a,b)\) and then adds three times the prime exponents coming from \(a\).

Step 3: A quadratic condition modulo \(p\)

Subtract the two congruences:

$0\equiv (n+a)^3-n^3=a(3n^2+3an+a^2)\pmod{p^k}.$

When \(p\nmid a\), this forces

$3n^2+3an+a^2\equiv 0\pmod{p}.$

For odd primes \(p>5\), we may complete the square:

$4(3n^2+3an+a^2)=3(2n+a)^2+a^2,$

hence

$ (2n+a)^2\equiv -\frac{a^2}{3}\pmod{p}. $

This reduces the base search modulo \(p\) to a modular square-root problem. The implementation computes the square root when possible, converts it into up to two candidate residues, and then verifies those candidates in the original cubic congruences. For small primes and degenerate cases with \(p\mid a\), it safely enumerates all residues modulo \(p\) instead of relying on the quadratic shortcut.

Step 4: Lift solutions to the highest possible prime power

Suppose \(r\) is a simultaneous solution modulo \(p^t\). Any lift to the next power must have the form

$n=r+u\,p^t,\qquad u\in\{0,1,\dots,p-1\}.$

The implementation tests all \(p\) descendants and keeps only those that still satisfy both cubic congruences modulo \(p^{t+1}\). Repeating this determines the largest exponent \(k_p\) for which simultaneous roots still exist. If lifting fails at the next stage, then \(p^{k_p}\) is the largest power of \(p\) that can divide the gcd.

Step 5: The maximal gcd is the product of the local maxima

Let \(p^{e_p}\) be the exponent of \(p\) in the resultant, and let \(k_p\le e_p\) be the highest exponent actually reached by the lifting process. Then every value \(\gcd(u_n,v_n)\) has \(p\)-adic valuation at most \(k_p\), so

$M(a,b)\le \prod_p p^{k_p}.$

Conversely, choose one lifted residue class for each surviving prime. Different prime powers are coprime, so the Chinese remainder theorem merges them into a unique class modulo

$Q(a,b)=\prod_p p^{k_p}.$

Every \(n\) in that class makes both sequences divisible by \(p^{k_p}\) for every surviving prime, so

$\boxed{M(a,b)=Q(a,b).}$

Thus \(G(a,b)\) is simply the smallest nonnegative integer in the CRT-merged residue classes.

Worked Examples

For \((a,b)=(1,1)\), the resultant is

$1^3(1^6+27\cdot 1^2)=28=2^2\cdot 7.$

There is no simultaneous root modulo \(2\), while modulo \(7\) the unique solution is \(n\equiv 5\pmod{7}\). Hence the maximal gcd is \(7\), and the first index that attains it is

$G(1,1)=5.$

A lifting example is \((a,b)=(1,5)\). Here

$1^3(1^6+27\cdot 5^2)=676=2^2\cdot 13^2.$

The only surviving prime is \(13\). The residue \(n\equiv 5\pmod{13}\) lifts further to \(n\equiv 161\pmod{169}\), so the maximal gcd is \(13^2=169\) and

$G(1,5)=161.$

How the Code Works

The implementations first build a reusable prime table, precompute the values \(a^6\), \(27b^2\), and the prime factorization of each allowed \(a\). For each pair \((a,b)\), they factor \(a^6+27b^2\), add the prime exponents contributed by \(a^3\), and process each candidate prime separately.

For every prime block, the implementation finds the simultaneous residues modulo \(p\), lifts them as far as possible, and stores the highest modulus that still has solutions. The prime blocks are then ordered by the number of local residues, which keeps the CRT merge smaller in practice. Every merged residue achieves the maximal gcd, and the smallest merged residue is returned as \(G(a,b)\).

Finally, the values are summed over the full \((a,b)\)-grid. Since every pair is independent, the C++, Python, and Java implementations parallelize this outer accumulation. Their published checkpoints are

$G(1,1)=5,\qquad H(5,5)=128878,\qquad H(10,10)=32936544.$

Complexity Analysis

For one pair \((a,b)\), the first cost is factoring \(a^6+27b^2\) with the precomputed prime list. Then each candidate prime needs a local search modulo \(p\), followed by at most one lifting stage for each additional exponent. If the surviving residue counts are \(r_1,r_2,\dots,r_s\), then the CRT phase examines \(r_1r_2\cdots r_s\) combinations in the worst case.

So the runtime is dominated by three ingredients: factoring the resultant part, lifting prime-power roots, and merging local residue classes. Over the full rectangle \(1\le a\le m\), \(1\le b\le n\), the total runtime is roughly linear in the number of parameter pairs, multiplied by the average local arithmetic cost. Memory usage is modest and is dominated by the temporary residue lists carried through lifting and CRT.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=489
2. Resultant of polynomials: Wikipedia — Resultant
3. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
4. Modular square root: Wikipedia — Tonelli-Shanks algorithm
5. Greatest common divisor and valuations: Wikipedia — \(p\)-adic valuation