login
A304573
Number of non-perfect powers (A007916) less than n and relatively prime to n.
3
0, 0, 1, 1, 2, 1, 4, 3, 3, 2, 6, 3, 8, 4, 5, 6, 11, 5, 13, 6, 8, 8, 17, 7, 15, 9, 13, 8, 21, 7, 23, 12, 14, 12, 17, 10, 27, 14, 18, 13, 31, 10, 33, 16, 19, 18, 37, 14, 33, 16, 25, 19, 42, 15, 31, 20, 29, 23, 48, 14, 50, 25, 30, 27, 38, 17, 55, 27, 36, 21, 59
OFFSET
1,5
EXAMPLE
The a(21) = 8 positive integers less than and relatively prime to 21 that are not perfect powers are {2, 5, 10, 11, 13, 17, 19, 20}.
MATHEMATICA
Table[Length[Select[Range[2, n], And[GCD@@FactorInteger[#][[All, 2]]==1, GCD[n, #]==1]&]], {n, 50}]
PROG
(PARI) a(n) = sum(k=2, n-1, !ispower(k) && (gcd(n, k) == 1)); \\ Michel Marcus, May 15 2018
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 14 2018
STATUS
approved