A304574 - OEIS

%I #22 May 18 2018 06:33:08

%S 0,1,1,1,2,1,2,1,3,2,4,1,4,2,3,2,5,1,5,2,4,2,5,1,5,3,5,4,7,1,7,4,6,4,

%T 7,2,9,4,6,3,9,2,9,4,5,4,9,2,9,4,7,5,10,3,9,4,7,5,10,2,10,5,6,5,10,3,

%U 11,5,8,3,11,3,11,5,7,5,10,3,11,4,8,6,12,2

%N Number of perfect powers (A001597) less than n and relatively prime to n.

%e The a(33) = 6 perfect powers less than and relatively prime to 33 are {1, 4, 8, 16, 25, 32}.

%t Table[Length[Select[Range[n-1],And[#==1||GCD@@FactorInteger[#][[All,2]]>1,GCD[n,#]==1]&]],{n,100}] (* Corrected by _Peter Luschny_, May 17 2018 *)

%o (PARI) ispow(n) = (n==1) || ispower(n);

%o a(n) = #select(x->(ispow(x) && (gcd(n, x) == 1)), [1..n-1]); \\ _Michel Marcus_, May 17 2018

%o (Sage)

%o def a(n):

%o     return len([k for k in (1..n-1) if k.is_perfect_power() and gcd(n,k) == 1])

%o [a(n) for n in (1..84)] # _Peter Luschny_, May 16 2018

%Y Cf. A000010, A000961, A001597, A005117, A007916, A073311, A139555, A304326, A304362, A304573, A304575, A304576.

%K nonn

%O 1,5

%A _Gus Wiseman_, May 14 2018

%E a(1) = 0 corrected by _Zak Seidov_, May 15 2018