A396489 - OEIS

A396489

Least k such that psi(k) has exactly n divisors, where psi = A002322 is the reduced totient function.

1, 3, 5, 7, 17, 13, 256, 31, 37, 113, 4096, 61, 16384, 193, 323, 211, 65537, 181, 1048576, 241, 577, 13313, 16777216, 421, 1297, 12289, 1919, 2113, 1073741824, 1009, 4294967296, 1321, 25601, 458759, 24803, 1801, 274877906944, 786433, 233491, 2161, 4398046511104, 4801

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

For every n >= 2, psi(2^(n+1)) = 2^(n-1) has exactly n divisors, so a(n) <= 2^(n+1).

We have psi(a(p)) = 2^(p-1) for every prime p. Since psi(p1^e1 * p2^e2 * ... * pr^er) = lcm(psi(p1^e1), ..., psi(pr^er)), a(p) must actually be a prime power, that is, either a power of 2 or a Fermat prime F = 2^2^t + 1. Suppose that p > 2:

- If a(p) is a power of 2, then a(p) = 2^(p+1).

- If a(p) is a Fermat prime, then p = 2^t + 1 must itself be a Fermat prime.

We know that any Fermat prime larger than 2^2^4 + 1 must be at least 2^2^33 + 1. Since for p = 2^2^3 + 1 or 2^2^4 + 1 we know that 2^2^2^3 + 1 or 2^2^2^4 + 1 is not prime (so a(p) can't be a Fermat prime in these two cases), we have a(p) = 2^(p+1) for all primes p < 2^2^33 + 1 other than p = 2, 3, 5, 17.

See my pdf link for the calculation of a(n) with semiprime n.

LINKS

Jianing Song, Table of n, a(n) for n = 1..241

Jianing Song, A396489 on semiprimes <= 10^4.

Jianing Song, Notes on A396489.

Jianing Song, PARI Program.

MATHEMATICA

a[n_]:=Module[{k=1}, While[DivisorSigma[0, CarmichaelLambda[k]]!=n, k++]; k]; Array[a, 22] (* James C. McMahon, May 31 2026 *)

PROG

(PARI) \\ See Links.

CROSSREFS

Cf. A002322, A066800 (number of divisors of psi), A276044 (for EulerPhi), A395584 (for psi/2).