Project Euler Problem 458: Permutations of Project

Mathematical Analysis

Approach: Complement + Transfer Matrix

Count “bad” strings (those containing a permutation of “project” as a substring), then subtract.

Actually, we use a state machine directly.

State Definition

At each position, track how many of the 7 distinct letters appear in the “current window” that could form part of a permutation. Specifically, the state represents the number of distinct letters seen in the last consecutive characters that are all distinct from each other.

State s (0 <= s <= 7): we have a “run” of s consecutive characters at the end that are all mutually distinct. When s = 7, a forbidden permutation substring has been formed.

Transitions from state s when adding character c:

• If c duplicates one of the s most recent distinct characters, the run is broken. The new state depends on how far back the duplicate is.
• If c is new (not among the last s characters), state becomes s+1.

Actually, the cleanest model:

State = number of distinct characters in the current suffix window that forms a “streak” of all-distinct characters. We track how many distinct chars are at the tail.

From state s, adding one of 7 characters:

• (7 - s) characters are “new” (not in the current window of s distinct chars): transition to s+1
• For each position k in {1, …, s}, exactly 1 character duplicates the k-th from the end: this resets the window. If we duplicate position k (counting from end), the new streak length is k-1 (the last k-1 characters are still all distinct). Wait — if we duplicate position k from the end (1-indexed), then the longest suffix of all-distinct chars has length k-1… No, it’s more subtle.

The correct transition: if we duplicate the character that is i-th from the end (i=1 means the immediately preceding character), then the new run of distinct characters starting from the current position backwards is… we need to restart.

The standard approach: Define state s = number of distinct consecutive characters at the end. When adding char c:

• c matches one of the last s chars. Say it matches position i from the end (1-indexed). Then the new distinct suffix = (i-1) + 1? No…

  Actually if c equals the char at position i from the end, the new window of distinct chars is the last (i-1) chars plus c. But c equals the i-th from end, so among positions {end-(i-1), …, end-1, new}, the char at new = char at end-i+1…

  Hmm, the simplest correct formulation: if c duplicates the character that is at position i from the right (within the window of s distinct chars), then the longest suffix of distinct characters ending at the new position has length… Since c is a duplicate of position i, and positions 1..i-1 are all distinct from each other and from c (since the window of s was all-distinct), the new distinct suffix length = i (those i-1 chars plus c? No, c is same as position i).

  Actually: positions (from right): 1=newest, 2, …, s=oldest in window. The duplicate is at position i. The new char = char at pos i. New suffix of distinct chars from the right: just the new char alone might not be enough…

  The key insight: after adding c which equals position i from end:

  • The last 1 char (c) is always distinct.
  • The last 2 chars: c, prev_1. These are distinct iff prev_1 != c, i.e., i != 1.
  • …continuing…
  • The last j chars for j <= i-1: these are c, prev_1, …, prev_{j-1}. All distinct since within the original window they were distinct, and none equals c (only pos i does).
  • The last i chars: c, prev_1, …, prev_{i-1}. But c = prev_{i-1}? No, c = position i from old end, which is prev_i in the original. Wait, I need to be more careful.

  After adding c: the sequence ends with …, old_s, old_{s-1}, …, old_1, c. c = old_i. The suffix of distinct chars:

  • Length 1: {c} — always fine.
  • Length 2: {old_1, c} — fine if old_1 != c, i.e., i != 1.
  • Length k: {old_{k-1}, …, old_1, c} — all distinct if c not in {old_1,…,old_{k-1}}, i.e., i >= k. Since i >= k means old_i is not among old_1,…,old_{k-1}.
  • Length i: {old_{i-1}, …, old_1, c} — all distinct since c = old_i and old_i not in {old_1,…,old_{i-1}} (they were all distinct in original window).
  • Length i+1: {old_i, old_{i-1}, …, old_1, c} — but c = old_i, DUPLICATE!

  So the new state = i.

  Wait, that’s wrong. Let me re-index. Let old positions from RIGHT be: old_1 (rightmost), old_2, …, old_s (leftmost in window). c duplicates old_i.

  New sequence: …, old_s, …, old_1, c. Suffix distinct check from right: c, old_1, old_2, …

  • {c}: distinct. Length 1.
  • {c, old_1}: distinct iff i != 1.
  • {c, old_1, …, old_{k-1}}: distinct iff i > k-1, i.e., i >= k.
  • {c, old_1, …, old_{i-1}}: distinct since i >= i. Length = i.
  • {c, old_1, …, old_i}: NOT distinct since c = old_i.

  So new state = i.

For i = 1 (c = old_1): new state = 1. For i = 2: new state = 2. … For i = s: new state = s.

But wait: if c is NOT in the window (new char), state goes from s to s+1. There are (7-s) such chars. If c IS in the window at position i, there’s exactly 1 such char for each i. Total chars accounted for: (7-s) + s = 7. Correct!

Transition Matrix (8x8)

States 0 through 7. State 7 is absorbing (forbidden pattern found).

From state s (s < 7):

• To state s+1: (7 - s) ways
• To state i for i in {1, …, s}: 1 way each

From state 7 (absorbing): stays at 7 with 7 ways.

We want to count strings that never reach state 7.

Matrix Exponentiation

Build the 8x8 transition matrix M. Then the state vector after n characters is M^n * v0, where v0 = (1, 0, 0, …, 0) (start in state 0).

T(n) = 7^n - (M^n)[7][0] if we track the “bad” count.

Or equivalently: T(n) = sum of (M^n)[s][0] for s = 0..6.

Use matrix exponentiation mod 10^9 with O(8^3 * log n) = O(512 * 40) = trivial.

Transition matrix M (from -> to):

From state 0: to state 1 with 7 ways. From state 1: to state 1 with 1, to state 2 with 6. From state 2: to state 1 with 1, to state 2 with 1, to state 3 with 5. From state 3: to state 1 with 1, to state 2 with 1, to state 3 with 1, to state 4 with 4. From state 4: to state 1..4 with 1 each, to state 5 with 3. From state 5: to state 1..5 with 1 each, to state 6 with 2. From state 6: to state 1..6 with 1 each, to state 7 with 1. From state 7: to state 7 with 7. (absorbing)

Verification

T(7) = 7^7 - (number of length-7 strings with a permutation of “project” as substring) The only way a length-7 string has such a substring is if the entire string IS a permutation. So T(7) = 7^7 - 7! = 823543 - 5040 = 818503. Confirmed.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

/*
 * Project Euler Problem 458: Permutations of Project
 *
 * T(n) = number of strings of length n over {p,r,o,j,e,c,t} that do NOT
 * contain any permutation of "project" as a contiguous substring.
 *
 * T(7) = 7^7 - 7! = 818503.
 * Find T(10^12) mod 10^9.
 *
 * Approach: 8-state transfer matrix + matrix exponentiation.
 *
 * Compile: g++ -O2 -o solution solution.cpp
 */

#include <cstdio>
#include <cstring>
#include <cstdint>

typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1000000000LL;  // 10^9
const int SZ = 8;

struct Matrix {
    ll m[SZ][SZ];

    Matrix() { memset(m, 0, sizeof(m)); }

    static Matrix identity() {
        Matrix I;
        for (int i = 0; i < SZ; i++) I.m[i][i] = 1;
        return I;
    }

    Matrix operator*(const Matrix& B) const {
        Matrix C;
        for (int i = 0; i < SZ; i++)
            for (int k = 0; k < SZ; k++) {
                if (m[i][k] == 0) continue;
                for (int j = 0; j < SZ; j++)
                    C.m[i][j] = (C.m[i][j] + m[i][k] * B.m[k][j]) % MOD;
            }
        return C;
    }
};

Matrix mat_pow(Matrix base, ll exp) {
    Matrix result = Matrix::identity();
    while (exp > 0) {
        if (exp & 1) result = result * base;
        base = base * base;
        exp >>= 1;
    }
    return result;
}

/*
 * Build transition matrix M[to][from]:
 *
 * From state s (0 <= s <= 6):
 *   - To state s+1: (7-s) ways (new distinct char)
 *   - To state i for i=1..s: 1 way (duplicate of i-th from right)
 * From state 0:
 *   - To state 1: 7 ways
 * From state 7 (absorbing):
 *   - To state 7: 7 ways
 */
Matrix build_transition() {
    Matrix M;

    for (int s = 0; s < 7; s++) {
        M.m[s + 1][s] = 7 - s;  // new char
        for (int i = 1; i <= s; i++) {
            M.m[i][s] += 1;  // duplicate at position i
        }
    }
    M.m[7][7] = 7;  // absorbing

    return M;
}

int main() {
    ll n = 1000000000000LL;  // 10^12

    // Verify T(7)
    {
        Matrix M = build_transition();
        Matrix M7 = mat_pow(M, 7);
        ll t7 = 0;
        for (int s = 0; s < 7; s++)
            t7 = (t7 + M7.m[s][0]) % MOD;
        printf("T(7) mod 10^9 = %lld (expected 818503)\n", t7);
    }

    // Compute T(10^12) mod 10^9
    Matrix M = build_transition();
    Matrix Mn = mat_pow(M, n);

    ll ans = 0;
    for (int s = 0; s < 7; s++)
        ans = (ans + Mn.m[s][0]) % MOD;

    printf("T(%lld) mod %lld = %lld\n", n, MOD, ans);

    return 0;
}

#!/usr/bin/env python3
"""
Project Euler Problem 458: Permutations of Project

T(n) = number of strings of length n over {p,r,o,j,e,c,t} that do NOT contain
any permutation of "project" as a contiguous substring.

T(7) = 7^7 - 7! = 818503.
Find T(10^12) mod 10^9.

Approach: State machine + matrix exponentiation.
State s = length of longest suffix of all-distinct characters (0..7).
State 7 is absorbing (forbidden). We want sum of states 0..6 after n steps.
"""

MOD = 10**9

def build_transition_matrix():
    """
    Build 8x8 transition matrix.
    M[to][from] = number of characters that cause transition from 'from' to 'to'.

    From state s (0 <= s <= 6):
      - To state (s+1): (7-s) ways (new distinct character)
      - To state i for i in 1..s: 1 way each (duplicate char at position i from right)
    From state s = 0:
      - To state 1: 7 ways (any character)
    From state 7 (absorbing):
      - To state 7: 7 ways

    Note: from state s, the only way to go to state 0 is... never (adding any char gives
    at least state 1). Except the initial state is 0 before any character.
    """
    M = [[0] * 8 for _ in range(8)]

    for s in range(7):  # from state s
        # New distinct char -> state s+1
        M[s + 1][s] = 7 - s
        # Duplicate at position i -> state i
        for i in range(1, s + 1):
            M[i][s] += 1

    # Absorbing state 7
    M[7][7] = 7

    return M

def mat_mul(A, B, mod):
    """Multiply two 8x8 matrices mod m."""
    n = len(A)
    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, exp, mod):
    """Matrix exponentiation: M^exp mod m."""
    n = len(M)
    # Identity matrix
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        result[i][i] = 1

    base = [row[:] for row in M]
    while exp > 0:
        if exp & 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        exp >>= 1
    return result

def solve(n, mod=MOD):
    """Compute T(n) mod mod."""
    M = build_transition_matrix()
    Mn = mat_pow(M, n, mod)

    # Initial state vector: all weight in state 0.
    # Final state = Mn * v0, where v0 = (1,0,...,0).
    # T(n) = sum of Mn[s][0] for s = 0..6
    total = 0
    for s in range(7):
        total = (total + Mn[s][0]) % mod

    return total

def verify():
    """Verify T(7) = 818503."""
    t7 = solve(7, 10**18)  # Use large mod to get exact value
    expected = 7**7 - 5040  # 818503
    print(f"T(7) = {t7}, expected = {expected}, match = {t7 == expected}")

    # Also verify small cases by brute force
    from itertools import product

    def has_perm_substring(s, length=7):
        """Check if string s contains a substring that is a permutation of 7 distinct chars."""
        for i in range(len(s) - length + 1):
            if len(set(s[i:i+length])) == length:
                return True
        return False

    for n in range(1, 10):
        count = 0
        for combo in product(range(7), repeat=n):
            if not has_perm_substring(combo):
                count += 1
        t_n = solve(n, 10**18)
        status = "OK" if count == t_n else "FAIL"
        print(f"T({n}) = {t_n}, brute force = {count} [{status}]")

def generate_visualization():
    """Generate visualization of the state machine and T(n) growth."""