Set of Integers with a Given Abundancy Index

Question

Let $\sigma (n)$ be the sum of divisors of $n$. Define the abundancy index of $n$ to be $I(n)=\frac {\sigma(n)}{n}=\frac ab$ with $a,b$ coprime integers. For a given limit $L$ and coprime integers $a,b$, I want to find the set of all integers $n \leq L$ with $I(n)=\frac ab$.

So far I've learnt that:

1. Integers that belong to the same set are called "friendly numbers"
2. Integers that are the only ones with a given index are called "solitary"
3. An index for which no solutions exist is called "abundancy outlaw"

But I am not sure if that's any helpful. Is there any clever approach to this (which doesn't involve factoring all numbers)? Perhaps reducing the problem into factoring only some integers which are better candidates? I assume $a$ and $b$ to be arbitrary, but I would like to hear if an assumption on either of them yields an effective approach for that specific case.

Answer 1

Comment converted to an answer (so that this question does not remain in the unanswered queue):

You will need the ideas from Ludwick's "An Analysis of the Ratio $\sigma(n)/n$", an undergraduate thesis completed in May of 1994 at Penn State University. I don't think a copy is currently available online. Here is an archived copy with timestamp April 14, 2009 from the Wayback Machine.

Answer 2

To calculate phi(n), you factor n into powers of primes, and a factor p^k in n translates into a factor p^k + p^(k-1) + … + p + 1 in phi(n).

To find n with a ratio a/b, n must have all the prime factors of a. These leads to factors in phi(n), and any factors not in b must be further factors of n. You need to find n where all the factors just match precisely.

In addition, a factor p^k, k >= 1, contributes at least (p+1)/p and at most p/(p-1) to the ratio. If your ratio becomes too large, there is no solution. If your ratio is small, you may have to add many prime factors. All in all, with the limitation n < L you should be able to write a program finding all solutions.

Take as an example a/b = 7/5. n must have a factor 5^k, k >= 1, contributing at least 6/5 to the ratio. n cannot have factors 2 or 3 because these would multiply the ratio by 3/2 or 4/3, making it too big. Since n cannot have a factor 2 or 3, phi(n) cannot have a factor 2 or 3. This means 5^1 is out as a factor of n, only 5^2, 5^4 etc. A factor of 5^2 7^1 makes the ratio too large, so n has no factor 7. Phi(n) cannot have a factor 7^2. You examine possible powers, exclude what’s impossible and find your solutions, hopefully quickly because the numbers involved become greater than L quickly.

Enjoy implementing this.

48/35 > 7/5