login
A304574
Number of perfect powers (A001597) less than n and relatively prime to n.
2
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,5
EXAMPLE
The a(33) = 6 perfect powers less than and relatively prime to 33 are {1, 4, 8, 16, 25, 32}.
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 *)
PROG
(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
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 14 2018
EXTENSIONS
a(1) = 0 corrected by Zak Seidov, May 15 2018
STATUS
approved