15253Code example for solving sigma(x) == A?
- Aug 31, 2004Has anybody written/used any code to solve for all solutions of:
sigma(x) == A
given a value of A? In particular, I'm most interested in a
PARI/GP function, but I'll look at anything. sigma(x) of course
has its standard meaning as the sum of the positive integer
divisors of x.
Obviously, for any reasonable implementation, A needs to be
factored, but I'm assuming that can be done efficiently.
One algorithm seems straightforward enough...
(1) For each divisor d of A, with d >= 3, find all solutions
to sigma(p^n) == d. (p prime, n >= 1).
(2) All solutions to sigma(x) == A can be built up from the
solutions found in step 1, using the identity
sigma(i*j) == sigma(i)*sigma(j), where i and j are coprime.
But the devil is in the details, and writing a simple, 5 or 10
line solution would be easy but could be very inefficient.
For instance, if A is equal to 5*q (where q is prime), there is
no need to even search for solutions to sigma(p^n) == q, since
sigma(x) == 5 is unsolvable.
If A is odd, can we make use of the knowledge that x must be
either a perfect square or twice a perfect square?
So before I go to the trouble of attempting to write a decent
implementation, has somebody been down this road before?