Project Euler

Pi Sequences

Count sequences derived from the primality of successive values, building chains.

Source sync Apr 19, 2026

Problem #0609

Level Level 15

Solved By 1,098

Languages C++, Python

Answer 172023848

Length 108 words

modular_arithmeticlinear_algebranumber_theory

For every $n \ge 1$ the prime-counting function $\pi(n)$ is equal to the number of primes not exceeding $n$.

E.g. $\pi(6)=3$ and $\pi(100)=25$.

We say that a sequence of integers $u = (u_0,\cdots,u_m)$ is a sequence if

$u_n \ge 1$ for every $n$
$u_{n + 1} = \pi (u_n)$
$u$ has two or more elements

For $u_0=10$ there are three distinct $\pi$ sequences: $(10,4)$, $(10,4,2)$ and $(10,4,2,1)$.

Let $c(u)$ be the number of elements of $u$ that are not prime.

Let $p(n,k)$ be the number of $\pi$ sequences $u$ for which $u_0\le n$ and $c(u)=k$.

Let $P(n)$ be the product of all $p(n,k)$ that are larger than $0$.

You are given: $P(10)=3 \times 8 \times 9 \times 3=648$ and $P(100)=31038676032$.

Find $P(10^8)$. Give your answer modulo $1000000007$.

Problem 609: Pi Sequences

Mathematical Analysis

Build chains $n \to \pi(n) \to \pi(\pi(n)) \to \cdots$ where $\pi$ is the prime counting function.

Derivation

The solution follows from the mathematical analysis above.

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$

Complexity Analysis

Time: See implementation.
Space: See implementation.

Answer

\boxed{172023848}

C++ project_euler/problem_609/solution.cpp

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

int main() {
    int N = 10000;
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= N; i++)
        if (is_prime[i])
            for (int j = i*i; j <= N; j += i)
                is_prime[j] = false;
    
    vector<int> pi(N + 1, 0);
    for (int i = 1; i <= N; i++)
        pi[i] = pi[i-1] + is_prime[i];
    
    map<int, int> counts;
    for (int n = 2; n <= N; n++) {
        int len = 0, x = n;
        while (x > 1) { x = pi[x]; len++; }
        counts[len]++;
    }
    
    ll MOD = 1000000007;
    ll product = 1;
    for (auto &[len, cnt] : counts)
        product = product * cnt % MOD;
    cout << product << endl;
    return 0;
}

Python project_euler/problem_609/solution.py

"""
Problem 609: Pi Sequences
Build chains n -> pi(n) -> pi(pi(n)) -> ... where pi is prime counting function.
"""

def sieve_pi(N):
    """Compute pi(n) for all n up to N."""
    is_prime = [False] * (N + 1)
    for i in range(2, N + 1):
        is_prime[i] = True
    for i in range(2, int(N**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, N + 1, i):
                is_prime[j] = False
    pi = [0] * (N + 1)
    for i in range(1, N + 1):
        pi[i] = pi[i-1] + (1 if is_prime[i] else 0)
    return pi, is_prime

def chain_length(n, pi):
    """Length of chain n -> pi(n) -> pi(pi(n)) -> ... until reaching fixed point."""
    length = 0
    while n > 1:
        n = pi[n]
        length += 1
    return length

N = 10000
pi, is_prime = sieve_pi(N)

# Verify
assert pi[10] == 4  # primes <= 10: 2,3,5,7
assert pi[100] == 25

# Chain lengths
chains = [chain_length(n, pi) for n in range(2, N + 1)]
print(f"Max chain length for n <= {N}: {max(chains)}")
print(f"Average chain length: {sum(chains)/len(chains):.2f}")

# Count by chain length
from collections import Counter
counts = Counter(chains)
for length in sorted(counts):
    print(f"  Chain length {length}: {counts[length]} numbers")

# Product of counts mod 10^9+7
MOD = 10**9 + 7
product = 1
for length in sorted(counts):
    product = (product * counts[length]) % MOD
print(f"Product of counts mod 10^9+7: {product}")