cp's OEIS Frontend

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

%I A304574 #26 Apr 05 2025 18:27:17
%S A304574 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 A304574 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 A304574 11,5,8,3,11,3,11,5,7,5,10,3,11,4,8,6,12,2
%N A304574 Number of perfect powers (A001597) less than n and relatively prime to n.
%H A304574 Michael De Vlieger, <a href="/A304574/b304574.txt">Table of n, a(n) for n = 1..10000</a>
%H A304574 Michael De Vlieger, <a href="/A304574/a304574.png">Log log scatterplot of a(n)</a>, n = 2..2^16, showing prime n in red, proper prime powers n in gold, squarefree composite n in green, and numbers n that are neither squarefree nor prime powers in blue and purple, where purple represents powerful n that are not prime powers. Large green points highlight composite primorials n.
%e A304574 The a(33) = 6 perfect powers less than and relatively prime to 33 are {1, 4, 8, 16, 25, 32}.
%t A304574 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 A304574 (PARI) ispow(n) = (n==1) || ispower(n);
%o A304574 a(n) = #select(x->(ispow(x) && (gcd(n, x) == 1)), [1..n-1]); \\ _Michel Marcus_, May 17 2018
%o A304574 (Sage)
%o A304574 def a(n):
%o A304574     return len([k for k in (1..n-1) if k.is_perfect_power() and gcd(n,k) == 1])
%o A304574 [a(n) for n in (1..84)] # _Peter Luschny_, May 16 2018
%Y A304574 Cf. A000010, A000961, A001597, A005117, A007916, A073311, A139555, A304326, A304362, A304573, A304575, A304576.
%K A304574 nonn
%O A304574 1,5
%A A304574 _Gus Wiseman_, May 14 2018
%E A304574 a(1) = 0 corrected by _Zak Seidov_, May 15 2018