

A276044


Least k such that phi(k) has exactly n divisors.


3



1, 3, 5, 7, 17, 13, 85, 31, 37, 65, 1285, 61, 4369, 193, 185, 143, 65537, 181, 327685, 241, 577, 3281, 5570645, 403, 1297, 12289, 1057, 1037, 286331153, 779, 1431655765, 899, 9509, 197633, 5629, 1333, 137438953472, 786433, 42653, 1763, 2199023255552, 2993, 8796093022208, 15361, 3737, 12648641
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Least k such that A000005(A000010(k)) = n.
From Jon E. Schoenfield, Nov 13 2016: (Start)
For every n > 0, phi(2^n) = 2^(n1) has exactly n divisors, so a(n) <= 2^n.
For every prime p, since phi(a(p)) has exactly p divisors, phi(a(p)) must be of the form q^(p1), where q is a prime number. If q >= 3, we would have phi(a(p)) >= 3^(p1), and since k > phi(k) for every k > 1, we would have a(p) >= 3^(p1)+1, which would be contradicted by the upper bound a(p) <= 2^p (see above) unless 3^(p1)+1 <= 2^p, which is true only for p = 2. Thus, for every prime p > 2, phi(a(p)) = 2^(p1), so a(p) > 2^(p1). In summary, we can state that, for every prime p > 2:
(1) a(p) is the least k such that phi(k) = 2^(p1), and
(2) 2^(p1) < a(p) <= 2^p.
After a(36)=1333, the next few known terms are a(38)=786433, a(39)=42653, a(40)=1763, and a(42)=2993; as shown above, known bounds on a(37) and a(41) are 2^36 < a(37) <= 2^37 and 2^40 < a(41) <= 2^41.
For prime p < 37, a(p) = A001317(p1).
Observation: for prime p < 37, a(p) is the product of distinct Fermat primes 2^(2^j)+1 for j=0..4, i.e., 3, 5, 17, 257, and 65537 (see A019434), according to the locations of the 1bits in p1:
. p1 in
p a(p) prime factorization of a(p) binary
== ========== =========================== ======
2 3 = 3 1
3 5 = 5 10
5 17 = 17 100
7 85 = 17 * 5 110
11 1285 = 257 * 5 1010
13 4369 = 257 * 17 1100
17 65537 = 65537 10000
19 327685 = 65537 * 5 10010
23 5570645 = 65537 * 17 * 5 10110
29 286331153 = 65537 * 257 * 17 11100
31 1431655765 = 65537 * 257 * 17 * 5 11110
.
This pattern does not continue to p=37, since 2^(2^5)+1 is not prime. (See also A038183 and the observation there from Arkadiusz Wesolowski.)
As noted, for every prime p, phi(a(p))=2^(p1), decompose a(p) = p_1^(e_1) *...* p_m^(e_m), then phi(a(p)) = p_1^(e_11)*(p_1  1) * ... * p_m^(e_m1)*(p_m  1). Thus a(p) is of the form 2^e * F_(a_1) *...* F_(a_l), where F_(a_i) = 2^(a_i) + 1 denote distinct Fermat primes. If e = 0, a_1 + ... + a_l = p  1, while if e > 0, e + a_1 + ... + a_l = p. It can be deduced that a(p) = 2^p unless p1 can be written as a_1 + ... a_l where 2^(a_i) + 1 are distinct Fermat primes. The only Fermat primes known have a_i in {1,2,4,8,16} and it is known that 2^a + 1 is composite for 16 < a < 2^33 (cf. A019434). It follows from the fact that 1 + 2 + 4 + 8 + 16 = 31 that a(p) = 2^p for primes p with 32 < p <= 2^33.  Pjotr Buys, Sep 18 2019


LINKS

David A. Corneth, Table of n, a(n) for n = 1..512


FORMULA

a(p) = 2^p for primes p with 32 < p <= 2^33.  Pjotr Buys, Sep 18 2019


EXAMPLE

a(5) = 17 because phi(17) = 16 has 5 positive divisors.


MATHEMATICA

Table[k = 1; While[DivisorSigma[0, #] &@ EulerPhi@ k != n, k++]; k, {n, 28}] (* Michael De Vlieger, Aug 21 2016 *)


PROG

(PARI) a(n) = {my(k = 1); while(numdiv(eulerphi(k)) != n, k++); k; }


CROSSREFS

Cf. A000005, A000010, A001317, A002181, A019434, A038183, A062821.
Sequence in context: A112092 A031441 A078150 * A114265 A258195 A110358
Adjacent sequences: A276041 A276042 A276043 * A276045 A276046 A276047


KEYWORD

nonn


AUTHOR

Altug Alkan, Aug 17 2016


EXTENSIONS

a(31)a(36) from Michel Marcus and Jon E. Schoenfield, Nov 13 2016
a(37)a(46) from Pjotr Buys, Sep 18 2019


STATUS

approved



