6
$\begingroup$

I'm trying to write a function that efficiently solves this problem:

Given positive integers m and n, determine whether $\sigma(n)=m$.

Of course I'm looking for a faster technique than "factor n, determine sigma(n), and check if the two are equal" or I wouldn't have posted here. My basic idea is finding small factors of n (or their absence) and short-circuiting if no factorization of the remaining part would give m.

Other tests, like requiring that $n$ be a square or twice a square if $m$ is odd, come to mind.

Any other ideas, or thoughts on how to actually implement this? If $m/n$ is very large it can be disqualified by comparing to a list of superabundant numbers and their abundancies, but if it is within the possible range I'd need to find some equivalent way to disqualify numbers that have no factors below some limit L to which I have tested, and it's not clear how to do this.

(Of course if I'm fortunate enough to find a component $p^a\parallel n$ with $\sigma(p^a)\nmid m$ I'm done, but too many numbers have no small factors to rely on finding this in all cases.)

  • 0
    What is $\sigma$? (I know, if I have to ask I'm probably not qualified to answer)2011-06-30
  • 0
    It's http://oeis.org/A0002032011-06-30
  • 1
    Well, this can't be any easier than primality testing, since $\sigma(n) = n+1$ if and only if $n$ is prime. Primality testing was only recently shown to be polynomial-time, so you aren't going to get a trivial polynomial-time algorithm.2011-06-30
  • 0
    n-1, maybe? :) funny.2011-06-30
  • 0
    Whew, thanks to Charles, I confused the Sigma of n with Euler's totient function, don't ask me why. I shouldn't read this site past 1 a.m., it's dangerous...2011-06-30

3 Answers 3

3

It has been a while since I played with this when searching for amicable numbers, but here are a few suggestions.

EDIT: Seeing the other answer, it appears that I should mention that $\sigma$ is multiplicative, i.e. if $n=\prod_i p_i^{e_i}$ then $\sigma(n) = \prod_i (p_i^{e_i+1}-1)/(p-1)$, this is necessary for the following.

Assuming that you have a table of primes run through the primes until you find a factor of $n$ and act accordingly. You only need primes up to around $n^{1/3}$.

  1. While you run through the small prime factors of n, say you find that $p^e | n$ check that $\sigma(p^e) | m$. (It is probably best to divide it out and check that $\sigma(n/p^e) = m/\sigma(p^e)$ (obviously not bothering with primes smaller than $p$ going forward). This tends to short circuit the computation very quickly.

  2. Obviously short circuit when $n>m$. This is why dividing out the factors of $p^e$ and $\sigma(p^e)$ is useful. In my experience steps 1 and 2 are the most powerful. Also test if $n+1=m$ and $n$ prime.

  3. If you are at a large enough p that you know that there can be only two prime factors, solve the quadratic resulting from $n = pq$, $m=(p+1)(q+1)$, so $n-m+1=p+q$ so p and q are roots of $x^2 + (m-n-1) x + n$ (check my algebra). (you also need to check if $n = p^2$ and $m = p^2+p+1$, but this is easy as $p=m-n-1$.

  4. Very occasionally (say whenever $p$ passes $2^k$ for $k>10$) check if $\sigma(n)$ must be smaller than $m$ by assuming that all the remaining factors of $n$ are distinct factors of size $p$. This gets fiddly, and I forget the details. The idea comes from H. J. J. TeRiele's 1986 amicable pair paper in Math Comp. Essentially if $n=p^k q$ then $m < (p+1)^k (q+1)$ with $p ($q$ not necessarily integer)[*]

  5. If you have dealt with the even prime, and you should do that first, then it is worth handling the case of odd $m$ separately (this is another reason to divide out $\sigma(p^e)$ as you find them. As you divide out small primes the powers of 2 in $m$ disappear fairly quickly.
  6. One more thing (a combination of 2 and 3) if $m then $n$ must have one or two prime factors, and you can apply 3.

[*] This is not too fiddly after all. If $p$ is a prime factor of $n$ the most it can contribute to $\sigma(n)/n$ is $(p+1)/p$, so if we want a bound on maximum possible value of $\sigma(n)$ given that $n$ has no prime factor smaller than $p$, and $n$ has $k$ prime factors, we can use the maximum of $\prod_i (p_i+1)$ constrained by $\prod_i p_i = n$ and $p_i>p$. This is a Lagrange multiplier problem and it is easy to see that it is maximized on the boundary and the maximum value is $(p+1)^{k-1} (q+1)$, and if we maximize this with respect to $k$ we see that we must choose $k$ to be as large as possible such that $q>p$.

  • 0
    Do you mean, "You only need primes up to around $ n^{1/2} $"?2011-06-30
  • 0
    @Alpha No. See step 3.2011-06-30
  • 0
    I am actually working with small enough numbers that #3 could be relevant--though 'usually' I think that switching to general factoring methods (ECM then SIQS) is better. #4 was really what I was asking about, so thanks for the reference! I'll look it up and see if it's helpful.2011-06-30
  • 0
    @Charles In my experience one of 1,2, or 4 kicks in well before you get to 3, but I was only dealing with numbers less than $2^64$, so ECM would have been overkill.2011-06-30
1

You could try a sieve. The simplest one that comes to mind is creating a list from 1 to some number n where initially each element in the list has the value 1; loop through the list continually adding the current number you're at to its multiples until you hit the end of the list. Here is some code (in C++):

int n = 1000000; // limit of the sieve vector  sigma(n+1,1); for(int i = 2;i <= n; i++)     for(int j = i;j <= n;j += i)         sigma[j] += i; 
  • 0
    This is too slow.2011-06-30
1

Bach, Miller and Shallit showed that given $\sigma(n)$ and n you can factor n in random polynomial time, which can be used for what you want. The paper is Sums of Divisors, Perfect Numbers and Factoring.

  • 0
    The usual case I want to dispense with is $\sigma(n)\neq m$ which I can hopefully do most of the time without ever fully factoring $n$.2011-07-01
  • 0
    Assume $\sigma(n)=m$. Run the algorithm with m and n as input. If it fails to produce a correct factorization of n then m and $\sigma(n)$ and m are not equal. If it produces a correct factorization of n then compute $\sigma(n)$ and check if $\sigma(n)=m$.2011-07-01
  • 0
    As to not factoring n, is that an issue if the factorization is computed efficiently? Of course it may be there are faster algorithms but getting one that runs in random polynomial time is a nontrivial first step.2011-07-01
  • 0
    No, but I somehow doubt it can factor many numbers efficiently (say, polynomial time). I will look into it, though.2011-07-01
  • 0
    Unless either I misunderstand, or am thinking of a different paper. They give a randomized algorithm that is not guaranteed to terminate. I suspect that a test of the form - if this algorithm never terminates then $\sigma(n)\ne m$ - is of little practical value.2011-07-01
  • 0
    Yes, I would guess its very unlikely the algorithm will terminate with a factor of n if $\sigma(n)\ne m$. But you can just choose some number of operations larger than the bound on the complexity of the algorithm and terminate if you reach it, which tells you $\sigma(n)\ne m$.2011-07-02
  • 0
    @David Marquis: It's impossible in general to bound the time on an arbitrary algorithm (Rice's theorem). Are bounds known in this case?2011-09-09
  • 0
    Further, Hartmanis 1978 shows that it's impossible in a stronger sense.2011-09-09