NumberWorld

The $\sigma_i(n)$ function is an important arithmetic function and as typical for such functions, it can not be computed efficiently for large input parameters $n$ due to the factorization problem. But in contrast to $\sigma_1(n)$, which does reveal the factorization of $n$ immediately (at least if $n=pq$), $\sigma_0(n)$ does not, or at least not that easy (see Part 2 and Part 1 ). Additionally, $\sigma_1(n)$ has also the strange property that it can be computed recursively, as i showed in that [ post ]. However, we know how to compute, or better, how to decide, if $\sigma_0(n)$ is $2$ or not. This is because $\sigma_0(n) = 2$ if and only if $n$ is a prime number. And primality can be checked by the AKS-Algorithm in deterministic polynomial time. If AKS is too slow for you, there much more faster probabilistic polynomial time algorithms. They utilize that a prime number has special properties, e.g., they use Fermat-Little-Theorem . But so called base-$b$ pseudo prime numbers can sur...

What would be the consequences if the sum of divisors function with $k=0$ could be computed efficiently, that is polynomial in $\log (n)$ if $n$ is the input to $\sigma_0(n)$? Note that if $n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}$ then $$\sigma_0(n) = \sum_{d|n} d^0 =  \sum_{d|n} 1 = (e_1+1)(e_n+1)...(e_m+1)$$ For square-free numbers $n$, this is always a power of $2$, hence $\log_2(\sigma_0(n))$ gives the number of prime factors in this case. Furthermore, the famous AKS-algorithm gives a deterministic polynomial time algorithm, that decides if $\sigma_0(n) = 2$ or not, i.e. $n$ is prime or composite. For the general case, Terence Tao gave an heuristic argument that generally this should be as hard as factoring a number: " There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors  problem is believed to have comparable difficulty ...

Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions . Well known examples are, e.g., the Euler's Totient Function and The Möbius Function . Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem . One of these functions, that heavily depends on that factorization, is the Divisor Function . Definition: Divisor Function Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$