Detailed mathematical approach

Problem Summary

For \(N=10^{11}\) and the prime \(p=2017\), we must compute

$S(N,p)=\sum_{\substack{1\le n\le N\\ p\mid \sigma(n)}} n,$

where \(\sigma(n)\) is the sum of positive divisors of \(n\). A brute-force scan would require evaluating \(\sigma(n)\) for every \(n\le N\), which is far too expensive. The solution instead identifies the exact prime-power exponents that force divisibility by \(2017\), rewrites the task as a weighted union of exact-valuation events, and then sums that union with inclusion-exclusion.

Mathematical Approach

Write the prime factorization of \(n\) as

$n=\prod_q q^{a_q}.$

Because the divisor-sum function is multiplicative,

$\sigma(n)=\prod_q \sigma\!\left(q^{a_q}\right).$

Therefore \(2017\mid \sigma(n)\) if and only if at least one prime \(q\) satisfies \(2017\mid \sigma(q^{a_q})\).

Step 1: Reduce the problem to trigger prime powers

Define the set of trigger pairs

$B=\left\{(q,e): e\ge 1,\ q^e\le N,\ 2017\mid \sigma(q^e)\right\},$

where \(q\) is prime.

Then the target sum is the weighted union

$S(N,2017)=\sum_{\substack{1\le n\le N\\ \exists (q,e)\in B:\ v_q(n)=e}} n,$

where \(v_q(n)\) denotes the exponent of \(q\) in \(n\). Exact valuations matter: the condition depends on the precise exponent \(a_q\), not merely on divisibility by \(q^e\).

The prime \(q=2017\) never contributes, because

$\sigma(2017^e)=1+2017+\cdots+2017^e\equiv 1 \pmod{2017}.$

Step 2: Characterize the bad exponents with multiplicative order

For a prime \(q\neq 2017\),

$\sigma(q^e)=1+q+\cdots+q^e=\frac{q^{e+1}-1}{q-1}.$

If \(q\not\equiv 1 \pmod{2017}\), the denominator is invertible modulo \(2017\), so

$2017\mid \sigma(q^e)\iff q^{e+1}\equiv 1 \pmod{2017}.$

Let \(\operatorname{ord}_{2017}(q)\) be the multiplicative order of \(q\) modulo \(2017\). Then

$2017\mid \sigma(q^e)\iff \operatorname{ord}_{2017}(q)\mid (e+1),$

so the bad exponents are exactly

$e=m\operatorname{ord}_{2017}(q)-1,\qquad m\ge 1.$

Since \(2017-1=2016=2^5\cdot 3^2\cdot 7\), every such order divides \(2016\).

The residue class \(q\equiv 1 \pmod{2017}\) behaves differently, because then

$\sigma(q^e)\equiv e+1 \pmod{2017}.$

That would require \(e+1\) to be a multiple of \(2017\), impossible under \(q^e\le 10^{11}\). So primes congruent to \(1\) modulo \(2017\) contribute nothing.

Step 3: Separate the order-2 branch from the rest

If \(q\equiv -1 \pmod{2017}\), then \(\operatorname{ord}_{2017}(q)=2\), hence all odd exponents are formally bad.

For the target scale, however, only \(e=1\) can occur. The smallest prime with \(q\equiv -1 \pmod{2017}\) is \(12101\), and

$12101^3>10^{11}.$

So the order-2 branch contributes only prime powers of the form \(q^1\).

All remaining bad cases come from primes \(q\not\equiv \pm 1 \pmod{2017}\) with order at least \(3\), so their smallest bad exponent is at least \(2\). Consequently such primes matter only when \(q\le \sqrt{N}\), which is why this branch is searched only up to \(\lfloor \sqrt{N}\rfloor\).

Step 4: Turn each trigger pair into a closed-form weighted sum

For each \((q,e)\in B\), define the event

$A_{q,e}=\{n\le N:\ v_q(n)=e\}.$

Every integer in this event has the form \(n=q^e m\) with \(q\nmid m\) and

$m\le M=\left\lfloor \frac{N}{q^e}\right\rfloor.$

If \(T(x)=x(x+1)/2\) denotes the triangular-number sum, then

$\sum_{n\in A_{q,e}} n =q^e\sum_{\substack{m\le M\\ q\nmid m}} m =q^e\left(T(M)-q\,T\!\left(\left\lfloor \frac{M}{q}\right\rfloor\right)\right).$

This gives every single-event contribution in constant time once \(q^e\) is known.

Step 5: Use pairwise inclusion-exclusion, and stop there exactly

Events with the same prime \(q\) but different exponents are disjoint, so overlaps only arise from distinct primes. If \((q,e)\) and \((r,f)\) are trigger pairs with \(q\neq r\), then

$n=q^e r^f m,\qquad q\nmid m,\qquad r\nmid m,$

with

$m\le X=\left\lfloor \frac{N}{q^e r^f}\right\rfloor.$

Therefore

$\sum_{n\in A_{q,e}\cap A_{r,f}} n =q^e r^f\left(T(X)-q\,T\!\left(\left\lfloor \frac{X}{q}\right\rfloor\right)-r\,T\!\left(\left\lfloor \frac{X}{r}\right\rfloor\right)+qr\,T\!\left(\left\lfloor \frac{X}{qr}\right\rfloor\right)\right).$

Hence

$S(N,2017)=\sum_{(q,e)\in B}\sum_{n\in A_{q,e}} n-\sum_{\substack{(q,e),(r,f)\in B\\ q<r}}\sum_{n\in A_{q,e}\cap A_{r,f}} n,$

because triple intersections cannot occur for \(N=10^{11}\). The three smallest admissible trigger prime powers are

$2311^2=5{,}340{,}721,\qquad 229^3=12{,}008{,}989,\qquad 3739^2=13{,}980{,}121,$

and their product already exceeds \(10^{11}\) by many orders of magnitude. So second-order inclusion-exclusion is exact, not approximate.

Worked Example

Two concrete trigger prime powers show the mechanism.

First, \(12101\equiv -1 \pmod{2017}\), so order \(2\) gives the bad exponent \(e=1\), and indeed

$\sigma(12101)=1+12101=12102=6\cdot 2017.$

Second, \(2311\) has multiplicative order \(3\) modulo \(2017\), so \(e=2\) is bad, and

$\sigma(2311^2)=1+2311+2311^2=5{,}343{,}033=2649\cdot 2017.$

For \(N=10^{11}\), their overlap uses

$P=12101\cdot 2311^2=64{,}628{,}064{,}821\le 10^{11},$

so exactly one multiplier \(m=1\) is possible. The pair contribution is therefore precisely \(P\), and it must be subtracted once from the two single-event contributions.

How the Code Works

The implementation first generates all primes up to \(\lfloor \sqrt{N}\rfloor\). That prime list serves two purposes: it determines multiplicative orders modulo \(2017\) for the non-\(\pm 1\) branch, and it also drives a sieve on the arithmetic progression \(2017k-1\) to collect every prime congruent to \(-1\) modulo \(2017\) up to \(N\).

Next, the C++, Python, and Java implementations enumerate all trigger pairs \((q,e)\). For the order-2 branch they record only exponent \(1\). For the other branch they compute the multiplicative order as a divisor of \(2016\), list every exponent \(e=m\operatorname{ord}_{2017}(q)-1\) with \(q^e\le N\), and discard primes that cannot contribute.

Once the trigger list is known, the implementation accumulates all single-event formulas above. It then subtracts all admissible pair overlaps in three groups: order-2 with order-2, order-2 with other triggers, and other triggers with each other. The Python implementation delegates execution to the compiled solver, while the Java implementation mirrors the same arithmetic directly with arbitrary-precision integers.

The solver also verifies the published checkpoints

$S(10^6,2017)=150850429,\qquad S(10^9,2017)=249652238344557,$

before evaluating the final \(N=10^{11}\) case.

Complexity Analysis

Generating all primes up to \(\sqrt{N}\) costs \(O(\sqrt{N}\log\log N)\) time and \(O(\sqrt{N})\) memory. Sieving the progression \(2017k-1\) up to \(N\) uses an array of length \(\lfloor (N+1)/2017\rfloor\), so that stage needs \(O(N/2017)\) memory and about \(O((N/2017)\log\log N)\) marking work. The remaining order checks and inclusion-exclusion sums run only over the finite trigger list and its admissible pairs. For the target parameters, those later steps are smaller than the two sieve phases.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=565
2. Divisor function: Wikipedia — Divisor function
3. Multiplicative order: Wikipedia — Multiplicative order
4. \(p\)-adic valuation: Wikipedia — \(p\)-adic valuation
5. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle