Decompose Number with Prime Factor

Question

Given a number n, Here are two operations can be taken:

• n - 1
• n divide by its prime factor

Question: In order to decompose n to 1, what is the minimal operations should be taken?

For example, in term of number 29, it is a prime number. So, the number of operation is 1. For number 30, the number of operations is 2(30 minus 1 and it is a prime number).

PS: It seems that we can decompose a number in no more than 4 operations(Not sure).

Answer 1

Let $f(n)$ be the minimal number of operations (subtracting $1$ or dividing by any prime factor of $n$) required to reach $1$ from $n$. I claim that not only is $f(n)$ unbounded, but for any positive integer $k$, the set of $n$ for which $f(n)>k$ has density $1$ (that is, "almost all" integers have $f(n)>k$). This follows from the upper bound $$ \#\{n\le x\colon f(n)\le k\} \ll_k \frac{x(\log\log x)^{k-1}}{\log x} \tag{$*$} $$ which we can prove by induction on $k$. The base case $k=1$ follows from the prime number theorem since $f(n)=1$ is equivalent to $n$ being prime.

Suppose the upper bound ($*$) holds for some integer $k$. Consider integers $n$ such that $f(n)\le k+1$. One possibility is that $f(n-1) \le k$; by hypothesis there are only $\ll_k x(\log\log x)^{k-1}/\log x$ such integers $n\le x$. The other possibility is that there exists a prime $p\le x$ and an integer $m\le x/p$ with $f(m)\le k$ such that $n=mp$. But the number of such integers is at most \begin{align*} \sum_{p\le x} \#\{m\le x\colon f(m)\le k\} &\ll_k \sum_{p\le x} \frac{\frac xp(\log\log \frac xp)^{k-1}}{\log \frac xp} \\ &\ll_k \frac{x(\log\log x)^{k-1}}{\log x} \sum_{p\le x} \frac1p \ll \frac{x(\log\log x)^{k-1}}{\log x} \log\log x \end{align*} as required to establish ($*$) for $k+1$.

It would be interesting to look at the distribution of $f(n)$. For example, $f(n)$ is certainly bounded above by the number of prime factors of $n$; does $f(n)$ follow the same Erdös–Kac law? (In the above argument, it depends on the size of the implicit constant depending on $k$.)

Answer 2

Here's a simple Python script that will count the number of steps needed to reach 1, for all integers less than a million:

import math

def prime_factors(n):
    '''
    Return a set of the unique prime factors of n.
    '''
    result = set()
    upper_bound = int(math.sqrt(n) * 1.00000001)
    for divisor in range(2, upper_bound + 1):
        if n == 1:
            return result
        while n % divisor == 0:
            result.add(divisor)
            n //= divisor
    # If we reach this point, n itself is prime
    result.add(n)
    return result

# number of steps required to reduce the number to 1
STEP_COUNT = [None, 0]
for n in range(2, 10**6):
    next_step = {n - 1} | {n // p for p in prime_factors(n)} - {n}
    num_steps = 1 + min(STEP_COUNT[ns] for ns in next_step)
    STEP_COUNT.append(num_steps)

PS: It seems that we can decompose a number in no more than 4 operations(Not sure).

Not true for $n = 27436 = 2^2 19^3$, which requires 5 steps (all divisions by a prime factor).

More generally,

• 1 is the only number requiring 0 steps.
• 2 is the smallest number requiring 1 step.
• 4 is the smallest number requiring 2 steps.
• 16 is the smallest number requiring 3 steps.
• 176 is the smallest number requiring 4 steps.
• 27436 is the smallest number requiring 5 steps.
• 602868736 is the smallest number requiring 6 steps. (Thanks to @EnEm.)