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

A digital root clock shows the number it is fed, then its digit sum, then that number's digit sum, and so on until one digit remains; then the panel goes black. Fed $137$ it shows $137$, then $11$, then $2$. Every digit is drawn with seven lamps: three horizontal bars (top, middle, bottom) and four verticals (top-left, top-right, bottom-left, bottom-right). A $1$ uses the two right-hand verticals, a $4$ the middle bar with top-left, top-right and bottom-right, an $8$ all seven; lighting a $2$ costs $5$ transitions and a $7$ only $4$. Energy is spent only when a lamp switches. ^[1]

Sam's clock blanks the whole panel between two displayed numbers, so for $137$ it pays $(2+5+4)\cdot2=22$, then $(2+2)\cdot2=8$, then $5\cdot2=10$: $40$ transitions. Max's clock switches off only the lamps the next number does not need, and for $137$ it pays $30$. Both are fed every prime $p$ with $A=10^7\le p\lt B=2\cdot10^7$, and we must find Sam's total minus Max's.

The whole solution in one sentence: a two-line identity about bit counts shows that Max's saving on a chain is exactly twice the number of lamps that stay lit from one displayed number to the next, so one sieve plus a few bit operations per prime settles the sum.

Mathematical Approach

1. The display as seven bits

Number the seven lamps of one digit position $0,\dots,6$ and describe a digit $d$ by the mask $M_d$, whose bit $j$ is $1$ exactly when lamp $j$ is lit. Write $\nu(x)$ for the number of $1$ bits of $x$. The statement fixes five lamp counts in words — a $1$ has two, a $2$ five, a $4$ four, a $7$ four, an $8$ seven — and the figure fixes the rest in the usual shapes, so

$$\begin{aligned}\nu(M_0)&=6,\ \nu(M_1)=2,\ \nu(M_2)=5,\\ \nu(M_3)&=5,\ \nu(M_4)=4,\ \nu(M_5)=5,\\ \nu(M_6)&=6,\ \nu(M_7)=4,\ \nu(M_8)=7,\\ \nu(M_9)&=6.\end{aligned}$$

The $7$ is worth a remark. On most seven-segment displays it is three lamps; this clock adds the top-left vertical, the shape known as a $7$ "with a tail", ^[3] and the statement settles it by pricing a $7$ at $4$. Likewise the $6$ keeps its top bar and the $9$ its bottom bar, six lamps each.

For a displayed number $n$ with digits $d_j$ (position $j=0$ the units) put

$$\sigma(n)=\sum_j\nu(M_{d_j}),$$

the lamps lit while $n$ stands on the panel: $\sigma(137)=2+5+4=11$, $\sigma(11)=4$, $\sigma(2)=5$.

2. Repeated digit sums and the digital root

Let $s(n)$ be the digit sum of $n$. The clock displays the chain

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

stopping at the first $n_t\lt10$. It is finite because $s(n)\lt n$ for $n\ge10$: writing $n=\sum_j d_j10^j$ gives $n-s(n)=\sum_j d_j(10^j-1)\ge0$, and for $n\ge10$ some $d_j$ with $j\ge1$ is nonzero, so that sum is positive. The last entry $n_t$ is the digital root of $n$. Since $10\equiv1\pmod9$, every number is congruent to its digit sum modulo $9$, so the whole chain is congruent to $n$ modulo $9$ and

$$n_t=1+\bigl((n-1)\bmod9\bigr)\quad(n\ge1).$$

This is the standard congruence formula for the digital root. ^[2] ^[6] It gives a free sanity check. Were the digital root of $p$ equal to $3$, $6$ or $9$ then, being congruent to $p$ modulo $9$ and hence modulo $3$, it would force $3\mid p$; so every prime $p\gt3$ has digital root in $\{1,2,4,5,7,8\}$.

3. The display is right-aligned, and a blank is not a zero

When the panel changes from $a$ to $b$ the numbers are aligned by decimal place, units under units, and a position used by one and not the other faces a blank, whose mask is $0$ — not that of the numeral $0$, which has six lamps. In the $137\to11$ step the hundreds position goes from a $1$ to blank, which is why the statement counts the first $1$ of $137$ as switched off.

Max switches exactly the lamps whose state differs, so the step costs

$$D(a,b)=\sum_j\nu\bigl(M_{a_j}\oplus M_{b_j}\bigr),$$

with $\oplus$ the bitwise exclusive or and an absent digit contributing the mask $0$: the Hamming distance between the two panel states read as bit strings. ^[4] Lighting $n$ on a black panel costs $D(0,n)=\sigma(n)$ and blanking it costs $D(n,0)=\sigma(n)$, since every lit lamp is switched once and nothing else moves. The integer $0$ stands for the black panel, unambiguously: a positive integer has a positive digit sum and a digital root in $\{1,\dots,9\}$, so no chain entry is ever $0$.

4. What Sam pays, and what Max pays

Sam lights every chain entry from black and blanks it again, so

$$C_{\mathrm{Sam}}(n)=2\sum_{i=0}^{t}\sigma(n_i).$$

Max starts from a black panel, walks the chain, and blanks the panel at the end:

$$\begin{aligned}C_{\mathrm{Max}}(n)&=\sigma(n_0)+\sigma(n_t)\\ &\quad+\sum_{i=1}^{t}D(n_{i-1},n_i).\end{aligned}$$

The quantity to be summed over the primes of the window is $\Delta(n)=C_{\mathrm{Sam}}(n)-C_{\mathrm{Max}}(n)$.

5. The key identity: the saving is twice the shared light

One lamp tells the whole story. Lit in both consecutive displays, it costs Sam two transitions, off and on again, and costs Max nothing; lit in just one of them it costs one transition either way, and dark in both it costs nothing. Every shared lamp therefore saves exactly two transitions; the rest is bookkeeping. Let $\kappa(a,b)$ count the lamps lit in both panel states,

$$\kappa(a,b)=\sum_j\nu\bigl(M_{a_j}\wedge M_{b_j}\bigr),$$

with $\wedge$ the bitwise and. Counting bit by bit, $x\oplus y$ has a $1$ exactly where one of $x,y$ does and $x\wedge y$ does not, so

$$\nu(x\oplus y)=\nu(x)+\nu(y)-2\,\nu(x\wedge y),$$

and summing this over the digit positions yields

$$D(a,b)=\sigma(a)+\sigma(b)-2\,\kappa(a,b).$$

Substituting into Max's cost, the inner sum becomes

$$\begin{aligned}&\sum_{i=1}^{t}\bigl(\sigma(n_{i-1})+\sigma(n_i)\bigr)\\ &\qquad-2\sum_{i=1}^{t}\kappa_i,\end{aligned}$$

where $\kappa_i=\kappa(n_{i-1},n_i)$. In the first sum every $\sigma(n_i)$ appears twice except $\sigma(n_0)$ and $\sigma(n_t)$, so it equals

$$2\sum_{i=0}^{t}\sigma(n_i)-\sigma(n_0)-\sigma(n_t).$$

The leftover terms cancel the outer $\sigma(n_0)+\sigma(n_t)$ of Max's cost, leaving

$$\Delta(n)=2\sum_{i=1}^{t}\kappa(n_{i-1},n_i).$$

So $\Delta(n)$ is always even, and $\Delta(n)=0$ for a single-digit feed, where the chain has one entry and the sum is empty — the second checkpoint of the C++ program.

6. The statement's example, worked out

For $137\to11\to2$ the masks give $\sigma=11,4,5$, so $C_{\mathrm{Sam}}=2(11+4+5)=40$. The steps cost $D(0,137)=11$, $D(137,11)=7$, $D(11,2)=7$, $D(2,0)=5$, so $C_{\mathrm{Max}}=30$: the two totals of the statement. The shared counts are $\kappa(137,11)=4$, the two right-hand verticals surviving in both the units and the tens position, and $\kappa(11,2)=1$, only the top-right vertical being reused. Section 5 then gives $\Delta(137)=2(4+1)=10=40-30$.

7. A chain from the real window

Take $19999999$, the largest prime in the window and the one with the largest digit sum. Its chain is $19999999\to64\to10\to1$, with $\sigma=44,10,8,2$, so $C_{\mathrm{Sam}}=2(44+10+8+2)$${}=128$, while $\kappa=9,4,2$ lamps survive the three steps. Hence $\Delta=2(9+4+2)=30$ and $C_{\mathrm{Max}}=98$, which also equals $44+36+10+6+2$: the lighting, the three steps and the blanking.

8. What the chains look like between $10^7$ and $2\cdot10^7$

Every $p$ in the window has eight digits and leading digit $1$, so $s(p)\le1+7\cdot9=64$, attained by $19999999$, while the smallest digit sum here is $4$, attained by $10010101$. By Section 2 the digit sum is congruent to $p$ modulo $9$ and so never a multiple of $3$, and every integer in $\{4,\dots,64\}$ that is not a multiple of $3$ does occur: exactly $41$ values. Put $m=s(p)$. If $m\lt10$ the chain ends; otherwise $s(m)\le14$, since $s(m)\le5+9$ for $m\le59$ and $s(m)\le6+4$ for $60\le m\le64$. A remaining two-digit value then lies in $\{10,\dots,14\}$, whose digit sums are at most $5$. So the chain has at most four entries, and enumeration gives the counts:

$s(p)\lt10$, only for $s(p)\in\{4,5,7,8\}$: two entries, just $211$ primes;
$s(p)\ge10$ with a single-digit digit sum: three entries, $410898$ primes;
$s(s(p))\ge10$, for the thirteen values $s(p)\in\{19,28,29,37,38,46,$${}47,49,55,56,58,59,64\}$: four entries, $194919$ primes.

These disjoint groups hold all $606028$ primes of the window. The same enumeration shows that the attained values of $\Delta(p)$ are exactly $2,4,\dots,40$.

9. Two digits of $p$ and its digit sum decide the saving

Because $n_1=s(p)$ has at most two digits, every position of $p$ above the tens meets a blank in the first step and so adds nothing to $\kappa(n_0,n_1)$. Only the tens and units positions of $p$ remain — and by Section 3 both must be kept as digits, since a tens digit $0$ shows the numeral $0$, six lamps, not a blank. The prime $10000609$ makes the point: with $s(p)=16$ its last two displayed digits $0$ and $9$ share $2+5=7$ lamps with $16$, whereas the bare integer $9$ would share only $5$.

So $\kappa(p,n_1)$ is fixed by that pair of digits and $n_1$, and since $p$ has eight digits the pair is read off $p\bmod100$. The later $\kappa_2,\kappa_3$ depend on $n_1$ alone, so $\Delta(p)$ is determined by $(p\bmod100,\,s(p))$. Exactly $1164$ such pairs occur here, so counting the primes per class and taking a weighted total checks the prime-by-prime sum; it also shows the work per prime is bounded.

10. Finding the primes

The method puts no condition on the primes, so a sieve of Eratosthenes lists them over $[0,B)$: one flag per integer, and for each $p$ with $p^2\lt B$ the multiples $p^2,p^2+p,\dots$ are struck out, from $p^2$ on because smaller multiples of $p$ carry a smaller prime factor and are gone already. ^[5] The largest striking prime is $4463$, and the sieve yields $\pi(2\cdot10^7)-\pi(10^7)$${}=1270607-664579=606028$ primes. A segmented sieve would store only the interval and the primes up to $\sqrt B$; at this size the programs keep the plain full sieve.

How the Code Works

The C++ program ^[7] builds the ten masks of Section 1 in digit_masks() from named bit constants T, M, B, TL, TR, BL, BR equal to 1 << 0 up to 1 << 6; the entry for $7$ carries the comment that it uses four segments in this display style. digital_root_chain implements Section 2 literally: it appends the current value, stops once it is below $10$, and otherwise replaces it by its digit_sum.

Two functions price a panel state. segment_count_number is $\sigma$ of Section 1: it peels digits off with % 10 and / 10 and adds __builtin_popcount of each mask. ^[8] transition_cost(from, to) is $D$ of Section 3: it peels digits off both numbers at once — the right-aligned comparison — substitutes the mask $0$ once a number is exhausted, and adds the bit count of the exclusive or. sam_cost and max_cost assemble the formulas of Section 4; neither uses the identity of Section 5, which is why that identity is available as an independent check.

solve(from, to) sieves a byte vector of length to as in Section 10, then walks $p$ across the window, skips composites, and adds sam_cost - max_cost into an i64. run_checkpoints() guards it: $137$ must give $40$ and $30$, and a single-digit feed must make the clocks agree; main exits with status $2$ on failure. parse_arguments accepts --from=, --to= and --skip-checkpoints and insists on from >= 2 and to > from, so the program runs on smaller intervals too; it does not guard against overflow while reading an oversized argument.

The two ports compute the same quantities with a different layout. Python nests its helpers inside solve(), calls the segment counter seg_count, counts bits with bin(x).count('1'), clears each sieving prime's multiples by one bytearray slice assignment, and fixes the interval as constants instead of parsing arguments; its masks list is defined twice, and the second definition, built from the same named constants as the C++ table, replaces the first before anything uses it. Java keeps digitSum, segmentCountNumber and transitionCost as methods but builds the chain and both costs inline in solve(), reusing one int[] chain of length $16$ — ample for the four entries Section 8 proves — and counts bits with Integer.bitCount ^[8]. Neither port carries the checkpoint guard.

Complexity and Verification

The sieve dominates: $O(B\log\log B)$ time and $O(B)$ memory, ^[5] here one byte per integer, about $20$ MB of sieve array in each language — the payload, not the peak, since Python briefly holds both the $20$ MB bytes object and the bytearray copy made from it. By Section 8 a chain has at most four entries of at most eight digits, so each prime costs a bounded number of bit operations and the pass adds only $O(B)$. Measured on one machine, C++ takes $0.10$ s and Java $0.11$ s; Python needs $3.5$ s, its loop visiting all $10^7$ integers in interpreted code and its sieve step materialising a temporary slice just to learn that slice's length. As $\Delta(p)\le40$, the total stays below $606028\cdot40=24241120$, which even a signed 32-bit integer would hold.

The C++ program runs its two checkpoints unless --skip-checkpoints is given; the ports carry no checks of their own. The following were verified for this article.

The identity of Section 5 agreed with the definition of $C_{\mathrm{Sam}}-C_{\mathrm{Max}}$ for every $n\le200000$ and all $606028$ primes here.
$\Delta(p)$ really is constant on each of the $1164$ classes of Section 9, and the weighted total over them equals the prime-by-prime total.
The digital roots of the $606028$ primes are $1,2,4,5,7,8$ only, as Section 2 requires, each occurring between $100914$ and $101136$ times.
Six smaller intervals, run with the --from/--to options of the published C++ program and reproduced by an independent implementation: $[10,10^2)$ gives $218$, $[10^2,10^3)$ $2316$, then $20744$, $179968$, $1530746$ and, for $[10^6,10^7)$, $13167082$.
The first is checkable by hand: $19\to10\to1$ has $\sigma=8,8,2$ and $\kappa=7,2$, so $C_{\mathrm{Sam}}=36$ and $\Delta(19)=18$; over the $21$ primes with $10\le p\lt100$ this sums to $218$.
The C++, Python and Java programs print the same value for the required window.

Footnotes and References

The references below supply the background facts used above. The identity of Section 5 and the results of Sections 8 and 9 are derived and verified explicitly here.

Project Euler 315 — Digital Root Clocks. The official statement describes a clock that shows a number and then its successive digit sums, prices the seven-segment shapes (a 2 costs 5 transitions, a 7 costs 4), contrasts Sam's clock, which blanks the panel between numbers, with Max's, which keeps the lamps the next number needs, totals 40 and 30 transitions for 137, and asks for the difference over the primes between 10⁷ and 2·10⁷.
Wikipedia — Digital root. The digital root comes from repeatedly summing the decimal digits, and in base 10 it is the remainder modulo 9 with 0 replaced by 9; the congruence formula dr(n) = 1 + ((n − 1) mod 9) for n ≠ 0 is the one used in Section 2.
Wikipedia — Seven-segment display. The segments are labelled a to g: a top, middle and bottom bar plus two verticals on each side. It records both the common three-segment 7 and the alternative 7 "with a tail", the four-segment form this problem uses, and notes that 6 and 9 may be drawn with or without theirs.
Wikipedia — Hamming distance. For two strings of equal length it is the number of positions at which the symbols differ, and for bit strings the number of 1 bits of their exclusive or — how Section 3 measures Max's cost for one step.
Wikipedia — Sieve of Eratosthenes. It gives O(n log log n) time and O(n) memory for the basic sieve and justifies both refinements the code uses: multiples of p may be struck out from p² on, since smaller ones carry a smaller prime factor, and only primes up to √n are needed.
OEIS A010888 — digital root of n. The entry defines the additive digital root as the result of repeatedly adding the digits of n and states a(n) = ((n − 1) mod 9) + 1 for n > 0, the period-9 fact used in Section 2.
C++ — Euler315.cpp. The linked immutable revision contains digit_masks, transition_cost, max_cost, solve and the run_checkpoints guard, with the --from, --to and --skip-checkpoints options; the unguarded argument overflow sits in parse_int_after_prefix. It is the implementation record for this article; the identity check and class decomposition are additional validation, not tests packaged there.
Bit counts in the compiled ports, both computing the ν of Section 1. GCC manual — bit operation built-in functions documents __builtin_popcount, which "returns the number of 1-bits in x"; Java — java.lang.Integer documents Integer.bitCount(int), the one-bits of the two's complement representation.

Problem 315 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    int from = 10000000;
    int to = 20000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--from=", options.from) ||
            parse_int_after_prefix(arg, "--to=", options.to)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.from >= 2 && options.to > options.from;
}

std::array<int, 10> digit_masks() {
    // Segment order: top, middle, bottom, top-left, top-right, bottom-left, bottom-right.
    constexpr int T = 1 << 0;
    constexpr int M = 1 << 1;
    constexpr int B = 1 << 2;
    constexpr int TL = 1 << 3;
    constexpr int TR = 1 << 4;
    constexpr int BL = 1 << 5;
    constexpr int BR = 1 << 6;

    return {
        T | B | TL | TR | BL | BR,          // 0
        TR | BR,                            // 1
        T | M | B | TR | BL,                // 2
        T | M | B | TR | BR,                // 3
        M | TL | TR | BR,                   // 4
        T | M | B | TL | BR,                // 5
        T | M | B | TL | BL | BR,           // 6
        T | TL | TR | BR,                   // 7 (4 segments in this display style)
        T | M | B | TL | TR | BL | BR,      // 8
        T | M | B | TL | TR | BR            // 9
    };
}

int digit_sum(int n) {
    int s = 0;
    while (n > 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}

std::vector<int> digital_root_chain(int n) {
    std::vector<int> chain;
    while (true) {
        chain.push_back(n);
        if (n < 10) {
            break;
        }
        n = digit_sum(n);
    }
    return chain;
}

int segment_count_number(int n, const std::array<int, 10>& masks) {
    int total = 0;
    while (n > 0) {
        total += __builtin_popcount(static_cast<unsigned>(masks[static_cast<std::size_t>(n % 10)]));
        n /= 10;
    }
    return total;
}

int transition_cost(int from, int to, const std::array<int, 10>& masks) {
    int cost = 0;
    while (from > 0 || to > 0) {
        const int a = (from > 0) ? masks[static_cast<std::size_t>(from % 10)] : 0;
        const int b = (to > 0) ? masks[static_cast<std::size_t>(to % 10)] : 0;
        cost += __builtin_popcount(static_cast<unsigned>(a ^ b));
        from /= 10;
        to /= 10;
    }
    return cost;
}

int sam_cost(const std::vector<int>& chain, const std::array<int, 10>& masks) {
    int cost = 0;
    for (int value : chain) {
        cost += 2 * segment_count_number(value, masks);
    }
    return cost;
}

int max_cost(const std::vector<int>& chain, const std::array<int, 10>& masks) {
    int cost = 0;
    cost += transition_cost(0, chain.front(), masks);
    for (std::size_t i = 1; i < chain.size(); ++i) {
        cost += transition_cost(chain[i - 1], chain[i], masks);
    }
    cost += transition_cost(chain.back(), 0, masks);
    return cost;
}

i64 solve(const int from, const int to) {
    const auto masks = digit_masks();

    std::vector<std::uint8_t> is_prime(static_cast<std::size_t>(to), 1U);
    is_prime[0] = 0U;
    if (to > 1) {
        is_prime[1] = 0U;
    }
    for (int p = 2; static_cast<long long>(p) * p < to; ++p) {
        if (is_prime[static_cast<std::size_t>(p)] == 0U) {
            continue;
        }
        for (int q = p * p; q < to; q += p) {
            is_prime[static_cast<std::size_t>(q)] = 0U;
        }
    }

    i64 total_diff = 0;
    for (int p = from; p < to; ++p) {
        if (is_prime[static_cast<std::size_t>(p)] == 0U) {
            continue;
        }
        const auto chain = digital_root_chain(p);
        total_diff += static_cast<i64>(sam_cost(chain, masks) - max_cost(chain, masks));
    }
    return total_diff;
}

bool run_checkpoints() {
    const auto masks = digit_masks();
    {
        const auto chain = digital_root_chain(137);
        const int sam = sam_cost(chain, masks);
        const int mx = max_cost(chain, masks);
        if (sam != 40 || mx != 30) {
            std::cerr << "Checkpoint failed for 137 sample transitions" << '\n';
            return false;
        }
    }
    {
        const auto chain = digital_root_chain(7);
        if (sam_cost(chain, masks) != max_cost(chain, masks)) {
            std::cerr << "Checkpoint failed for single-digit transition equivalence" << '\n';
            return false;
        }
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.from, options.to) << '\n';
    return 0;
}

Python

def solve():
    FROM = 10000000
    TO = 20000000

    # Segment masks: T, M, B, TL, TR, BL, BR
    masks = [
        0b1111101,  # 0: T|B|TL|TR|BL|BR
        0b1010000,  # 1: TR|BR
        0b0110110,  # 2: T|M|B|TR|BL
        0b1110100,  # 3: T|M|B|TR|BR
        0b1011010,  # 4: M|TL|TR|BR
        0b1101100,  # 5: T|M|B|TL|BR
        0b1101110,  # 6: T|M|B|TL|BL|BR
        0b1011001,  # 7: T|TL|TR|BR (4-seg style)
        0b1111111,  # 8: all
        0b1111100,  # 9: T|M|B|TL|TR|BR
    ]

    # Wait, let me re-derive from the C++ code carefully
    T = 1; M = 2; B = 4; TL = 8; TR = 16; BL = 32; BR = 64
    masks = [
        T|B|TL|TR|BL|BR,       # 0
        TR|BR,                  # 1
        T|M|B|TR|BL,           # 2
        T|M|B|TR|BR,           # 3
        M|TL|TR|BR,            # 4
        T|M|B|TL|BR,           # 5
        T|M|B|TL|BL|BR,       # 6
        T|TL|TR|BR,            # 7
        T|M|B|TL|TR|BL|BR,    # 8
        T|M|B|TL|TR|BR,       # 9
    ]

    def popcount(x):
        return bin(x).count('1')

    def digit_sum(n):
        s = 0
        while n > 0:
            s += n % 10
            n //= 10
        return s

    def digital_root_chain(n):
        chain = []
        while True:
            chain.append(n)
            if n < 10:
                break
            n = digit_sum(n)
        return chain

    def seg_count(n):
        total = 0
        while n > 0:
            total += popcount(masks[n % 10])
            n //= 10
        return total

    def transition_cost(fr, to):
        cost = 0
        while fr > 0 or to > 0:
            a = masks[fr % 10] if fr > 0 else 0
            b = masks[to % 10] if to > 0 else 0
            cost += popcount(a ^ b)
            fr //= 10
            to //= 10
        return cost

    def sam_cost(chain):
        return sum(2 * seg_count(v) for v in chain)

    def max_cost(chain):
        cost = transition_cost(0, chain[0])
        for i in range(1, len(chain)):
            cost += transition_cost(chain[i-1], chain[i])
        cost += transition_cost(chain[-1], 0)
        return cost

    # Sieve primes
    is_prime = bytearray(b'\x01' * TO)
    is_prime[0] = 0
    is_prime[1] = 0
    p = 2
    while p * p < TO:
        if is_prime[p]:
            is_prime[p*p::p] = bytearray(len(is_prime[p*p::p]))
        p += 1

    total_diff = 0
    for p in range(FROM, TO):
        if not is_prime[p]:
            continue
        chain = digital_root_chain(p)
        total_diff += sam_cost(chain) - max_cost(chain)

    return str(total_diff)

if __name__ == '__main__':
    print(solve())

Java

public class Euler315 {
    static int[] digitMasks() {
        int T = 1 << 0;
        int M = 1 << 1;
        int B = 1 << 2;
        int TL = 1 << 3;
        int TR = 1 << 4;
        int BL = 1 << 5;
        int BR = 1 << 6;

        return new int[] {
                T | B | TL | TR | BL | BR,
                TR | BR,
                T | M | B | TR | BL,
                T | M | B | TR | BR,
                M | TL | TR | BR,
                T | M | B | TL | BR,
                T | M | B | TL | BL | BR,
                T | TL | TR | BR,
                T | M | B | TL | TR | BL | BR,
                T | M | B | TL | TR | BR
        };
    }

    static int digitSum(int n) {
        int s = 0;
        while (n > 0) {
            s += n % 10;
            n /= 10;
        }
        return s;
    }

    static int segmentCountNumber(int n, int[] masks) {
        int total = 0;
        while (n > 0) {
            total += Integer.bitCount(masks[n % 10]);
            n /= 10;
        }
        return total;
    }

    static int transitionCost(int from, int to, int[] masks) {
        int cost = 0;
        while (from > 0 || to > 0) {
            int a = (from > 0) ? masks[from % 10] : 0;
            int b = (to > 0) ? masks[to % 10] : 0;
            cost += Integer.bitCount(a ^ b);
            from /= 10;
            to /= 10;
        }
        return cost;
    }

    public static String solve() {
        int from = 10000000;
        int to = 20000000;
        int[] masks = digitMasks();

        byte[] isPrime = new byte[to];
        for (int i = 2; i < to; i++)
            isPrime[i] = 1;
        for (int p = 2; (long) p * p < to; ++p) {
            if (isPrime[p] == 1) {
                for (int q = p * p; q < to; q += p) {
                    isPrime[q] = 0;
                }
            }
        }

        long totalDiff = 0;
        int[] chain = new int[16];

        for (int p = from; p < to; ++p) {
            if (isPrime[p] == 0)
                continue;

            int cSize = 0;
            int curr = p;
            while (true) {
                chain[cSize++] = curr;
                if (curr < 10)
                    break;
                curr = digitSum(curr);
            }

            int samCost = 0;
            for (int i = 0; i < cSize; i++) {
                samCost += 2 * segmentCountNumber(chain[i], masks);
            }

            int mxCost = transitionCost(0, chain[0], masks);
            for (int i = 1; i < cSize; i++) {
                mxCost += transitionCost(chain[i - 1], chain[i], masks);
            }
            mxCost += transitionCost(chain[cSize - 1], 0, masks);

            totalDiff += (samCost - mxCost);
        }

        return String.valueOf(totalDiff);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}