Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have already found a summation formula here: http://math.stackexchange.com/a/22723, and also a very interesting recursive formula here: http://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).

share|improve this question
1  
What do you mean by "Closed form"? (The answer to whatever you choose will be "probably not".) –  Mike Miller Jun 20 at 22:31
1  
relevant link: mathworld.wolfram.com/DivisorFunction.html –  Alessandro Jun 20 at 22:32
add comment

1 Answer 1

up vote 13 down vote accepted

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.

share|improve this answer
    
Great answer (+1), but not everyone believes factoring is 'hard'. –  RghtHndSd Jun 21 at 1:06
    
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). –  Marc van Leeuwen Jun 21 at 5:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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