Detailed mathematical approach

Problem Summary

For a given bound \(n\), we sum \(p+q\) over all triples of positive integers \((p,q,r)\) satisfying

$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$

A naive search over all triples is far too expensive. The key observation is that, once \(r\) is fixed, every valid pair \((p,q)\) comes from a divisor of \(r^2-1\), so the problem becomes a structured divisor-enumeration task instead of a three-dimensional brute-force scan.

Mathematical Approach

Let \(S(n)\) denote the required total:

$S(n)=\sum (p+q),$

where the sum ranges over all triples \((p,q,r)\) satisfying the conditions above. The derivation below explains why the implementations only need to loop over \(r\) and divisors of \(r^2-1\).

Step 1: Turn the congruences into exact equations

Because \(pr \equiv 1 \pmod q\), there is an integer \(a\) such that

$pr-1=aq.$

Likewise, from \(qr \equiv 1 \pmod p\), there is an integer \(b\) with

$qr-1=bp.$

Since \(q>r\), we have

$0 \le a=\frac{pr-1}{q} < p.$

Reduce the first equation modulo \(p\). Because \(qr \equiv 1 \pmod p\), the number \(q\) is the inverse of \(r\) modulo \(p\). Multiplying \(pr-1=aq\) by \(r\) modulo \(p\) gives

$-r \equiv aqr \equiv a \pmod p.$

The unique integer in \([0,p-1]\) congruent to \(-r\) modulo \(p\) is \(p-r\), so

$a=p-r.$

Therefore

$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$

By symmetry, the second congruence yields

$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$

Step 2: Measure how far \(p\) and \(q\) are from \(r\)

Set

$d=p-r,\qquad e=q-r,$

so that

$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$

Insert \(p=r+d\) into the formula for \(q\):

$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$

Hence

$e=\frac{r^2-1}{d},\qquad de=r^2-1.$

This is the core reduction. For a fixed \(r\), every valid triple corresponds to a factor pair of \(r^2-1\).

Step 3: Determine the exact divisor range

The condition \(p \le n\) becomes

$r+d \le n,\qquad d \le n-r.$

The ordering \(q>p\) is equivalent to \(e>d\). Since \(de=r^2-1\), this means

$d^2 < r^2-1.$

For integers \(r \ge 2\), that is equivalent to

$d \le r-1.$

So the admissible divisors are exactly those satisfying

$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$

Once such a divisor is chosen, the corresponding pair is forced:

$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$

Step 4: Prove the converse direction

The reduction is not just necessary; it is exact. Suppose \(r \ge 2\) and \(d\) is a divisor of \(r^2-1\) with \(1 \le d \le m_r\). Define

$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$

Then

$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$

so \(pr \equiv 1 \pmod q\). Similarly,

$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$

so \(qr \equiv 1 \pmod p\). The bound \(d \le n-r\) guarantees \(p \le n\), and \(d \le r-1\) guarantees \(q>p\). Therefore every admissible divisor produces one valid triple, and every valid triple produces one admissible divisor. This is a bijection.

Step 5: Final summation formula

For a fixed \(r\), each valid divisor contributes

$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$

Thus

$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$

where \(m_r=\min(r-1,n-r)\). This is exactly the quantity computed by the implementations.

Worked Example: \(n=5\)

Only \(r=2,3,4\) can contribute.

For \(r=2\), we have \(r^2-1=3\) and \(m_r=\min(1,3)=1\). The only admissible divisor is \(d=1\), giving

$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$

so the contribution is \(3+5=8\).

For \(r=3\), we have \(r^2-1=8\) and \(m_r=\min(2,2)=2\). The admissible divisors are \(d=1,2\):

$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$

$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$

For \(r=4\), we have \(r^2-1=15\) and \(m_r=\min(3,1)=1\). Only \(d=1\) is allowed, producing

$ (p,q)=(5,19),\quad p+q=24. $

Adding everything gives

$S(5)=8+15+12+24=59.$

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They begin by building a smallest-prime-factor table up to slightly above \(n\). That allows fast factorizations of \(r-1\) and \(r+1\) for every \(r\).

For each \(r\) from \(2\) to \(n-1\), the implementation computes \(m_r=\min(r-1,n-r)\). If \(m_r \le 0\), that \(r\) cannot contribute. Otherwise, it factors \(r-1\) and \(r+1\), merges the prime exponents, and thereby obtains the prime factorization of

$r^2-1=(r-1)(r+1).$

Next, it recursively enumerates divisors from that factorization. During this search, branches are pruned as soon as the partial divisor already exceeds \(m_r\), because such a divisor cannot yield a valid \(p\).

Whenever a complete admissible divisor \(d\) is produced, the implementation computes

$p=r+d,\qquad q=r+\frac{r^2-1}{d},$

and adds \(p+q\) to the running total. The whole algorithm is therefore a careful divisor-generation procedure driven by the exact bijection proved above.

Complexity Analysis

Building the smallest-prime-factor table costs \(O(n\log\log n)\) time and \(O(n)\) memory. For each \(r\), factoring \(r-1\) and \(r+1\) is fast because the factorization follows the precomputed table. The dominant work is enumerating admissible divisors of \(r^2-1\), so the total running time is well described by

$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right),$

up to the usual small-factor savings from pruning divisors larger than \(m_r\). In practice, this is dramatically smaller than brute-force enumeration over all candidate triples.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=784
2. Modular arithmetic: Wikipedia — Modular arithmetic
3. Divisor function: Wikipedia — Divisor function
4. Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic
5. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes