How does the primality of $n$ impact the number of divisors of $2n+1$?

83 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.