Loading ...
Sorry, an error occurred while loading the content.

15253Code example for solving sigma(x) == A?

Expand Messages
  • jbrennen
    Aug 31, 2004
      Has 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?