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,1

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

Links

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

Example

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

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 *)

Prog

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

Crossrefs

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

Sequence in context: A192135 A345053 A256817 * A391626 A048169 A089882

Adjacent sequences: A281013 A281014 A281015 * A281017 A281018 A281019

Keyword

nonn

Author

Altug Alkan, Jan 13 2017

Status

approved