Is there a closed form expression for the sum of all the proper divisors of an integer?

1.1k Views Asked by At

I have already found a summation formula here: https://math.stackexchange.com/a/22723, and also a very interesting recursive formula here: https://math.stackexchange.com/a/22744. Any ideas on how to reduce either of these to a closed form expression would be greatly appreciated.

Edit: Essentially, I want a finite expression using elementary functions that gives the sum of the proper divisors of an integer n in terms of n (and not the prime decomposition).

1

There are 1 best solutions below

3
On BEST ANSWER

There is no computationally efficient one at least. Let $\sigma(n)$ be the sum of all divisors, which behaves better analytically, the sum of proper divisors is just $\sigma(n)-n$. Consider the simplest case $n=pq$, then $\sigma(n)=n+p+q+1$. So if you know $n$ and can find $\sigma(n)$ efficiently then you know $pq$ and $p+q$, and can factor $n$ just by solving a quadratic equation. So the formula you want can't do much better than prime factoring, which is believed to be a 'hard' problem.

It would also mean that you can have an explicit formula that gives you prime factors of $n$ as elementary functions of $n$ itself, at least when $n$ only has two factors. No such formula is known, and it is unlikely to exist.