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