5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – rtybase May 6 '18 at 12:17
  • 1
    $\begingroup$ @rtybase, right! We also have prime powers $q^k$ with $\gcd(q^k, \sigma(q^k)) = 1$. $\endgroup$ – Jose Arnaldo Bebita-Dris May 6 '18 at 12:57
  • $\begingroup$ 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$. $\endgroup$ – didgogns May 11 '18 at 17:16
  • $\begingroup$ $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$. $\endgroup$ – didgogns May 11 '18 at 17:36
  • 1
    $\begingroup$ Let $n=q^k \sigma(q^k)$ then $\sigma(q^k)$ divides both $n$ and $\sigma(n)$. $\endgroup$ – didgogns May 13 '18 at 11:07
1
$\begingroup$

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}$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.