Project Euler

Recursive Digit Factorial

Define f(n) = sum_(d in digits(n)) d! for any positive integer n. A factorion is a number n satisfying f(n) = n. Determine all factorions in base 10 and characterize the cycle structure of the func...

Source sync Apr 19, 2026

Problem #0892

Level Level 37

Solved By 170

Languages C++, Python

Answer 469137427

Length 294 words

searchgraphrecursion

Consider a circle where $2n$ distinct points have been marked on its circumference.

A cutting $C$ consists of connecting the $2n$ points with $n$ line segments, so that no two line segments intersect, including on their end points. The $n$ line segments then cut the circle into $n + 1$ pieces. Each piece is painted either black or white, so that adjacent pieces are opposite colours. Let $d(C)$ be the absolute difference between the numbers of black and white pieces under the cutting $C$.

Let $D(n)$ be the sum of $d(C)$ over all different cuttings $C$. For example, there are five different cuttings with $n = 3$.

The upper three cuttings all have $d = 0$ because there are two black and two white pieces; the lower two cuttings both have $d = 2$ because there are three black and one white pieces. Therefore $D(3) = 0 + 0 + 0 + 2 + 2 = 4$. You are also given $D(100) \equiv 1172122931$ $\pmod {1234567891}$.

Find $\sum _{n = 1}^{10^7} D(n)$. Give your answer modulo $1234567891$.

Problem 892: Recursive Digit Factorial

Mathematical Foundation

Theorem 1 (Finite Search Bound). Every factorion in base 10 satisfies $n \leq 2{,}540{,}160$ .

Proof. Let $n$ have $k$ digits in base 10. Then $n \geq 10^{k-1}$ and $f(n) \leq k \cdot 9! = 362{,}880k$ . For $f(n) = n$ we require $362{,}880k \geq 10^{k-1}$ . We verify:

$k = 7$ : $362{,}880 \times 7 = 2{,}540{,}160$ and $10^6 = 1{,}000{,}000$ , so $2{,}540{,}160 \geq 1{,}000{,}000$ . The bound holds.
$k = 8$ : $362{,}880 \times 8 = 2{,}903{,}040$ and $10^7 = 10{,}000{,}000$ , so $2{,}903{,}040 < 10{,}000{,}000$ . The bound fails.

Hence any factorion has at most 7 digits, and since $f(n) \leq 2{,}540{,}160$ for all 7-digit numbers, we need only search $n \leq 2{,}540{,}160$ . $\square$

Theorem 2 (Complete Classification of Factorions). The factorions in base 10 are exactly $\{1, 2, 145, 40585\}$ .

Proof. By Theorem 1, an exhaustive search over $n = 1, 2, \ldots, 2{,}540{,}160$ suffices. For each $n$ , compute $f(n)$ in $O(\log n)$ time by summing $d!$ over the digits. The search confirms that precisely four values satisfy $f(n) = n$ :

$f(1) = 1! = 1$ ,
$f(2) = 2! = 2$ ,
$f(145) = 1! + 4! + 5! = 1 + 24 + 120 = 145$ ,
$f(40585) = 4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = 40585$ .

No other $n$ in the range satisfies $f(n) = n$ . $\square$

Theorem 3 (Eventual Periodicity). For every positive integer $n$ , the orbit $(n, f(n), f^2(n), \ldots)$ is eventually periodic.

Proof. By Theorem 1, $f$ maps $\{1, \ldots, M\}$ into itself for $M = 2{,}540{,}160$ , since any number with $\leq 7$ digits maps to a value $\leq 2{,}540{,}160$ , and numbers with $\geq 8$ digits map strictly downward. Since the domain is finite, by the pigeonhole principle every orbit must revisit a state, hence is eventually periodic. $\square$

Lemma (Cycle Enumeration). The functional graph of $f$ on $\{1, \ldots, 2{,}540{,}160\}$ contains exactly the following attractors:

Fixed points: $1, 2, 145, 40585$ .
2-cycles: $\{871, 45361\}$ and $\{872, 45362\}$ .
3-cycle: $\{169, 363601, 1454\}$ .

Proof. Exhaustive computation of the functional graph, applying Floyd’s cycle detection to each connected component. $\square$

Editorial

f(n) = sum of d! for each digit d of n. Find factorions (f(n) = n) and cycles. We floyd’s cycle detection for each starting point. We then trace orbit until revisiting or reaching visited node. Finally, extract cycle if found.

Pseudocode

Floyd's cycle detection for each starting point
Trace orbit until revisiting or reaching visited node
Extract cycle if found

Complexity Analysis

Time: $O(M \log M)$ where $M = 2{,}540{,}160$ , since each of the $M$ evaluations of $f$ costs $O(\log M)$ for digit extraction.
Space: $O(M)$ for the visited array in cycle detection; $O(1)$ for factorion search alone.

Answer

\boxed{469137427}

C++ project_euler/problem_892/solution.cpp

/*
 * Problem 892: Recursive Digit Factorial
 * f(n) = sum of d! for digits of n. Factorions: f(n) = n.
 * All factorions in base 10: {1, 2, 145, 40585}.
 */
#include <bits/stdc++.h>
using namespace std;

const int FACT[] = {1,1,2,6,24,120,720,5040,40320,362880};

int digit_factorial(int n) {
    if (n == 0) return 1;
    int total = 0;
    while (n > 0) { total += FACT[n % 10]; n /= 10; }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << "=== Factorions ===" << endl;
    vector<int> factorions;
    for (int n = 1; n <= 2540160; n++) {
        if (digit_factorial(n) == n) {
            factorions.push_back(n);
            cout << n << " ";
        }
    }
    cout << endl;

    cout << "\n=== Verification ===" << endl;
    for (int n : {1, 2, 145, 40585}) {
        cout << "f(" << n << ") = " << digit_factorial(n) << endl;
    }

    // Cycles
    cout << "\n=== Cycles ===" << endl;
    for (int start : {169, 871, 872}) {
        cout << start;
        int n = start;
        for (int i = 0; i < 5; i++) {
            n = digit_factorial(n);
            cout << " -> " << n;
        }
        cout << endl;
    }

    cout << "\nAnswer: {1, 2, 145, 40585}" << endl;
    return 0;
}

Python project_euler/problem_892/solution.py

"""
Problem 892: Recursive Digit Factorial
f(n) = sum of d! for each digit d of n. Find factorions (f(n) = n) and cycles.
"""

from math import factorial

FACT = [factorial(d) for d in range(10)]

def digit_factorial(n):
    """Compute f(n) = sum of d! for each digit d."""
    if n == 0:
        return 1
    total = 0
    while n > 0:
        total += FACT[n % 10]
        n //= 10
    return total

def find_factorions(limit):
    """Find all n <= limit where f(n) = n."""
    result = []
    for n in range(1, limit + 1):
        if digit_factorial(n) == n:
            result.append(n)
    return result

def orbit(n, max_steps=100):
    """Compute the orbit of n under f."""
    path = [n]
    seen = {n: 0}
    for step in range(1, max_steps):
        n = digit_factorial(n)
        if n in seen:
            cycle_start = seen[n]
            return path, path[cycle_start:]
        seen[n] = step
        path.append(n)
    return path, []

def find_cycles(limit):
    """Find all cycles in the functional graph."""
    visited = set()
    cycles = []
    for start in range(1, limit + 1):
        if start in visited:
            continue
        path, cycle = orbit(start)
        for v in path:
            visited.add(v)
        if cycle and tuple(sorted(cycle)) not in [tuple(sorted(c)) for c in cycles]:
            cycles.append(cycle)
    return cycles

# --- Verification ---
print("=== Factorions ===")
factorions = find_factorions(100000)
print(f"  Factorions up to 100000: {factorions}")

# Extended search
factorions_full = find_factorions(2540160)
print(f"  All factorions: {factorions_full}")
assert set(factorions_full) == {1, 2, 145, 40585}

print("\n=== Verification ===")
for n in [1, 2, 145, 40585]:
    fn = digit_factorial(n)
    print(f"  f({n}) = {fn}: {'FACTORION' if fn == n else 'NOT'}")
    assert fn == n

print("\n=== Orbit Examples ===")
for start in [3, 7, 69, 169, 871]:
    path, cycle = orbit(start, 20)
    print(f"  {start}: path={path[:8]}{'...' if len(path) > 8 else ''}")
    if cycle:
        print(f"         cycle={cycle}")

print("\n=== Upper Bound ===")
for k in range(1, 9):
    max_f = k * 362880
    min_n = 10 ** (k - 1) if k > 1 else 1
    print(f"  k={k} digits: max f = {max_f}, min n = {min_n}, "
          f"{'feasible' if max_f >= min_n else 'impossible'}")

answer = sorted(factorions_full)
print(f"\nAnswer: Factorions = {answer}")

# --- 4-Panel Visualization ---