Detailed mathematical approach

Problem Summary

For each prime

$p\in[10^7,2\cdot 10^7),$

we form its digital-root chain

$n_0=p,\qquad n_{i+1}=s(n_i),$

until a single digit is reached. Two seven-segment clocks display this chain:

Sam always turns everything off and then lights the next number from scratch.

Max only toggles the segments that actually change.

We must sum

$\Delta(p)=C_{\text{Sam}}(p)-C_{\text{Max}}(p)$

over all primes in the interval.

Mathematical Approach

1) Seven-segment bitmasks.

Each digit \(d\in\{0,\dots,9\}\) is encoded by a 7-bit mask \(M_d\). For example, in the segment convention used by the code, digit \(1\) has 2 lit segments, digit \(7\) has 4, digit \(8\) has 7, and so on.

Let

$\sigma(d)=\operatorname{popcount}(M_d)$

be the number of lit segments in one digit. For a whole number \(n\) with decimal digits \(d_j\), define

$\Sigma(n)=\sum_j \sigma(d_j).$

This is the cost of lighting \(n\) from a blank display, and also the cost of turning \(n\) fully off.

2) Sam's cost.

Sam never tries to reuse lit segments. If the chain is

$n_0\to n_1\to\cdots\to n_t,$

then each displayed value contributes once to turn it on and once to turn it off. Therefore

$C_{\text{Sam}}(n_0)=2\sum_{i=0}^{t}\Sigma(n_i).$

3) Max's cost as a Hamming distance.

To go directly from number \(a\) to number \(b\), Max flips only the segments whose states differ. Align the numbers by decimal place from the right; missing digits are treated as a blank digit with mask \(0\), not as the numeral \(0\).

Thus the transition cost is

$D(a,b)=\sum_j \operatorname{popcount}(M_{a_j}\oplus M_{b_j}),$

where an absent digit contributes mask \(0\).

This is exactly the bitwise Hamming distance between the two displayed numbers.

4) Max's total chain cost.

Max starts from a blank display, walks through the digital-root chain, then returns to blank at the end:

$C_{\text{Max}}(n_0)=D(0,n_0)+\sum_{i=1}^{t}D(n_{i-1},n_i)+D(n_t,0).$

Finally, for one prime we add

$\Delta(n_0)=C_{\text{Sam}}(n_0)-C_{\text{Max}}(n_0).$

5) Worked example: \(137\to11\to2\).

The chain is

$137\to 1+3+7=11\to 1+1=2.$

Segment counts are

$\Sigma(137)=\sigma(1)+\sigma(3)+\sigma(7)=2+5+4=11,$

$\Sigma(11)=2+2=4,\qquad \Sigma(2)=5.$

So Sam spends

$C_{\text{Sam}}=2(11+4+5)=40.$

For Max, the code computes

$D(0,137)=11,$

$D(137,11)=7,$

$D(11,2)=7,$

$D(2,0)=5.$

Hence

$C_{\text{Max}}=11+7+7+5=30,$

and therefore

$\Delta(137)=40-30=10.$

This is exactly the checkpoint embedded in the C++ solution.

6) Why the chain is tiny in this problem.

All primes lie between \(10^7\) and \(2\cdot10^7\), so they have at most 8 digits. The first digit sum is therefore at most

$1+7\cdot 9=64.$

After one application of digit sum, the chain is already at most two digits long. After another application it is at most \(10\), and then immediately a single digit. So each prime contributes only a handful of transitions.

7) Prime accumulation.

The rest of the problem is just iteration over primes in the interval. The code uses a sieve to mark all primes in

$[10^7,2\cdot10^7),$

builds the digital-root chain for each prime, and accumulates the difference \(\Delta(p)\).

Algorithm

1) Predefine the 7-segment masks for digits \(0\) through \(9\).

2) Sieve the interval to find all primes.

3) For each prime, build the chain \(p\to s(p)\to s(s(p))\to\cdots\).

4) Compute Sam's cost as

$2\sum \Sigma(n_i).$

5) Compute Max's cost using transition XOR distances.

6) Add the difference.

Complexity Analysis

The sieve costs

$O(B\log\log B)$

time and

$O(B)$

memory for upper bound \(B\). After that, each prime contributes only a tiny constant amount of work because its digital-root chain is extremely short in this range.

Checks And Final Result

The implementation checks:

For \(137\), Sam costs \(40\) and Max costs \(30\).

For a single-digit chain such as \(7\), Sam and Max coincide.

The final answer for the full interval is

$13625242.$

Further Reading

1. Problem page: https://projecteuler.net/problem=315
2. Digital root: https://en.wikipedia.org/wiki/Digital_root
3. Seven-segment display: https://en.wikipedia.org/wiki/Seven-segment_display