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

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, 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, 11, 5, 8, 3, 11, 3, 11, 5, 7, 5, 10, 3, 11, 4, 8, 6, 12, 2

Offset: 1

Author

Gus Wiseman, May 14 2018

Keywords

• nonn

Examples

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Log log scatterplot of a(n), 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.

Crossrefs

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

Programs

Mathematica

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

PARI

ispow(n) = (n==1) || ispower(n);
a(n) = #select(x->(ispow(x) && (gcd(n, x) == 1)), [1..n-1]); \\ Michel Marcus, May 17 2018

Sage

def a(n):
    return len([k for k in (1..n-1) if k.is_perfect_power() and gcd(n,k) == 1])
[a(n) for n in (1..84)] # Peter Luschny, May 16 2018

Extensions

a(1) = 0 corrected by Zak Seidov, May 15 2018