A281016 Numbers k such that k, phi(k) and cototient(k) are all perfect powers.

8, 16, 32, 64, 125, 128, 256, 512, 1024, 2048, 3125, 4096, 4913, 8192, 16384, 32768, 50653, 65536, 78125, 131072, 262144, 524288, 1030301, 1048576, 1419857, 1953125, 2097152, 4194304, 7645373, 8388608, 16777216, 16974593, 33554432, 35831808, 48828125, 64481201, 67108864, 69343957

Offset: 1

Author

Altug Alkan, Jan 13 2017

Keywords

• nonn

Comments

This sequence does not contain only prime powers. Least term that has a prime factor which is not of the form m^2 + 1 is 35831808 = 2^14 * 3^7. The next one is 102503232 = 2^6 * 3^6 * 13^3. There are infinitely many such numbers.

Contains 2^a * 3^b whenever min(GCD(a,b), GCD(a,b-1), GCD(a+1,b-1)) > 1, e.g. if a == 14 (mod 42) and b == 7 (mod 42). - Robert Israel, Jul 08 2025

Examples

			125 = 5^3 is a term because phi(5^3) = 10^2 and cototient(5^3) = 5^2.
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..547 (first 158 terms from Robert Israel, terms <= 10^20)

Crossrefs

Cf. A000010, A001597, A051953, A054754, A166955.

Programs

Maple

ispow:= proc(n) local F;
  F:= ifactors(n)[2];
  igcd(F[..,2]) > 1
end proc:
N:= 10^8: # for terms <= N
P:= select(isprime, [2,seq(i,i=3..isqrt(N),2)]):
Cands:= {seq(seq(i^p, i = 2 .. floor(N^(1/p))),p = P)}:
filter:= proc(n) local t; t:= numtheory:-phi(n); ispow(t) and ispow(n-t) end proc:
sort(convert(select(filter, Cands),list)); # Robert Israel, Jul 08 2025

Mathematica

Select[Range[10^6], Times @@ Boole@ Map[Or[# == 1, GCD @@ FactorInteger[#][[All, 2]] > 1] &, {#, EulerPhi@ #, # - EulerPhi@ #}] > 0 &] (* Michael De Vlieger, Jan 14 2017 *)

PARI

is(n) = ispower(eulerphi(n)) && ispower(n-eulerphi(n)) && ispower(n);