Smallest Value After Replacing With Sum of Prime Factors — Medium Problem & Solution

Repeatedly replace n with the sum of its prime factors counted with multiplicity — so 12 = 2 × 2 × 3 becomes 7.

Difficulty: Medium
Topics: Math, Simulation, Number Theory
Asked at: Amazon, Adobe, Samsung
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Repeatedly replace n with the sum of its prime factors counted with multiplicity — so 12 = 2 × 2 × 3 becomes 7.

Return the value n settles on, which is the smallest value it ever reaches.

Example 1

Input: n = 15
Output: 5
Explanation: 15 becomes 3 + 5 = 8, then 2 + 2 + 2 = 6, then 2 + 3 = 5, and 5 is prime.

Example 2

Input: n = 3
Output: 3
Explanation: A prime is its own sum of prime factors.

Example 3

Input: n = 12
Output: 7
Explanation: 12 becomes 2 + 2 + 3 = 7.

Constraints

2 <= n <= 100000

How to solve Smallest Value After Replacing With Sum of Prime Factors

Each round is a trial-division factorisation whose factors are summed with multiplicity. The sequence strictly decreases until it hits a prime, which is a fixed point.

Approach

Write a helper that factorises x by trial division from 2 up to sqrt(x), adding each prime as many times as it divides, and adding the leftover if it exceeds 1.
Loop: compute the helper's value; if it equals the current value, return it; otherwise continue from it.

Why it works

For composite x = a · b with a, b >= 2, the sum of prime factors is at most a + b <= a · b, with equality only at 4 — and 4 maps to 4, so the loop terminates there too. For a prime p the sum is p itself, so primes are the fixed points and the sequence never increases.

Complexity

Time — O(log n · sqrt(n)) overall — the value shrinks fast
Space — O(1)

Pitfalls

Summing distinct primes rather than counting multiplicity gives 5 for 12 instead of 7.
Forgetting the leftover factor after the loop loses the largest prime whenever it exceeds sqrt(x).
4 is a fixed point and would loop forever without the 'stop when unchanged' test.

Reference solution

Python

def smallestValue(n: int) -> int:
    def prime_sum(v: int) -> int:
        total = 0
        x = v
        p = 2
        while p * p <= x:
            while x % p == 0:
                total += p
                x //= p
            p += 1
        if x > 1:
            total += x
        return total

    cur = n
    while True:
        nxt = prime_sum(cur)
        if nxt == cur:
            return cur
        cur = nxt

JavaScript

var smallestValue = function(n) {
    var primeSum = function(v) {
        var total = 0, x = v;
        for (var p = 2; p * p <= x; p++) {
            while (x % p === 0) { total += p; x = x / p; }
        }
        if (x > 1) total += x;
        return total;
    };
    var cur = n;
    for (;;) {
        var next = primeSum(cur);
        if (next === cur) return cur;
        cur = next;
    }
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue