A309906 - OEIS

%I #39 May 15 2023 08:44:15

%S 4,32,8,160,8,384,8,384,16,256,8,7680,8,128,32,1792,8,4096,8,3840,32,

%T 256,8,36864,16,128,32,2560,8,24576,8,4096,32,128,32,327680,8,128,32,

%U 36864,8,18432,8,2560,128,256,8,344064,16,1024,32,2560,8,20480,32

%N a(n) is the smallest number of divisors of p^n - 1 that may possibly occur for arbitrarily large primes p.

%C The existence of infinitely many primes p such that p^n - 1 has exactly a(n) divisors is conjectured. E.g., although it is known that p-1 has fewer than 4 divisors for only finitely many primes p (see Example section), it is not known whether there exist infinitely many primes p such that p-1 has exactly 4 divisors. (Thanks to _Jianing Song_, who pointed out the need for this clarification.) - _Jon E. Schoenfield_, Mar 04 2021

%C For each prime q, every number k that has exactly q divisors is a prime power k = p^(q-1) for some prime p. As a result, a(q-1) can be useful in identifying numbers of the form p^(q-1) - 1 that are terms of A161460 (see Example section).

%C From _Bernard Schott_, Aug 22 2019: (Start)

%C For n prime >= 3, a(n) = 8;

%C for n = q^2, q prime >= 3, a(n) = 16. (End)

%H Antti Karttunen, <a href="/A309906/b309906.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A000005(A079612(n))*2^A000005(n).

%F a(n) = 2^(A000005(n)+1) for odd n. - _Jianing Song_, Dec 05 2021

%e a(1) = 4: The only primes p for which p-1 has fewer than 4 divisors are 2, 3, and 5; for all primes p > 5, p-1 has at least 4 divisors, and the terms in A005385 (Safe primes) except 5 are primes p such that p-1 has exactly 4 divisors.

%e a(2) = 32: p^2 - 1 = (p-1)*(p+1) has fewer than 32 divisors only for p = 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 47, and 73; for all primes p such that the product of the 3-smooth parts of p-1 and p+1 is 24 and p-1 and p+1 each have one prime factor > 3, p^2 - 1 has exactly 32 divisors (see A341658).

%e a(4) = 160: primes p such that p^4 - 1 has exactly 160 divisors are plentiful (see A341662), but only p = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 59, 61, 71, 79, and 101 yield tau(p^4 - 1) < 160. Of these, p = 13, 29, 59, and 61 all give tau(p^4 - 1) = 80; 37 and 101 both give 120 divisors; and 41 and 71 both give 144. For each of the ten remaining primes (p = 2, 3, 5, 7, 11, 17, 19, 23, 31, 79), the value of tau(p^4 - 1) is unique, so each of those ten values of p^4 - 1 is a term in A161460.

%o (PARI) f(n) = {if (n%2, 2, res = 1; forprime(p=2, n+1, if (!(n % (p-1)), t = valuation(n, p); if (p==2, if (t, res *= p^(t+2)), res *= p^(t+1)); ); ); res; ); } \\ A079612

%o a(n) = numdiv(f(n))*2^numdiv(n); \\ _Michel Marcus_, Aug 22 2019

%Y Cf. A000005, A005385, A006863, A079612, A161460, A341658, A341662, A341670.

%K nonn

%O 1,1

%A _Jon E. Schoenfield_, Aug 21 2019

%E Name edited by _Jon E. Schoenfield_, Mar 04 2021