cp's OEIS Frontend

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

%I A281016 #23 Jul 08 2025 17:11:52
%S A281016 8,16,32,64,125,128,256,512,1024,2048,3125,4096,4913,8192,16384,32768,
%T A281016 50653,65536,78125,131072,262144,524288,1030301,1048576,1419857,
%U A281016 1953125,2097152,4194304,7645373,8388608,16777216,16974593,33554432,35831808,48828125,64481201,67108864,69343957
%N A281016 Numbers k such that k, phi(k) and cototient(k) are all perfect powers.
%C A281016 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.
%C A281016 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
%H A281016 David A. Corneth, <a href="/A281016/b281016.txt">Table of n, a(n) for n = 1..547</a> (first 158 terms from Robert Israel, terms <= 10^20)
%e A281016 125 = 5^3 is a term because phi(5^3) = 10^2 and cototient(5^3) = 5^2.
%p A281016 ispow:= proc(n) local F;
%p A281016   F:= ifactors(n)[2];
%p A281016   igcd(F[..,2]) > 1
%p A281016 end proc:
%p A281016 N:= 10^8: # for terms <= N
%p A281016 P:= select(isprime, [2,seq(i,i=3..isqrt(N),2)]):
%p A281016 Cands:= {seq(seq(i^p, i = 2 .. floor(N^(1/p))),p = P)}:
%p A281016 filter:= proc(n) local t; t:= numtheory:-phi(n); ispow(t) and ispow(n-t) end proc:
%p A281016 sort(convert(select(filter, Cands),list)); # _Robert Israel_, Jul 08 2025
%t A281016 Select[Range[10^6], Times @@ Boole@ Map[Or[# == 1, GCD @@ FactorInteger[#][[All, 2]] > 1] &, {#, EulerPhi@ #, # - EulerPhi@ #}] > 0 &] (* _Michael De Vlieger_, Jan 14 2017 *)
%o A281016 (PARI) is(n) = ispower(eulerphi(n)) && ispower(n-eulerphi(n)) && ispower(n);
%Y A281016 Cf. A000010, A001597, A051953, A054754, A166955.
%K A281016 nonn
%O A281016 1,1
%A A281016 _Altug Alkan_, Jan 13 2017