Project Euler

3-Like Numbers

For a positive integer n, define f(n) as the number of non-empty substrings of n (in decimal) that are divisible by 3. Call n 3-like if f(n) equiv 0 (mod 3). Let F(d) count the d -digit 3-like numb...

Source sync Apr 19, 2026

Problem #0706

Level Level 19

Solved By 700

Languages C++, Python

Answer 884837055

Length 458 words

modular_arithmeticlinear_algebradynamic_programming

For a positive integer $n$, define $f(n)$ to be the number of non-empty substrings of $n$ that are divisible by $3$. For example, the string "2573" has $10$ non-empty substrings, three of which represent numbers that are divisible by $3$, namely $57$, $573$ and $3$. So $f(2573) = 3$.

If $f(n)$ is divisible by $3$ then we say that $n$ is $3$-like.

Define $F(d)$ to be how many $d$ digit numbers are $3$-like. For example, $F(2) = 30$ and $F(6) = 290898$.

Find $F(10^5)$. Give your answer modulo $1\,000\,000\,007$.

Problem 706: 3-Like Numbers

Mathematical Foundation

Lemma 1 (Substring Divisibility via Prefix Sums). A substring from position $i$ to position $j$ (1-indexed) of a number with digits $d_1 d_2 \cdots d_k$ is divisible by 3 if and only if $S_j \equiv S_{i-1} \pmod{3}$ , where $S_r = \sum_{\ell=1}^{r} d_\ell$ is the prefix digit sum and $S_0 = 0$ .

Proof. A number is divisible by 3 iff its digit sum is divisible by 3. The digit sum of the substring from $i$ to $j$ is $S_j - S_{i-1}$ , which is divisible by 3 iff $S_j \equiv S_{i-1} \pmod{3}$ . $\square$

Theorem 1 (Counting Formula). Let $c_r = |\{k \in \{0, 1, \ldots, d\} : S_k \equiv r \pmod{3}\}|$ for $r = 0, 1, 2$ , where $c_0 + c_1 + c_2 = d + 1$ . Then

f(n) = \binom{c_0}{2} + \binom{c_1}{2} + \binom{c_2}{2}.

Proof. Each pair $(i-1, j)$ with $0 \le i-1 < j \le d$ and $S_j \equiv S_{i-1} \pmod{3}$ corresponds to a substring divisible by 3. The number of such pairs with $S_{i-1} \equiv S_j \equiv r$ is $\binom{c_r}{2}$ . Summing over $r = 0, 1, 2$ gives the total. $\square$

Lemma 2 (Reduction Modulo 3). For $c \in \mathbb{Z}_{\ge 0}$ :

\binom{c}{2} \bmod 3 = \begin{cases} 0 & \text{if } c \equiv 0 \pmod{3}, \\ 0 & \text{if } c \equiv 1 \pmod{3}, \\ 1 & \text{if } c \equiv 2 \pmod{3}. \end{cases}

Proof. Direct computation: $\binom{c}{2} = c(c-1)/2$ . For $c \equiv 0$ : $c \equiv 0$ , so $3 \mid c(c-1)/2$ . For $c \equiv 1$ : $c-1 \equiv 0$ , so $3 \mid c(c-1)/2$ . For $c \equiv 2$ : $c(c-1)/2 \equiv 2 \cdot 1/2 \equiv 1 \pmod{3}$ . $\square$

Theorem 2 (State-Based DP with Matrix Exponentiation). The 3-like condition $f(n) \equiv 0 \pmod{3}$ depends only on $(c_0 \bmod 3, c_1 \bmod 3, c_2 \bmod 3)$ . This gives a state space of $3^3 = 27$ states. The transitions when appending a digit depend on the current prefix sum modulo 3 (which determines which $c_r$ to increment) and the digit’s residue modulo 3.

Proof. The current prefix sum modulo 3 is determined by which counter was last incremented. Appending a digit $d$ changes the prefix sum from $s$ to $(s + d) \bmod 3$ , incrementing $c_{(s+d) \bmod 3}$ by 1. Since we track counters modulo 3, the new state is fully determined. Among digits 0—9, there are 4 with residue 0 (namely 0, 3, 6, 9), 3 with residue 1 (1, 4, 7), and 3 with residue 2 (2, 5, 8). The first digit excludes 0, but digit 0 has residue 0, so the first-digit distribution is (3, 3, 3) and subsequent digits use (4, 3, 3). This yields a $27 \times 27$ transition matrix $M$ that can be exponentiated. $\square$

Theorem 3 (Final Count). $F(d)$ is obtained by:

Setting the initial state vector $\mathbf{v}_0$ from the first digit (which is nonzero).
Computing $\mathbf{v}_d = M^{d-1} \mathbf{v}_0$ .
Summing entries of $\mathbf{v}_d$ corresponding to accepting states (those with $\binom{c_0}{2} + \binom{c_1}{2} + \binom{c_2}{2} \equiv 0 \pmod{3}$ ).

Proof. The matrix power $M^{d-1}$ propagates the state distribution through $d - 1$ digit appends (after the first digit). The accepting condition is evaluated on the final state using Lemma 2. $\square$

Editorial

For a positive integer n, f(n) = number of non-empty substrings divisible by 3. n is 3-like if f(n) is divisible by 3. F(d) = count of d-digit 3-like numbers. Find F(10^5) mod 1_000_000_007. We state: (c0 mod 3, c1 mod 3, c2 mod 3) — 27 states. We then initial: S_0 = 0, so c0 = 1, c1 = 0, c2 = 0. Finally, build 27x27 transition matrix M for one digit (digits 0-9).

Pseudocode

State: (c0 mod 3, c1 mod 3, c2 mod 3) — 27 states
Initial: S_0 = 0, so c0 = 1, c1 = 0, c2 = 0
prefix_sum = 0
Build 27x27 transition matrix M for one digit (digits 0-9)
Digit residues: {0,3,6,9}→0, {1,4,7}→1, {2,5,8}→2
Counts: (4, 3, 3)
Increment c_{new_s} mod 3
Handle first digit: only digits 1-9 (residues: 3 each)
Initialize state after first digit + S_0
After S_0=0: c0=1. First digit sets S_1 = r, so c_r += 1
Apply M^{d-1} to v
Sum accepting states

Complexity Analysis

Time: $O(27^3 \cdot \log d) = O(\log d)$ since the matrix size is a constant ( $27 \times 27$ ) and we use fast matrix exponentiation with $O(\log d)$ squarings.
Space: $O(27^2) = O(1)$ for the transition matrix.

Answer

\boxed{884837055}

C++ project_euler/problem_706/solution.cpp

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

const long long MOD = 1000000007;

// State: (c0 mod 3, c1 mod 3, c2 mod 3) -> 27 states
// But we also need to know current prefix sum mod 3 to determine which counter to increment.
// current prefix sum mod 3 is determined by which c_r we last incremented.
// Actually, we need to track prefix_sum mod 3 explicitly as part of the state.
// State: (c0 mod 3, c1 mod 3, c2 mod 3, prefix_sum mod 3) but prefix_sum mod 3
// is not independent - no, it tells us which counter gets incremented next.
// Actually prefix_sum is the current S_k mod 3. When we add digit d, new S = (S + d) mod 3,
// and we increment c_{new_S}. So we need to track current S mod 3.
// Total states: 27 * 3 = 81

typedef vector<vector<long long>> Matrix;

int stateIndex(int c0, int c1, int c2, int s) {
    return ((c0 * 3 + c1) * 3 + c2) * 3 + s;
}

Matrix multiply(const Matrix& A, const Matrix& B, int n) {
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            if (A[i][k] == 0) continue;
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        }
    return C;
}

Matrix matpow(Matrix M, long long p, int n) {
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;
    while (p > 0) {
        if (p & 1) result = multiply(result, M, n);
        M = multiply(M, M, n);
        p >>= 1;
    }
    return result;
}

int main() {
    const int N = 81; // 27 * 3
    const long long D = 100000; // 10^5 digits

    // Build transition matrix
    Matrix T(N, vector<long long>(N, 0));

    // digits mod 3: 0,3,6,9 -> residue 0 (4 digits)
    //               1,4,7   -> residue 1 (3 digits)
    //               2,5,8   -> residue 2 (3 digits)
    int digitCount[3] = {4, 3, 3};

    for (int c0 = 0; c0 < 3; c0++)
        for (int c1 = 0; c1 < 3; c1++)
            for (int c2 = 0; c2 < 3; c2++)
                for (int s = 0; s < 3; s++) {
                    int from = stateIndex(c0, c1, c2, s);
                    // Add a digit with residue r (0,1,2)
                    for (int r = 0; r < 3; r++) {
                        int newS = (s + r) % 3;
                        int nc0 = c0, nc1 = c1, nc2 = c2;
                        if (newS == 0) nc0 = (nc0 + 1) % 3;
                        else if (newS == 1) nc1 = (nc1 + 1) % 3;
                        else nc2 = (nc2 + 1) % 3;
                        int to = stateIndex(nc0, nc1, nc2, newS);
                        T[to][from] = (T[to][from] + digitCount[r]) % MOD;
                    }
                }

    // Initial state: c0=1 (for S_0=0), c1=0, c2=0, prefix_sum=0
    // But first digit can't be 0 (d-digit number), so we handle first digit separately
    // First digit: 1-9
    // digit residues for 1-9: residue 0: {3,6,9} -> 3 digits
    //                          residue 1: {1,4,7} -> 3 digits
    //                          residue 2: {2,5,8} -> 3 digits

    vector<long long> state(N, 0);
    // Initial: c0=1 (S_0=0 counted), c1=0, c2=0, current prefix_sum=0
    // After first digit d with residue r:
    // new prefix_sum = r, increment c_r
    for (int r = 0; r < 3; r++) {
        int c0 = 1, c1 = 0, c2 = 0;
        int newS = r;
        if (newS == 0) c0 = (c0 + 1) % 3; // c0 becomes 2
        else if (newS == 1) c1 = 1;
        else c2 = 1;
        int idx = stateIndex(c0 % 3, c1, c2, newS);
        int cnt = 3; // 3 digits for each residue among 1-9
        state[idx] = (state[idx] + cnt) % MOD;
    }

    // Apply transition matrix D-1 times for remaining digits
    if (D > 1) {
        Matrix Tp = matpow(T, D - 1, N);
        vector<long long> newState(N, 0);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                newState[i] = (newState[i] + Tp[i][j] * state[j]) % MOD;
        state = newState;
    }

    // Sum states where binom(c0,2) + binom(c1,2) + binom(c2,2) = 0 mod 3
    // binom_mod3[c mod 3]: c=0->0, c=1->0, c=2->1
    int binom_mod3[3] = {0, 0, 1};

    long long answer = 0;
    for (int c0 = 0; c0 < 3; c0++)
        for (int c1 = 0; c1 < 3; c1++)
            for (int c2 = 0; c2 < 3; c2++) {
                int val = (binom_mod3[c0] + binom_mod3[c1] + binom_mod3[c2]) % 3;
                if (val == 0) {
                    for (int s = 0; s < 3; s++) {
                        int idx = stateIndex(c0, c1, c2, s);
                        answer = (answer + state[idx]) % MOD;
                    }
                }
            }

    cout << answer << endl;
    return 0;
}

Python project_euler/problem_706/solution.py

"""
Project Euler Problem 706: 3-Like Numbers

For a positive integer n, f(n) = number of non-empty substrings divisible by 3.
n is 3-like if f(n) is divisible by 3.
F(d) = count of d-digit 3-like numbers.
Find F(10^5) mod 1_000_000_007.
"""

MOD = 1_000_000_007

def mat_mul(A, B, n):
    C = [[0]*n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0:
                continue
            for j in range(n):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def mat_pow(M, p, n):
    result = [[0]*n for _ in range(n)]
    for i in range(n):
        result[i][i] = 1
    while p > 0:
        if p & 1:
            result = mat_mul(result, M, n)
        M = mat_mul(M, M, n)
        p >>= 1
    return result

def solve():
    D = 100000  # 10^5
    N = 81  # 27 states * 3 prefix sums

    def idx(c0, c1, c2, s):
        return ((c0 * 3 + c1) * 3 + c2) * 3 + s

    # Digit counts by residue mod 3: {0,3,6,9}->4, {1,4,7}->3, {2,5,8}->3
    digit_count = [4, 3, 3]

    # Build transition matrix
    T = [[0]*N for _ in range(N)]
    for c0 in range(3):
        for c1 in range(3):
            for c2 in range(3):
                for s in range(3):
                    fr = idx(c0, c1, c2, s)
                    for r in range(3):
                        ns = (s + r) % 3
                        nc = [c0, c1, c2]
                        nc[ns] = (nc[ns] + 1) % 3
                        to = idx(nc[0], nc[1], nc[2], ns)
                        T[to][fr] = (T[to][fr] + digit_count[r]) % MOD

    # Initial state after first digit (1-9, 3 of each residue class)
    state = [0] * N
    for r in range(3):
        c = [1, 0, 0]  # c0=1 for S_0=0
        c[r] = (c[r] + 1) % 3
        i = idx(c[0], c[1], c[2], r)
        state[i] = (state[i] + 3) % MOD

    # Apply transition D-1 times
    if D > 1:
        Tp = mat_pow(T, D - 1, N)
        new_state = [0] * N
        for i in range(N):
            for j in range(N):
                new_state[i] = (new_state[i] + Tp[i][j] * state[j]) % MOD
        state = new_state

    # binom(c, 2) mod 3: c%3=0->0, c%3=1->0, c%3=2->1
    bmod3 = [0, 0, 1]

    answer = 0
    for c0 in range(3):
        for c1 in range(3):
            for c2 in range(3):
                if (bmod3[c0] + bmod3[c1] + bmod3[c2]) % 3 == 0:
                    for s in range(3):
                        answer = (answer + state[idx(c0, c1, c2, s)]) % MOD

    print(answer)

solve()