Problem 315: Digital Root Clocks

Mathematical Foundation

Definition (Segment Encoding). Each decimal digit is represented by a 7-bit mask over segments $\{a, b, c, d, e, f, g\}$:

Note: digit 7 uses 4 segments (including the top-left vertical $f$), per the Project Euler specification.

Definition (Segment Count Functions). For a number $n$ with digits $d_1 d_2 \cdots d_k$, define:

• $\text{seg}(n) = \sum_{i=1}^{k} |M(d_i)|$, the total number of active segments,
• $M(d)$ = bitmask of digit $d$.

Lemma 1 (Sam’s Cost). For the digital root chain $n_0, n_1, \ldots, n_K$ (where $n_0 = p$, $n_K$ is a single digit), Sam’s total segment transitions are:

Proof. Sam turns on all segments of $n_i$ (cost $\text{seg}(n_i)$), then turns them all off (cost $\text{seg}(n_i)$), for each $i = 0, 1, \ldots, K$. Total: $2\sum_i \text{seg}(n_i)$. $\square$

Lemma 2 (Max’s Cost). Max’s total segment transitions are:

where $\text{ham}(n_i, n_{i+1})$ is the number of segments that differ between the right-aligned digit-by-digit bitmask representations of $n_i$ and $n_{i+1}$ (the Hamming distance of the composite bitmasks, padding shorter numbers with zero on the left).

Proof. Max initially turns on $n_0$ from blank (cost $\text{seg}(n_0)$). At each transition $n_i \to n_{i+1}$, Max toggles only the differing segments (cost $\text{ham}(n_i, n_{i+1})$). Finally, Max turns off $n_K$ to blank (cost $\text{seg}(n_K)$). $\square$

Theorem (Difference Identity). For any two bitmasks $A$ and $B$:

where $\oplus$ is XOR (symmetric difference) and $\wedge$ is AND (intersection). Consequently:

where $\text{common}(n_i, n_{i+1})$ is the number of segments shared between consecutive displays (computed digit-by-digit, right-aligned).

Proof. For bitmasks $A, B \subseteq \{0,1\}^7$: every bit is either in $A \cap B$, in $A \setminus B$, or in $B \setminus A$. The XOR counts bits in exactly one of $A, B$; the AND counts bits in both. So $|A| + |B| = |A \oplus B| + 2|A \wedge B|$.

Now expand the difference:

Rewriting: $\text{Sam} - \text{Max} = \text{seg}(n_0) + 2\sum_{i=1}^{K-1}\text{seg}(n_i) + \text{seg}(n_K) - \sum_{i=0}^{K-1}\text{ham}(n_i, n_{i+1})$.

Using $\text{seg}(n_i) + \text{seg}(n_{i+1}) = \text{ham}(n_i, n_{i+1}) + 2\,\text{common}(n_i, n_{i+1})$, we telescope:

Editorial

For primes p in (10^7, 210^7), compute the total difference Sam(p) - Max(p) where: The difference at each transition = 2 * (common segments). Seven-segment display: a | | f b |g| | | e c |d|. We sieve primes in (10^7, 210^7) using Sieve of Eratosthenes. We then iterate over each prime p. Finally, return global sum.

Pseudocode

Input: primes p in (10^7, 2*10^7)
Output: sum of Sam(p) - Max(p) over all such primes
Sieve primes in (10^7, 2*10^7) using Sieve of Eratosthenes
Precompute seg_count[d] and bitmask[d] for d = 0..9
For each prime p:
Return global sum

Complexity Analysis

• Time: $O(N \log \log N)$ for the sieve where $N = 2 \times 10^7$. Per prime: $O(\log p)$ for the chain (at most 3—4 steps, each with $\le 8$ digits). Total: $O(N \log \log N)$.
• Space: $O(N)$ for the sieve.

Answer

#include <bits/stdc++.h>
using namespace std;

// Problem 315: Digital Root Clocks
// For each prime p in (10^7, 2*10^7), compute Sam(p) - Max(p)
// where Sam and Max display the digital root chain on 7-segment displays.
// Sam turns everything off then on; Max only changes differing segments.
// Difference = 2 * (common segments at each transition).

int main() {
    const int LO = 10000000;   // 10^7
    const int HI = 20000000;   // 2*10^7

    // Segment bitmasks for digits 0-9 (matching the Project Euler display)
    // Bits: a=0(top), b=1(top-right), c=2(bot-right), d=3(bot), e=4(bot-left), f=5(top-left), g=6(mid)
    // Key: digit 7 has 4 segments (a,b,c,f) including top-left vertical
    // 0:a,b,c,d,e,f(6) 1:b,c(2) 2:a,b,d,e,g(5) 3:a,b,c,d,g(5) 4:b,c,f,g(4)
    // 5:a,c,d,f,g(5) 6:a,c,d,e,f,g(6) 7:a,b,c,f(4) 8:all(7) 9:a,b,c,d,f,g(6)
    const int seg[10] = {0x3f, 0x06, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x27, 0x7f, 0x6f};

    // Precompute segment count and common segments between digits
    int seg_count[10];
    int common[10][10];
    for (int i = 0; i < 10; i++) {
        seg_count[i] = __builtin_popcount(seg[i]);
        for (int j = 0; j < 10; j++) {
            common[i][j] = __builtin_popcount(seg[i] & seg[j]);
        }
    }

    // Function to compute total segments for a number
    auto total_segs = [&](int n) -> int {
        if (n == 0) return seg_count[0];
        int s = 0;
        while (n > 0) {
            s += seg_count[n % 10];
            n /= 10;
        }
        return s;
    };

    // Function to compute common segments between two numbers
    // (digit by digit, right-aligned; missing digits have 0 common)
    auto common_segs = [&](int a, int b) -> int {
        int s = 0;
        while (a > 0 && b > 0) {
            s += common[a % 10][b % 10];
            a /= 10;
            b /= 10;
        }
        return s;
    };

    // Function to compute digit sum
    auto digit_sum = [](int n) -> int {
        int s = 0;
        while (n > 0) {
            s += n % 10;
            n /= 10;
        }
        return s;
    };

    // Sieve of Eratosthenes
    vector<bool> is_composite(HI, false);
    for (int i = 2; (long long)i * i < HI; i++) {
        if (!is_composite[i]) {
            for (int j = i * i; j < HI; j += i) {
                is_composite[j] = true;
            }
        }
    }

    long long answer = 0;

    for (int p = LO + 1; p < HI; p++) {
        if (is_composite[p]) continue;

        // Compute the digital root chain and accumulate 2 * common segments
        // Chain: p -> digit_sum(p) -> digit_sum(digit_sum(p)) -> ... -> single digit

        int current = p;
        while (current >= 10) {
            int next = digit_sum(current);
            answer += 2 * common_segs(current, next);
            current = next;
        }
        // The chain also includes the initial turn-on and final turn-off,
        // but these are the same for Sam and Max, so they don't contribute
        // to the difference.
    }

    cout << answer << endl;

    return 0;
}

"""
Problem 315: Digital Root Clocks

For primes p in (10^7, 2*10^7), compute the total difference
Sam(p) - Max(p) where:
- Sam turns off all segments then turns on new ones at each step
- Max only changes segments that differ

The difference at each transition = 2 * (common segments).

Seven-segment display:
    _a_
   |   |
   f   b
   |_g_|
   |   |
   e   c
   |_d_|
"""

# Segment bitmasks: a=0(top), b=1(top-right), c=2(bot-right), d=3(bot), e=4(bot-left), f=5(top-left), g=6(mid)
# NOTE: In the Project Euler display, digit 7 has 4 segments (includes top-left f).
SEGMENTS = {
    0: 0x3f,  # a,b,c,d,e,f     = 6 segments
    1: 0x06,  # b,c             = 2 segments
    2: 0x5b,  # a,b,d,e,g       = 5 segments
    3: 0x4f,  # a,b,c,d,g       = 5 segments
    4: 0x66,  # b,c,f,g         = 4 segments
    5: 0x6d,  # a,c,d,f,g       = 5 segments
    6: 0x7d,  # a,c,d,e,f,g     = 6 segments
    7: 0x27,  # a,b,c,f         = 4 segments
    8: 0x7f,  # a,b,c,d,e,f,g   = 7 segments
    9: 0x6f,  # a,b,c,d,f,g     = 6 segments
}

SEG_COUNT = {d: bin(SEGMENTS[d]).count('1') for d in range(10)}

def popcount(x):
    """Count set bits."""
    return bin(x).count('1')

def common_segments(a, b):
    """Count common segments between displays of numbers a and b."""
    total = 0
    while a > 0 and b > 0:
        total += popcount(SEGMENTS[a % 10] & SEGMENTS[b % 10])
        a //= 10
        b //= 10
    return total

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

def solve():
    LO = 10_000_000
    HI = 20_000_000

    # Sieve of Eratosthenes
    is_prime = bytearray([1]) * HI
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(HI**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))

    answer = 0
    for p in range(LO + 1, HI):
        if not is_prime[p]:
            continue

        current = p
        while current >= 10:
            nxt = digit_sum(current)
            answer += 2 * common_segments(current, nxt)
            current = nxt

    print(answer)