Detailed mathematical approach

Problem Summary

Define \(S(N)\) as the sum of all integers \(m\le N\) such that \(m\) is squarefree and every prime divisor \(p\mid m\) satisfies

$p-1\mid m+3.$

The target value is \(N=10^{12}\), so testing every integer up to \(N\) is infeasible. Useful checkpoints are

$S(100)=32,\qquad S(10^6)=22868117.$

The implementations therefore convert the prime-divisor conditions into modular constraints and search only inside branches that remain arithmetically possible.

Mathematical Approach

The search is organized around the factorization of \(m\). Instead of scanning all integers, we explicitly choose some large prime factors, deduce a congruence for the missing part, and only enumerate that remainder when the resulting arithmetic progression is sparse enough.

Step 1: Immediate consequences of the condition

The definition already requires

$m\ \text{to be squarefree}.$

Two further observations are crucial.

If \(m=q\) is prime, then the only nontrivial condition is

$q-1\mid q+3,$

so \(q-1\mid 4\). Hence the prime solutions are exactly

$q\in\{2,3,5\}.$

The value \(1\) is also valid vacuously because it has no prime divisors.

Next, a composite solution cannot be even. If \(2\mid m\) and some odd prime \(p\mid m\), then \(m+3\) is odd, while \(p-1\) is an even number greater than \(1\), so \(p-1\nmid m+3\). Therefore every composite solution is an odd squarefree product of distinct odd primes.

Step 2: Separate selected large prime factors from the rest

Choose a descending set of prime factors

$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$

that we want to treat explicitly, and write

$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$

The remaining factor \(u\) must then be odd, squarefree, and have all of its prime factors strictly smaller than the smallest selected prime \(\ell_k\).

For every \(\ell\in\mathcal{L}\), the original condition gives

$\ell-1\mid Q\,u+3.$

Since \(\ell\equiv 1\pmod{\ell-1}\), the selected factor \(\ell\) disappears modulo \(\ell-1\):

$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$

So each selected prime yields one linear congruence for the unknown remainder factor:

$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$

Once the large prime factors are fixed, the rest of the problem has become a congruence problem in one variable.

Step 3: Reduce each congruence and merge them with CRT

A congruence of the form

$a\,u\equiv -3\pmod n$

has a solution only when

$\gcd(a,n)\mid 3.$

If that divisibility fails, the entire search branch is impossible and can be discarded immediately.

Otherwise, writing

$d=\gcd(a,n),$

we divide through by \(d\) and obtain

$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$

Now the coefficient is invertible modulo \(n/d\), so this determines a unique residue class for \(u\) modulo \(n/d\).

Repeating the same reduction for every selected prime produces several residue classes, and the implementations merge them with the generalized Chinese Remainder Theorem. Either they are inconsistent, in which case the branch dies, or they collapse to a single progression

$u\equiv r\pmod M.$

Step 4: Enumerate the remainder only when the progression is sparse

After the congruence merge, all candidates have the form

$u=r+tM,\qquad t\ge 0.$

They must satisfy the obvious size bound

$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$

There is also a sharper structural bound: because \(u\) is squarefree and may use each odd prime below \(\ell_k\) at most once,

$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q.$

Hence the real search interval is

$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q\right).$

If the arithmetic progression contributes only a modest number of terms up to \(U\), the implementations enumerate those terms directly. Each candidate remainder is then checked to be odd and squarefree, factored only with primes below \(\ell_k\), combined with the selected large primes, and finally tested against the original condition for every prime factor of the completed \(m\).

If the progression is still too dense, the search does not enumerate yet. Instead it selects one more large prime factor, appends it to \(\mathcal{L}\), and repeats the congruence-merging step. This branch-and-bound recursion shifts work from brute-force scanning into modular pruning.

Step 5: Worked example for \(N=100\)

The trivial valid values are

$1,\ 2,\ 3,\ 5.$

Now look at the branch where the only selected large prime is \(7\). Then \(Q=7\), and the congruence coming from \(7-1=6\) is

$u\cdot 1\equiv -3\equiv 3\pmod 6,$

so

$u\equiv 3\pmod 6.$

Also

$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$

Because the remaining prime factors must be smaller than \(7\), the only candidates in this progression are

$u=3,\ 9.$

The value \(9\) is rejected because it is not squarefree. The value \(3\) gives

$m=7\cdot 3=21,$

and indeed

$21+3=24$

is divisible by both \(2\) and \(6\), corresponding to the prime divisors \(3\) and \(7\).

For the next possible largest prime, \(11\), the congruence becomes \(u\equiv 7\pmod{10}\), so the only candidate below \(100/11\) is \(u=7\), which gives \(m=77\). That value satisfies the congruence forced by \(11\), but it fails the full condition for the smaller prime \(7\), because \(77+3=80\) is not divisible by \(6\). No larger branch produces a valid composite below \(100\).

Therefore the full list up to \(100\) is

$1,\ 2,\ 3,\ 5,\ 21,$

and hence

$S(100)=1+2+3+5+21=32.$

How the Code Works

The C++, Python, and Java implementations all follow the same number-theoretic decomposition. They generate primes up to about \(\sqrt{N}\), insert the trivial values \(1,2,3,5\), and then recurse over descending sets of selected odd primes \(\ge 7\).

For each recursive branch, the implementation turns the selected-prime constraints into linear congruences, applies the gcd solvability test, and merges the surviving residue classes with generalized CRT. If the combined modulus already exceeds the remaining numeric search interval, only the smallest nonnegative solution can still matter, so the search range is effectively clamped there.

Next it estimates how many terms of the progression remain below the current bound. A branch is enumerated directly only when that estimate is around \(10^4\) terms or fewer; otherwise another large prime is appended and the recursion continues, which usually increases the modulus and decreases the candidate density.

Every enumerated remainder is factored with the branch-specific bound, checked for oddness and squarefreeness, combined with the selected primes, and then verified again against the original condition for every prime divisor. A set of accepted values removes duplicates that can arise from overlapping branches. The Python implementation is only a thin wrapper around the compiled search and parses the final numeric output.

Complexity Analysis

Let \(N\) be the search limit. Building the prime table up to \(\sqrt{N}\) costs \(O(\sqrt{N}\log\log\sqrt{N})\) time and \(O(\sqrt{N})\) memory. After that, there is no clean closed form for the total running time because the recursion is highly data-dependent: each branch either dies early due to incompatible congruences or produces an arithmetic progression whose size is roughly \(U/M\) before final factoring and verification.

The implementation only enumerates a branch once that quantity is small, so most of the practical speed comes from modular pruning rather than from raw trial division. For one enumerated candidate, the remaining factor is checked by bounded trial division using primes below the current threshold, and the completed value is then validated against all of its distinct prime divisors. Memory usage is dominated by the prime list, the set of accepted values, and the recursion stack. In practice the admissible numbers are sparse enough that this strategy is fast for the target limit.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=536
2. Chinese Remainder Theorem: Wikipedia — Chinese Remainder Theorem
3. Squarefree integer: Wikipedia — Squarefree integer
4. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
5. Euclidean algorithm: Wikipedia — Euclidean algorithm