Detailed mathematical approach

Problem Summary

For a prime \(p\), a verification consists of a prime \(q\) and coprime integers \(A \ge B > 0\) such that every prime less than \(q\) divides the product \(AB\), and either

$p = A + B < q^2$

or

$p = A - B < q^2.$

For each prime \(p\), define \(V(p)\) as the smallest possible value of \(A\) among all such verifications, and define

$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$

The goal is to evaluate \(S(3800)\). A brute-force scan over all possible triples \((A,B,q)\) would waste almost all of its work, so the implementations reorganize the search around divisibility by the primes below \(q\).

Mathematical Approach

The decisive simplification is that once the small primes below \(q\) are assigned to either \(A\) or \(B\), both branches \(p=A+B\) and \(p=A-B\) reduce to the same pair of congruences for \(A\). That turns the problem into a finite search over partitions of a squarefree product.

Step 1: Choose the Smallest Admissible Prime \(q\)

The definition only requires

$p < q^2,$

with \(q\) prime. If some verification works for a certain \(q\), then the same \(A\) and \(B\) also work for any smaller prime \(q'\) with \(p < q'^2\), because the divisibility requirement becomes weaker when fewer primes must divide \(AB\).

Therefore the minimum \(A\) must use the smallest prime satisfying \(q^2 > p\):

$q=\min\{r \text{ prime}: r^2 > p\}.$

So for each fixed prime \(p\), the value of \(q\) is determined immediately.

Step 2: Encode the Divisibility Condition by Splitting a Primorial

Let \(P\) be the product of all primes less than \(q\):

$P=\prod_{r < q} r,$

where the product runs over primes. Since \(AB\) is divisible by every prime below \(q\), we have

$P \mid AB.$

At the same time, the verification requires

$\gcd(A,B)=1.$

Because \(P\) is squarefree, every prime factor of \(P\) must divide exactly one of \(A\) and \(B\), never both. That means we can partition the primes below \(q\) into two disjoint groups and write

$D \cdot E = P,\qquad \gcd(D,E)=1,$

with

$D \mid A,\qquad E \mid B.$

Equivalently,

$A=Dx,\qquad B=Ey$

for some positive integers \(x\) and \(y\). Every divisor \(D \mid P\) corresponds to exactly one such partition, because \(E=P/D\).

Step 3: Both Branches Lead to the Same CRT System

Now fix one partition \(D \cdot E=P\).

In the sum branch \(p=A+B\), the condition \(E \mid B\) becomes

$E \mid (p-A),$

so \(A\) must satisfy

$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$

In the difference branch \(p=A-B\), we have \(B=A-p\), and the condition \(E \mid B\) again gives

$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$

Thus both branches share the same congruence core. Since \(\gcd(D,E)=1\), the Chinese Remainder Theorem gives a unique residue class modulo

$P=DE.$

If we write \(A=Dt\), then

$Dt \equiv p \pmod E,$

hence

$t \equiv pD^{-1} \pmod E.$

So one representative is

$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$

and every candidate for this partition has the form

$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$

Step 4: Convert the Sum Branch into a Short Interval

Suppose \(p=A+B\) with \(A \ge B > 0\). Then

$B=p-A,$

so positivity gives \(A < p\), and the ordering \(A \ge B\) gives

$A \ge p-A \iff 2A \ge p.$

Therefore the sum branch is exactly the interval

$\left\lceil \frac{p}{2} \right\rceil \le A < p.$

For a prime \(p\), coprimality is automatic here:

$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$

because \(0 < A < p\). So for a fixed partition we only need the smallest number in the progression \(A_0+kP\) that lies in this interval.

Step 5: Convert the Difference Branch into a Lower Bound

Suppose instead that \(p=A-B\). Then

$B=A-p,$

and \(B > 0\) is equivalent to

$A > p.$

Now coprimality is no longer automatic. We have

$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$

so the condition \(\gcd(A,B)=1\) becomes

$p \nmid A.$

Hence, for the difference branch, we choose the smallest term of the arithmetic progression \(A_0+kP\) that is strictly larger than \(p\) and not divisible by \(p\).

This last check is simple because \(p\) is not one of the primes below \(q\), so

$\gcd(p,P)=1.$

Therefore, if the first term above \(p\) happens to be a multiple of \(p\), adding one more period \(P\) immediately moves to a non-multiple.

Step 6: Minimize Over All Prime Partitions

Each divisor \(D \mid P\) describes one allocation of the primes below \(q\) between \(A\) and \(B\). For that partition, the CRT gives one residue class modulo \(P\), and the two branches give at most two minimal admissible values of \(A\).

So the answer for one prime \(p\) is

$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{sum}}(D),A_{\mathrm{diff}}(D)\bigr)\Bigr),$

ignoring any missing sum-branch candidate when the interval \([\lceil p/2\rceil,p)\) contains no term from that residue class. Finally,

$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$

Worked Example: \(p=11\)

The smallest prime with \(q^2 > 11\) is \(q=5\), so

$P=2 \cdot 3 = 6.$

The divisors of \(P\) are \(1,2,3,6\). For each one, let \(E=6/D\) and solve

$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$

This gives the following residue classes and candidates:

$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{sum: none},&& \text{difference: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{sum: }8,&& \text{difference: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{sum: }9,&& \text{difference: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{sum: }6,&& \text{difference: }12. \end{aligned}$

The global minimum is \(A=6\), achieved in the sum branch with \(B=5\). Therefore

$V(11)=6.$

How the Code Works

The C++, Python, and Java implementations all follow the same workflow. They first generate the relevant prime lists, then determine for each prime \(p\) the smallest prime \(q\) with \(q^2 > p\).

For each distinct \(q\), the implementation caches the primes below \(q\), forms the product \(P\), enumerates all divisors \(D \mid P\), and precomputes the modular inverse needed for the CRT step. This is useful because many different primes \(p\) share the same \(q\), so the partition data does not need to be rebuilt every time.

When processing one prime \(p\), the implementation scans all partitions \(D \cdot E=P\). For each partition it constructs the residue \(A_0\), lifts it to the smallest admissible value in the sum branch, lifts it again to the smallest admissible value in the difference branch, and keeps the smaller valid result. The minimum over all partitions becomes \(V(p)\), and that value is added to the running total.

The same arithmetic reproduces the small checkpoints

$S(10)=10,\qquad S(200)=7177,$

which serve as a sanity check before evaluating the final target.

Complexity Analysis

Let \(q(p)\) be the smallest prime with \(q(p)^2 > p\), and let \(k=\pi(q(p)-1)\) be the number of primes below \(q(p)\). Because \(P\) is squarefree, it has exactly

$2^k$

divisors. So after the partition table for that \(q\) has been prepared, evaluating one prime \(p\) costs \(O(2^k)\) congruence checks and arithmetic progression adjustments.

Prime generation itself is \(O(n\log\log n)\), while the cached partition tables are built once per distinct \(q\), not once per prime. For the actual target \(n=3800\), the largest needed \(q\) is \(67\), so the largest table uses the \(18\) primes below \(67\), giving

$2^{18}=262144$

partitions. That is the reason the method is practical: the search space is exponential in the number of small primes below \(q\), but that number stays modest in the required range.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=574
2. Primorial: Wikipedia — Primorial
3. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
4. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
5. Greatest common divisor: Wikipedia — Greatest common divisor