Project Euler Problem 827
Define Q(n) to be the smallest number that occurs in exactly n Pythagorean triples (a,b,c) where a lt b lt c.
Solution
Answer: 397289979
Let $T(n)$ denote the number of Pythagorean triples $(a,b,c)$ with $a<b<c$ in which the integer $n$ appears.
The classical parametrization
$$(a,b,c)=\bigl(k(u^2-v^2),,2kuv,,k(u^2+v^2)\bigr)$$
allows one to derive the exact multiplicative formula for $T(n)$.
Write
$$n = 2^\alpha \prod_{p\equiv1\pmod4} p^{e_p} \prod_{q\equiv3\pmod4} q^{f_q}.$$
Define
$$B=\prod_{p\equiv1\pmod4}(2e_p+1), \qquad A=(2\alpha+1)\prod_{p\equiv1\pmod4}(2e_p+1)\prod_{q\equiv3\pmod4}(2f_q+1).$$
Then the number of triples containing $n$ is
$$T(n)=\frac{A+B-2}{2}.$$
Hence $Q(N)$ is obtained by minimizing $n$ subject to
$$A+B=2(N+1).$$
For each divisor $B\mid(N+1)$ with $B$ odd, set
$$D=\frac{2(N+1)}{B}-1.$$
The minimal $n$ is constructed greedily by assigning larger exponents to smaller primes:
- factors contributing to $B$ use primes $1\bmod4$,
- factors contributing to $D$ use $2$ and primes $3\bmod4$.
This reproduces the checks
$$Q(5)=15,\qquad Q(10)=48,\qquad Q(10^3)=8064000.$$
Evaluating
$$\sum_{k=1}^{18} Q(10^k)\pmod{409120391}$$
gives
$$397289979.$$
Answer: 397289979