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
Keywords
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
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
Comments