login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A276044 Least k such that phi(k) has exactly n divisors. 2

%I

%S 1,3,5,7,17,13,85,31,37,65,1285,61,4369,193,185,143,65537,181,327685,

%T 241,577,3281,5570645,403,1297,12289,1057,1037,286331153,779,

%U 1431655765,899,9509,197633,5629,1333

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

%C Least k such that A000005(A000010(k)) = n.

%C From _Jon E. Schoenfield_, Nov 13 2016: (Start)

%C For every n > 0, phi(2^n) = 2^(n-1) has exactly n divisors, so a(n) <= 2^n.

%C For every prime p, since phi(a(p)) has exactly p divisors, phi(a(p)) must be of the form q^(p-1), where q is a prime number. If q >= 3, we would have phi(a(p)) >= 3^(p-1), and since k > phi(k) for every k > 1, we would have a(p) >= 3^(p-1)+1, which would be contradicted by the upper bound a(p) <= 2^p (see above) unless 3^(p-1)+1 <= 2^p, which is true only for p = 2. Thus, for every prime p > 2, phi(a(p)) = 2^(p-1), so a(p) > 2^(p-1). In summary, we can state that, for every prime p > 2:

%C (1) a(p) is the least k such that phi(k) = 2^(p-1), and

%C (2) 2^(p-1) < a(p) <= 2^p.

%C 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.

%C For prime p < 37, a(p) = A001317(p-1).

%C 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 1-bits in p-1:

%C . p-1 in

%C p a(p) prime factorization of a(p) binary

%C == ========== =========================== ======

%C 2 3 = 3 1

%C 3 5 = 5 10

%C 5 17 = 17 100

%C 7 85 = 17 * 5 110

%C 11 1285 = 257 * 5 1010

%C 13 4369 = 257 * 17 1100

%C 17 65537 = 65537 10000

%C 19 327685 = 65537 * 5 10010

%C 23 5570645 = 65537 * 17 * 5 10110

%C 29 286331153 = 65537 * 257 * 17 11100

%C 31 1431655765 = 65537 * 257 * 17 * 5 11110

%C .

%C 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_.)

%C Does a(p) = 2^p for all primes p > 31? (End)

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

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

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

%Y Cf. A000005, A000010, A001317, A019434, A038183, A062821.

%K nonn,more

%O 1,2

%A _Altug Alkan_, Aug 17 2016

%E a(31)-a(36) from _Michel Marcus_ and _Jon E. Schoenfield_, Nov 13 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 19 12:35 EDT 2019. Contains 325159 sequences. (Running on oeis4.)