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,5

Links

Table of n, a(n) for n=1..84.

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

Crossrefs

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

Sequence in context: A194835 A054065 A194868 * A139024 A217317 A331128

Adjacent sequences: A304571 A304572 A304573 * A304575 A304576 A304577

Keyword

nonn

Author

Gus Wiseman, May 14 2018

Extensions

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

Status

approved