3
$\begingroup$

Find all positive integers $𝑛$ such that $\sigma\left(n\right) = n + 1 + \sigma\left(n + 1\right)$, where $\sigma\,()$ is the divisor function.

I found $n = 18,\ 3200$.

For $n \leq 10^8$, only the above two integers satisfy the condition.

If no other such integers exist, can you show this?

$\endgroup$
11
  • 5
    $\begingroup$ As you are probably aware, many problems of this nature are beyond current techniques. As you've searched so far, what can you say about the sign changes between the two sides? In the range you've looked at, I mean. $\endgroup$
    – lulu
    Dec 5, 2022 at 16:10
  • 1
    $\begingroup$ Quick search seems to show that the right hand is almost always greater than the left, yes? Maybe some statement of that form is provable. $\endgroup$
    – lulu
    Dec 5, 2022 at 16:13
  • 2
    $\begingroup$ @lulu I believe that the left side is greater than the right a positive proportion of the time. This follows from the assertion that the points of the form $\bigl( \frac{\sigma(n)}n, \frac{\sigma(n+1)}{n+1} \bigr)$ are dense in $(1,\infty)\times(1,\infty)$; I believe this assertion has been proved for a general class of multiplicative functions including $\frac{\sigma(n)}n$. $\endgroup$ Dec 5, 2022 at 22:25
  • 1
    $\begingroup$ The right hand side is 2n+3 if n+1 is prime, and slightly larger if it is the product of large primes. The left hand side is >2n if n is divisible by 2, 3, 6 for example. I think it might be coincidence that they rarely match exactly. $\endgroup$
    – gnasher729
    Dec 7, 2022 at 9:11
  • 1
    $\begingroup$ That there are not many solutions is plausible : If both sigma's are even , $n$ must be odd , but because of $\sigma(n)>2n$ abundant. Such numbers are rare. If one of the sigma's is odd, $n$ or $n+1$ must be of the form $k^2$ or $2k^2$. $\endgroup$
    – Peter
    Dec 7, 2022 at 10:39

2 Answers 2

1
$\begingroup$

There is a good reason why such integers will be rare.

The sum of the divisors of n is odd iff n is a power of two multiplied by an odd square. The difference of the sum of divisors of two integers is even if after dividing by the largest possible power of two both are squares or neither is a square, and the difference is odd if one is a square and the other isn’t. n is a square roughly eith probability 1/2sqrt(n), the difference between the number of divisors is even with a probability close to 1, and odd with probability close to 1/sqrt(n).

What are the chances that this difference has the same parity as n+1? If n+1 is even, about 1. If n+1 is odd, about 1/sqrt(n). That’s the probability for the difference having the same parity as n+1, the probability for being equal to n is of course much smaller.

If n+1 is even then the parity is the usually the same. But in this case, n+1 has divisors n+1 and (n+1)/2, which makes it about n/2 larger before we look at other divisors. And we added n+1, so the divisors of n ignoring the missing n/2 must be about 1.5n larger. That doesn’t happen often.

Actually, the difference which should be zero is less than a million four times for 120million < n < 130 million, and that number seems to be shrinking. If we subtract instead of adding n+1 then there are 5 solutions with n = 1, 5, 8585, 16,119, 29,886,159. They get more rare seemingly on a logarithmic scale.

I’d expect a third solution for the original problem to involve huge numbers that will never be found. The number of cases where the difference between left and right side is even and less than a million goes down rapidly. Like 30 or 40 between k and 2k when k is around a billion.

PS. If p and 6p+1 are both primes, then the divisor sum of 6p is 1+2+3+6+n+n/2+n/3+n/6 = 2n+12, while the right hand side is (n+1)+(1+(n+1)) = n+3, so we have a difference of 9 quite often.

$\endgroup$
1
  • $\begingroup$ I also have doubts that there are only two solutions, but I also guess that the third solution is still small enough that it can be found. $\endgroup$
    – Peter
    Dec 8, 2022 at 8:15
1
$\begingroup$

You should be able to check a much larger range quite quickly. You can get a reasonably good approximation by finding the prime factors say up to 29, which lets you exclude most cases quite quickly.

Let d(n) = sigma(n) / n. To find d(n) we find the prime factors. Then if p is a factor we multiply (1+1/p), if p^2 is a factor then we multiply (1 + 1/p + 1/p^2) etc.

Say n has factors 3^2 and 23, and no other prime factors < 30. There may be more prime factors 31, 37, 41 etc. Then d(n) > (1 + 1/3 + 1/9) (1+ 1/23), and d(n) < (1 + 3 +1/9)(1 + 1/23 ..) x (1+1/31)(1+ 1/37)…. On the right hand side a factor 1 is added. The two results will very often be far apart.

I’d print out pairs with a relative difference less than 1/1000 for example to get an impression how close they get. It’s unlikely that there is a reason if you find no nearby values, just chances against you.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .