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.)
Does a(p) = 2^p for all primes p > 31? (End)
