4
$\begingroup$

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).

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer (+1), but not everyone believes factoring is 'hard'. $\endgroup$ – RghtHndSd Jun 21 '14 at 1:06
  • $\begingroup$ The first thing I thought when I saw the question is "that would give a really neat way to test for primality ($\sigma(n)=n+1$)". But this argument is even more convincing. To be precise the problem it would solve is: factoring a number known to be a product of two distinct primes, which is indeed thought to be hard (RSA cryptography is based on that assumption). $\endgroup$ – Marc van Leeuwen Jun 21 '14 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.