Open Source · 7 Languages · 1007 Problems + Bonus

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 315: Digital Root Clocks

Project Euler Problem 315 Solution

EulerSolve provides an optimized solution for Project Euler Problem 315, Digital Root Clocks, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

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.$$