A343494 Numbers k such that tau(k) and tau(k+1) are both prime, where tau is the number of divisors function.

2, 3, 4, 16, 65536

Offset: 1

Author

Claude H. R. Dequatre, Apr 17 2021

Keywords

• nonn
• hard
• more

Comments

Considering the first 10^8 positive integers, we note the following: only five of them meet the definition; the first two (2,3) are prime and the next three (4, 16 and 65536) are perfect squares (4 = 2^2, 16 = 4^2 and 65536 = 256^2).

Open questions: are there any other terms greater than 65536? If yes, are they all composite numbers and more specifically perfect squares?

From Jon E. Schoenfield, Apr 19 2021: (Start)

a(6), if it exists, is at least 2^(2^(2^33)). Proof:

Every number having a prime number of divisors is of the form p^e where p is a prime and the exponent e is a nonnegative integer such that e+1 is prime, so we can write k = p^j, k+1 = q^m, and p^j + 1 = q^m, where both j+1 and m+1 are prime.

Either k or k+1 must be even, so either p or q must be 2.

Suppose q=2. We have p^j + 1 = 2^m, so p^j = 2^m - 1. m cannot be 1, since that would mean p^j = 1 (impossible), and m+1 is prime, so m is an even number. Let m = 2*v. Then p^j = 2^(2*v) - 1 = (2^v - 1)*(2^v + 1): two factors differing by exactly two, and both odd. The only way their product can be a prime power (i.e., p^j) is if they are 1 and 3, so p^j = 1*3 = 3, i.e., k=3; this is a(2), the only odd term in the sequence.

Now suppose p=2. We have 2^j + 1 = q^m, so 2^j = q^m - 1. If m > 1, then since m+1 is prime, m is an even number. Let m = 2*v. Then 2^j = q^(2*v) - 1 = (q^v - 1)*(q^v + 1): again, two factors differing by exactly two, but this time, both are even. The only way their product can be a power of 2 (i.e., 2^j) is if q^v - 1 and q^v + 1 are 2 and 4, so we have 2^j = 2*4 = 8. But tau(8) = 4 (not a prime).

So if p=2, we must have m=1, and thus 2^j + 1 = q. But 2^j + 1 cannot be prime unless j is a power of 2, so we have k = 2^j = 2^(2^u) for some nonnegative integer u such that both tau(k) = tau(2^(2^u)) = 2^u + 1 and k+1 = 2^(2^u) + 1 are prime. However, tau(k) = 2^u + 1 is prime only when it is either 2 (which occurs at u=0, i.e., at k = 2^(2^0) = 2^1 = 2, which is a(1)) or a Fermat prime (cf. A019434), i.e., a prime of the form 2^(2^t)+1 for some nonnegative integer t. So, other than a(1)=2, all even terms k must satisfy k = 2^j and tau(k) = tau(2^j) = j+1 = 2^(2^t)+1, i.e., j=2^(2^t), so k = 2^j = 2^(2^(2^t)), such that tau(k) = 2^(2^t)+1 is a Fermat prime. Only 5 Fermat primes are known: 3, 5, 17, 257, and 65537; these are 2^(2^t)+1 where t = 0, 1, 2, 3, and 4. It is known (see comments at A109434) that 2^(2^t)+1 is composite for all t in 5..32, so since tau(k) must be a prime, t cannot be in 5..32; also, since k+1 must be a prime, t cannot be in 3..5 (these would result in k+1 = 2^(2^8)+1, 2^(2^16)+1, and 2^(2^32)+1, respectively). Consequently, if k is an even term > a(1)=2, we must have k = 2^(2^(2^t)) with t in 0..2 or t >= 33:

.

t k = 2^(2^(2^t)) k+1 tau(k) = 2^(2^t)+1

-- --------------- ------------- ----------------------

0 4 (= a(3)) 5 (prime) 3 (prime)

1 16 (= a(4)) 17 (prime) 5 (prime)

2 65536 (= a(5)) 65537 (prime) 17 (prime)

3 2^(2^8) (composite) 257 (prime)

4 2^(2^16) (composite) 65537 (prime)

5 2^(2^32) (composite) 2^(2^5)+1 (composite)

6 2^(2^64) (?) 2^(2^6)+1 (composite)

. . (?) (composite)

. . (?) (composite)

. . (?) (composite)

32 2^(2^(2^32)) (?) 2^(2^32)+1 (composite)

33 2^(2^(2^33)) (?) 2^(2^33)+1 (?)

.

So a(6), if it exists, must be at least 2^(2^(2^33)). (End)

Examples

			16 is a term because tau(16) = 5 and tau(17) = 2 and 5 and 2 are prime.
147 is not a term because tau(147) = 6 and tau(148) = 6 and 6 is not prime.
157 is not a term because tau(157) = 2 and tau(158) = 4 and 2 is prime but not 4.
		

Crossrefs

Cf. A000005, A000040, A009087.

Programs

Mathematica

Select[Range[1000000], PrimeQ[DivisorSigma[0, #]] && PrimeQ[DivisorSigma[0, #+1]] &] (* Vaclav Kotesovec, Apr 19 2021 *)

PARI

for(k=1,1e8,if(isprime(numdiv(k)) && isprime(numdiv(k+1)),print1(k", ")))