# What proportion of the natural numbers satisfies the following inequality?

Solving this problem might be too ambitious, but I will ask it here nonetheless, because I do not know of an answer currently.

Let $\sigma(x)$ denote the sum of the divisors of $x \in \mathbb{N}$, and let $\gcd(y,z)$ denote the greatest common divisor of the positive integers $y$ and $z$.

Here is my question:

What proportion of the natural numbers satisfies $\gcd(n, \sigma(n)) > c\sqrt{n}$, where $c$ is a constant that does not depend on $n$?

MY ATTEMPT

I was able to get hold of Pollack's paper titled On the Greatest Common Divisor of a Number and Its Sum of Divisors, and while it does seem that my exact question is covered there, I am unable to parse my way through and thereby get an answer for my question here.

• Just an observation, as a start, we have primes with $\gcd(n,\sigma(n))=\gcd(n,n+1)=1$ and perfect numbers with $\gcd(n,\sigma(n))=\gcd(n,2n)=n$ – rtybase May 6 '18 at 12:17
• @rtybase, right! We also have prime powers $q^k$ with $\gcd(q^k, \sigma(q^k)) = 1$. – Jose Arnaldo Bebita-Dris May 6 '18 at 12:57
• Most of the numbers are not "perfect enough", so the proportion looks like $0$ as $n$ goes infinity. For any prime power $q^k$, $q^k\sigma(q^k)$ satisfies the condition so actual number is at least $\log n$. – didgogns May 11 '18 at 17:16
• $q^k\sigma(q^k)$ only works if $c\le1$. If then, for almost all square number $n^2$, $n^2\sigma(n^2)$ works, so the number will be at least about $n^{1/4}$. The smallest counterexample is $14$ because $\sigma(2^2)=7$. – didgogns May 11 '18 at 17:36
• Let $n=q^k \sigma(q^k)$ then $\sigma(q^k)$ divides both $n$ and $\sigma(n)$. – didgogns May 13 '18 at 11:07

I made a computer search up to $10^9$ and here are summary of results.

• Number of integers satisfying $n<10^k$ and $\gcd(n, \sigma(n))>\sqrt n$

$$\begin{array}{c|c|} k & \text{count} \\ \hline 1 & 1 \\ \hline 2 & 11 \\ \hline 3 & 69 \\ \hline 4 & 309 \\ \hline 5 & 1492 \\ \hline 6 & 6722 \\ \hline 7 & 30089 \\ \hline 8 & 133331 \\ \hline 9 & 363524 \\ \hline \end{array}$$

• Number of odd integers satisfying $n<10^k$ and $\gcd(n, \sigma(n))>\sqrt n$

$$\begin{array}{c|c|} k & \text{count} \\ \hline 2 & 0 \\ \hline 3 & 6 \\ \hline 4 & 26 \\ \hline 5 & 110 \\ \hline 6 & 502 \\ \hline 7 & 2020 \\ \hline 8 & 8830 \\ \hline 9 & 21618 \\ \hline \end{array}$$

• Top 10 numbers in terms of $c(n)=\gcd(n, \sigma(n))/\sqrt n$

$$\begin{array}{c|c|c|} \text{Rank} & n & c(n) \\ \hline 1 & 536854528 & 23170.1 \\ \hline 2 & 459818240 & 21443.4 \\ \hline 3 & 142990848 & 11957.9 \\ \hline 4 & 470564640 & 7230.8 \\ \hline 5 & 746444160 & 6830.3 \\ \hline 6 & 45532800 & 6747.8 \\ \hline 7 & 33550336 & 5792.3 \\ \hline 8 & 492101632 & 5545.8 \\ \hline 9 & 714954240 & 5347.7 \\ \hline 10 & 668304000 & 5170.3 \\ \hline \end{array}$$

• List of numbers such that for all $k<n$, $c(k)<c(n)$

$$\begin{array}{c|c|} n & c(n) \\ \hline 1 & 1.000000 \\ \hline 6 & 2.449490 \\ \hline 28 & 5.291503 \\ \hline 120 & 10.954451 \\ \hline 496 & 22.271057 \\ \hline 672 & 25.922963 \\ \hline 4320 & 32.863353 \\ \hline 4680 & 34.205263 \\ \hline 8128 & 90.155421 \\ \hline 30240 & 173.896521 \\ \hline 32760 & 180.997238 \\ \hline 435708 & 220.027271 \\ \hline 523776 & 723.723704 \\ \hline 2178540 & 1475.987805 \\ \hline 8910720 & 1492.541457 \\ \hline 17428320 & 2087.361971 \\ \hline 20427264 & 2259.826542 \\ \hline 23569920 & 4854.886198 \\ \hline 33550336 & 5792.265187 \\ \hline 45532800 & 6747.799641 \\ \hline 142990848 & 11957.878073 \\ \hline 459818240 & 21443.372869 \\ \hline 536854528 & 23170.121450 \\ \hline \end{array}$$

• List of numbers such that for all $k<n$, $\gcd(k, \sigma(k))<\gcd(n, \sigma(n))$

$$\begin{array}{c|c|} n & \gcd(n, \sigma(n)) \\ \hline 1 & 1 \\ \hline 6 & 6 \\ \hline 24 & 12 \\ \hline 28 & 28 \\ \hline 120 & 120 \\ \hline 496 & 496 \\ \hline 672 & 672 \\ \hline 4320 & 2160 \\ \hline 4680 & 2340 \\ \hline 8128 & 8128 \\ \hline 26208 & 13104 \\ \hline 30240 & 30240 \\ \hline 32760 & 32760 \\ \hline 174592 & 43648 \\ \hline 199584 & 66528 \\ \hline 293760 & 73440 \\ \hline 435708 & 145236 \\ \hline 523776 & 523776 \\ \hline 2142720 & 714240 \\ \hline 2178540 & 2178540 \\ \hline 8910720 & 4455360 \\ \hline 17428320 & 8714160 \\ \hline 20427264 & 10213632 \\ \hline 23569920 & 23569920 \\ \hline 33550336 & 33550336 \\ \hline 45532800 & 45532800 \\ \hline 91963648 & 45981824 \\ \hline 142990848 & 142990848 \\ \hline 459818240 & 459818240 \\ \hline 536854528 & 536854528 \\ \hline \end{array}$$

• From the first table, are there any odd $n < 10^k$ that satisfy $\gcd(n, \sigma(n)) > \sqrt{n}$, @didgogns? – Jose Arnaldo Bebita-Dris May 16 '18 at 15:24
• Using Sage Cell Server, I got the following examples for $k=3$: $117, 135, 585, 775, 819, 891$. – Jose Arnaldo Bebita-Dris May 16 '18 at 15:40
• Added number of odd numbers. The odd number with maximum $c(n)$ is $n=779372685$ with $c(n)=526.7$. – didgogns May 16 '18 at 16:10

Let us calculate it for some values of $n$
$n=2,sum=3$
$n=3,sum=4$
$n=4,sum=7$
$n=5,sum=6$
Now there GCD is 1 thus we can be sure that no $n$ satisfies the relation.