|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
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
|
|
CROSSREFS
|
Cf. A000005, A000010, A000961, A001597, A005117, A007916, A008683, A073311, A139555, A304326, A304362, A304574, A304575, A304576.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|