Consecutive Positive Divisors

Find the number of integers $1 \lt n \lt 10^7$, for which $n$ and $n + 1$ have the same number of positive divisors. For example, $14$ has the positive divisors $1, 2, 7, 14$ while $15$ has $1, 3, 5, 15$.

The number of positive divisors of a number is determined by its prime factorization. If a number has a prime factorization of $p_1^{e_1}*p_2^{e_2}*…*p_k^{e_k}$ for different primes $p_1, p_2, …, p_k$, then the number of divisors of the number is $(e_1+1)*(e_2+1)*…(e_k+1)$. This is because for each prime divisor, we can choose to include that prime 0 to $e_i$ times in any divisor of the original number.

Therefore, if $n$ and $n + 1$ have the same number of positive divisors, then because $n$ and $n + 1$ are coprime (GCD is 1, they do not share any factor other than 1), the configuration of the exponents in the prime factorizations of $n$ and $n + 1$ must also be the same.

$n$ can’t end in 0 because then it would have more factors (specifically in number of 2s and 5s as prime factors) than $n + 1$. So the numbers need to be in the form of either $p^a$ or $p^a*q^b$. We need to analyze these two cases separately:

Case 1: Numbers in the form $p^a$.

Clearly, $n+1$ has to be of the form $q^b$ which means that $n+1=q^b$.

So, $p^{a} + 1 = q^{b}$

The only solutions for $a,b>1$ are $3^2 + 1 = 2^3$ and $2^5 + 1 = 11^2$. So in this case, we have two solutions, namely n=8 and n=32.

Case 2: Numbers in the form $p^a*q^b$.

Here $n+1$ also has two prime factors, which means that $n+1=r^c*s^d$. By simplifying the expression, we get

$n = (r^{c/d})^{cd} * (s^{d/c})^{cd}$, where $cd$ must be less than or equal to $10^7$.

Here are the possible values considering the fact that the numbers $p^a*q^b$ and $r^c*s^d$ can not share a common factor:

$r^c=s^d=2^2$. Here $cd=4<10^7$ is permissible, so there is one solution. $r^c=s^d=2^3$. Here $cd=9$ is permissible, so another solution. $r^c=s^d=2^5$. Here $cd=25$ is permissible, so another solution. $r^c=s^d=2^6$. Here $cd=36$ is permissible, so another solution. $r^c=s^d=2^7$. Here $cd=49$ is permissible, so another solution. $r^c=s^d=2^8$. Here $cd=64$ is permissible, so another solution. $r^c=s^d=2^{10}$. Here $cd=100$ is permissible, so another solution. $r^c=s^d=3^2$. Here $cd=4$ is permissible, so another solution. $r^c=s^d=3^3$. Here $cd=9$ is permissible, so another solution. $r^c=s^d=5^2$. Here $cd=4$ is permissible, so another solution. This gives us 10 solutions for case 2. In total we have 10 (from case 2) + 2 (from case 1) = 12 integers $1 \lt n \lt 10^7$ for which $n$ and $n + 1$ have the same number of positive divisors.

More Answers: