I was looking at the number of divisors of odd natural numbers $2r+1$ and I observed an curious difference between the cases when $r$ is a prime and when it is a composite.

Let $p_n$ and $c_n$ be the $n$-th prime and the $n$-th composite number respectively. Let $f(n)$ be the number of natural numbers of the form $2p_k + 1, k \le n$ which have exactly four divisors. Let $g(n)$ be the number of natural numbers of the form $2c_k + 1, k \le n$ which have exactly four divisors.

I observed that as $n$ increases, $\dfrac{f(n)}{g(n)}$ decreases. For $n = 1 \times 10^7$ the ratio was about $0.710$ while for $n = 7 \times 10^7$ the ratio was about $0.706$. The data shows that a number for the from $2r+1$ is nearly $30\%$ less likely to have exactly four divisors if $r$ is a prime than it is if $r$ is composite. $30\%$ is a significant difference so I am curious to know the what is it about primes that causes this large difference?

Similarly, for number of the form $2r+1$ which have exactly ten divisors, I observed that if $r$ is a prime, the likelihood increases by about $3.5\%$. Thus in some cases, the likelihood decreases with primes and in some cases it increases.

Question 1: Why is a number of the from $2r+1$ about $30\%$ less likely to have exactly four divisors when $r$ is a prime?

Question 2: In which case does it increase for primes and in which case does it decrease?

  • 4
    $\begingroup$ A number with exactly four divisors is either of the form $p^3$ or $pq$ for distinct primes $p,q$. I wonder if its related to $2r+1$ not being of the form $p^3$, since if that was the case, $r=(p^3-1)/2$, which is divisible by $(p-1)/2$ $\endgroup$ – Kenta S Aug 4 '20 at 14:32
  • 2
    $\begingroup$ Shouldn't you consider $f(n)$ (respectively $g(n)$) to be the same as you define but with $2p+1\leq n$ (resp. $2c+1\leq n$)? Because when you are counting the primes and the composite numbers, both counting methods don't go to the same speed towards infinity, and it may (but may not) have a strong influence in your ratio (especially if the property "having exactly four divisors" is correlated to be in some regions of the natural numbers for instance). $\endgroup$ – Fabien Aug 4 '20 at 14:33

Reason 1: The nth prime is roughly log n times larger than the nth composite number, and larger numbers tend to have more factors.

Reason 2: Given n with a factor p, 2n+1 is not divisible by p. So if n has small factors, 2n+1 will tend to have fewer small factors. As an example, if n is prime then there is a 50% chance that 2n+1 is divisible by 3, while for random n the chance is one in three.

I’d check the results first with primes and non-primes of the same size.


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.