Problem 915: Digit Power Sum Sequences

Mathematical Analysis

Orbit Contraction

Theorem. For any $n \geq 10^7$ (7+ digits), $f(n) < n$. Hence every orbit under $f$ eventually enters the range $[1, 413343]$ and must cycle.

Proof. A $d$-digit number $n$ satisfies $n \geq 10^{d-1}$. The maximum value of $f$ on $d$-digit numbers is $d \cdot 9^5 = 59049d$. For $d \geq 7$:

so $f(n) < n$. The orbit is strictly decreasing until it enters $[1, 413343]$, where it must revisit some value (pigeonhole), forming a cycle. $\square$

Fixed Points of $f$

Lemma. $n = 1$ is a fixed point of $f$: $f(1) = 1^5 = 1$.

There are very few fixed points. For $n$ to be a fixed point, $n = \sum d_i^5$ where $d_i$ are the digits of $n$. Searching up to $413343$:

• $f(1) = 1$ (fixed point)
• Other possible fixed points and cycles can be found by iterating $f$ on all values up to $413343$.

Classification of Eventual Behavior

Every positive integer $n$ eventually enters one of finitely many cycles under $f$. The cycles for $p = 5$ (fifth-power digit sum) include:

• Fixed point at 1: $1 \to 1$
• Various longer cycles (e.g., involving numbers like 4150, 4151, etc.)

The Armstrong numbers (narcissistic numbers) for power 5 are: 1, 4150, 4151, 54748, 92727, 93084, 194979. These satisfy $n = f(n)$.

Memoized Orbit Classification

Algorithm. For each $n$ from 1 to $10^6$:

1. Follow the orbit $n, f(n), f(f(n)), \ldots$ until revisiting a known value.
2. If the orbit reaches a value already classified as “reaches 1” or “does not reach 1,” inherit that classification.
3. Cache the result for all values along the current path.

Theorem. This algorithm runs in $O(N)$ total time with $O(N)$ space, because each value is visited at most twice (once in its own orbit computation, once when another orbit passes through it).

Counting the Happy Numbers (Fifth-Power Variant)

Definition. A number $n$ is 5-happy if its orbit under $f$ eventually reaches 1.

For the classical happy-number problem (power 2), roughly 14.3% of numbers are happy. For power 5, the density differs.

Concrete Examples

Upper Bound on Orbit Length

Lemma. For any $n \leq 10^6$, the orbit reaches a value $\leq 413343$ within at most 2 applications of $f$. From there, the orbit length before cycling is bounded by $413343$ (in the worst case, but typically much less).

Proof. $f(n) \leq 6 \cdot 9^5 = 354294$ for any 6-digit $n$. And $f(m) \leq 6 \cdot 9^5 = 354294$ for any $m \leq 413343$. So after one step, we are in $[1, 354294]$ and stay there. $\square$

Proof of Correctness

The memoization algorithm correctly identifies whether each orbit reaches 1:

1. Termination: Guaranteed because orbits contract into a finite range and must cycle.
2. Correctness of caching: Once a value’s classification is determined, it is permanent---the orbit is deterministic.
3. Completeness: Every $n \leq 10^6$ is checked.

Complexity Analysis

• Time: $O(N)$ amortized---each number is processed once.
• Space: $O(N)$ for the memoization table.
• Per-step cost: $O(\log n)$ to compute digit sum (at most 6 digits for $n \leq 10^6$).

Answer

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

/*
 * Problem 915: Digit Power Sum Sequences
 *
 * f(n) = sum of 5th powers of digits of n.
 * Sum all n <= 10^6 whose orbit eventually reaches 1.
 *
 * Key observations:
 *   - f(n) < n for n >= 10^7, so orbits contract into [1, 413343].
 *   - Memoize orbit classification: reaches 1 or not.
 *   - Armstrong numbers for p=5: 1, 4150, 4151, 54748, 92727, 93084, 194979.
 *   - 1 is the only fixed point that qualifies.
 *
 * Complexity: O(N) amortized time with O(N) space.
 */

static const int N = 1000000;
static const int CACHE_SIZE = 500000;
static const int POW5[] = {0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049};

int digit_pow5(int n) {
    int s = 0;
    while (n > 0) {
        s += POW5[n % 10];
        n /= 10;
    }
    return s;
}

// 0 = unknown, 1 = reaches 1, 2 = does not reach 1
int cache[CACHE_SIZE];

bool reaches_one(int n) {
    if (n < CACHE_SIZE && cache[n]) return cache[n] == 1;

    vector<int> path;
    unordered_set<int> visited;
    int x = n;

    while (visited.find(x) == visited.end() && (x >= CACHE_SIZE || !cache[x])) {
        visited.insert(x);
        path.push_back(x);
        x = digit_pow5(x);
    }

    bool result;
    if (x < CACHE_SIZE && cache[x]) {
        result = (cache[x] == 1);
    } else if (x == 1) {
        result = true;
    } else {
        // Found a cycle; check if 1 is in it
        result = false;
        int y = x;
        do {
            if (y == 1) { result = true; break; }
            y = digit_pow5(y);
        } while (y != x);
    }

    for (int v : path) {
        if (v < CACHE_SIZE) {
            cache[v] = result ? 1 : 2;
        }
    }
    return result;
}

int main() {
    memset(cache, 0, sizeof(cache));
    cache[1] = 1; // 1 is a fixed point: f(1) = 1

    long long total = 0;
    for (int n = 1; n <= N; n++) {
        if (reaches_one(n)) {
            total += n;
        }
    }

    cout << total << endl;

    // Verification: Armstrong numbers for p=5
    // These are fixed points of f: n = f(n)
    vector<int> armstrong = {1, 4150, 4151, 54748, 92727, 93084, 194979};
    for (int a : armstrong) {
        assert(digit_pow5(a) == a);
    }

    return 0;
}

"""
Problem 915: Digit Power Sum Sequences

Define f(n) = sum of 5th powers of digits of n. Find the sum of all n <= 10^6
whose orbit under f eventually reaches 1.

Key ideas:
    - Orbit contraction: f(n) < n for n >= 10^7, so orbits enter [1, 413343].
    - Memoization: classify each value as "reaches 1" or not.
    - Armstrong numbers for p=5: 1, 4150, 4151, 54748, 92727, 93084, 194979.
    - The number 1 is a fixed point: f(1) = 1.

Methods:
    1. Memoized orbit classification
    2. Brute-force orbit tracing (for verification)
    3. Armstrong number identification
"""

from collections import Counter

POWER = 5
N = 10**6

# Precompute fifth powers of digits
POW5 = [d**POWER for d in range(10)]

def digit_power_sum(n: int) -> int:
    """Compute sum of 5th powers of digits of n."""
    s = 0
    while n > 0:
        s += POW5[n % 10]
        n //= 10
    return s

def solve(limit: int) -> int:
    """Sum of all n <= limit whose orbit under f eventually reaches 1."""
    # Cache: True if orbit reaches 1, False otherwise
    cache = {}

    def reaches_one(n: int) -> bool:
        if n in cache:
            return cache[n]
        # Trace orbit until we hit a cached value or detect a cycle
        path = []
        visited = set()
        x = n
        while x not in visited and x not in cache:
            visited.add(x)
            path.append(x)
            x = digit_power_sum(x)

        if x in cache:
            result = cache[x]
        elif x == 1:
            result = True
        else:
            # x is in visited but not 1 -> cycle not containing 1
            result = False
            # But check: maybe 1 is in the cycle
            # If x is in visited, we've found a cycle. Check if 1 is in it.
            cycle_start = path.index(x)
            cycle = path[cycle_start:]
            result = 1 in cycle

        # Cache all values in path
        for v in path:
            cache[v] = result
        return result

    total = 0
    for n in range(1, limit + 1):
        if reaches_one(n):
            total += n
    return total

def find_armstrong_numbers(power: int, max_digits: int = 7) -> list:
    """Find all Armstrong numbers for given power up to max_digits digits."""
    results = []
    for d in range(1, max_digits + 1):
        max_val = d * 9**power
        for n in range(max(1, 10**(d-1)), min(10**d, max_val + 1)):
            if digit_power_sum(n) == n:
                results.append(n)
    return results

# Solve
answer = solve(N)

# Find Armstrong numbers for verification
armstrong = find_armstrong_numbers(5)
# Expected: [1, 4150, 4151, 54748, 92727, 93084, 194979]

print(answer)

# Verification: check small cases
assert digit_power_sum(1) == 1
assert digit_power_sum(10) == 1
assert digit_power_sum(100) == 1
assert digit_power_sum(4150) == 4150  # Armstrong number