Solution

Answer: 13625242

Let each decimal digit be represented by a 7-segment bitmask.

A digital-root chain for a number $n$ is

$$n \to s(n) \to s(s(n)) \to \cdots$$

where $s(n)$ is the sum of decimal digits of $n$, until a one-digit number is reached.

For example:

$$137 \to 11 \to 2$$

The key observation is that both clocks differ only in how they transition between consecutive displays.

1. Mathematical analysis

Seven-segment representation

We encode each digit as a 7-bit mask.

Using the segment numbering

$$\begin{matrix} &0& \ 1&&2\ &3& \ 4&&5\ &6& \end{matrix}$$

the masks are:

Digit	Mask	Segments lit
0	0x77	6
1	0x24	2
2	0x5D	5
3	0x6D	5
4	0x2E	4
5	0x6B	5
6	0x7B	6
7	0x27	4
8	0x7F	7
9	0x6F	6

The number of lit segments is simply the popcount (number of set bits).

Sam’s clock

Sam always:

turns an entire number on,
later turns the entire number off.

Therefore if a displayed number $x$ uses $L(x)$ lit segments, Sam spends

$$2L(x)$$

transitions on that display.

Hence for a digital-root chain

$$x_0,x_1,\dots,x_k$$

Sam uses

$$S = 2\sum_{i=0}^k L(x_i)$$

Max’s clock

Max only changes segments that differ between consecutive displays.

If $M(a)$ and $M(b)$ are the bitmasks for two displays, then the number of transitions needed is

$$\operatorname{popcount}(M(a)\oplus M(b))$$

because XOR marks exactly the segments that change state.

Thus Max’s total is:

turn on first number,
XOR transitions between consecutive numbers,
turn off final number.

So:

$$T = L(x_0) + \sum_{i=0}^{k-1} \operatorname{popcount}(M(x_i)\oplus M(x_{i+1})) + L(x_k)$$

Prime range

We must evaluate this for all primes

$$10^7 \le p < 2\cdot 10^7$$

A sieve of Eratosthenes is easily fast enough.

2. Python implementation

from math import isqrt

# Seven-segment bitmasks
SEG = {
    0: 0x77,
    1: 0x24,
    2: 0x5D,
    3: 0x6D,
    4: 0x2E,
    5: 0x6B,
    6: 0x7B,
    7: 0x27,
    8: 0x7F,
    9: 0x6F,
}

def digit_sum(n):
    """Sum of decimal digits."""
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def segments_of_number(n):
    """
    Pack the seven-segment masks of all digits into one integer.
    Each digit gets 8 bits.
    """
    result = 0
    shift = 0

    while n > 0:
        result |= SEG[n % 10] << shift
        n //= 10
        shift += 8

    return result

def sam_cost(n):
    """Transitions used by Sam."""
    segs = segments_of_number(n)
    cost = 2 * segs.bit_count()

    if n > 9:
        cost += sam_cost(digit_sum(n))

    return cost

def max_cost(n, previous=0):
    """Transitions used by Max."""
    segs = segments_of_number(n)

    # Only changed segments toggle
    cost = (segs ^ previous).bit_count()

    if n > 9:
        cost += max_cost(digit_sum(n), segs)
    else:
        # Turn final display off
        cost += segs.bit_count()

    return cost

def sieve(limit):
    """Return list of primes <= limit."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for p in range(2, isqrt(limit) + 1):
        if is_prime[p]:
            step = p
            start = p * p
            for k in range(start, limit + 1, step):
                is_prime[k] = False

    return is_prime

A = 10_000_000
B = 20_000_000

prime = sieve(B)

answer = 0

for p in range(A, B + 1):
    if prime[p]:
        answer += sam_cost(p) - max_cost(p)

print(answer)

3. Code walkthrough

`segments_of_number`

Each digit contributes one 7-bit mask.

For example:

$$137$$

becomes

$$M(7)\ |\ (M(3)\ll 8)\ |\ (M(1)\ll 16)$$

This lets us compare entire displays with one XOR.

`sam_cost`

For each displayed value:

2 * segs.bit_count()

counts turning all segments on and off.

Then we recurse on the digit sum.

For $137$:

$137$: $2(2+5+4)=22$
$11$: $2(2+2)=8$
$2$: $2(5)=10$

Total:

$$40$$

`max_cost`

The transition count between displays is:

(segs ^ previous).bit_count()

because XOR detects exactly the changed segments.

For $137$:

empty $\to 137$: 11
$137 \to 11$: 7
$11 \to 2$: 7
$2 \to$ empty: 5

Total:

$$30$$

matching the problem statement.

4. Final verification

The computation:

uses the exact seven-segment transitions,
reproduces the sample values $40$ and $30$,
efficiently handles all primes in the interval.

The final total difference is:

$$13{,}625{,}242$$

Answer: 13625242

Project Euler Problem 315