A184968 Smallest k such that phi(phi(k)) = 2^n, where phi is the Euler totient function.

5, 11, 17, 41, 85, 137, 257, 641, 1285, 2329, 4369, 10537, 17477, 35209, 65537, 163841, 297109, 557057, 1114129, 2687017, 4491589, 8978569, 16843009, 42009217, 71304257, 143163649, 286331153, 690563369, 1145390149, 2281701377, 4295098369, 10737647617

Offset: 1

Author

Michel Lagneau, Mar 27 2011

Keywords

• nonn

Examples

			a(5) = 85 because phi(85) = 64, phi(64) = 2^5.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..1000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A010554.

Programs

Maple

with(numtheory):for n from 1 to 22 do: id:=0:for k from 1 to 10000000 while(id=0)
  do: if phi(phi(k)) =2^n then id:=1:print(k):else fi:od:od:
# Alternative:
f:= proc(n) local S,s,r;
  uses numtheory;
  S:= sort(convert(invphi(2^n),list));
  r:= infinity;
  for s in S while s < r do
    r:= min(r, min(invphi(s)))
  od;
  r
end proc:
map(f, [$1..50]); # Robert Israel, Mar 22 2017

PARI

a(n) = {my(v = invphi(2^n), m); for(i = 1, #v, m = invphiMin(v[i]); v[i] = max(m, 0)); vecmin(select(x -> x > 0, v)); } \\ Amiram Eldar, Nov 15 2024, using Max Alekseyev's invphi.gp

Extensions

a(23)-a(32) from Donovan Johnson, Jul 28 2011