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

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());
    }
}