A304576 -id:A304576 - cp's OEIS frontend

A304575 a(n) = Sum_{d|n} #{k < d, k squarefree and relatively prime to d}.

1, 2, 3, 4, 4, 6, 6, 8, 7, 8, 8, 12, 9, 12, 12, 15, 12, 16, 13, 17, 16, 18, 16, 24, 17, 20, 20, 23, 18, 26, 20, 28, 23, 26, 24, 33, 24, 29, 28, 35, 27, 35, 29, 37, 34, 35, 31, 46, 32, 38, 35, 41, 33, 45, 36, 47, 38, 42, 37, 54, 38, 46, 46, 54, 42, 53, 42, 54

Offset: 1

Gus Wiseman, May 14 2018

nonn

Note that a(n) <= n.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A005117, A008683, A073311, A111972, A112399, A139555, A265675, A304573, A304575, A304576.

s[n_]:=Length[Select[Range[n],And[SquareFreeQ[#],GCD[n,#]===1]&]];
Table[DivisorSum[n,s],{n,100}]

a(n) = sumdiv(n, d, #select(k->(issquarefree(k) && (gcd(k, d)==1)), [1..d])); \\ Michel Marcus, May 15 2018

a(n) = Sum_{d|n} A073311(d) (inverse Moebius transform of A073311). - Amiram Eldar, Nov 21 2024

A304574 Number of perfect powers (A001597) less than n and relatively prime to n.

Original entry on oeis.org

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

Gus Wiseman, May 14 2018

nonn

			The a(33) = 6 perfect powers less than and relatively prime to 33 are {1, 4, 8, 16, 25, 32}.

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.

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

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 *)

ispow(n) = (n==1) || ispower(n);
a(n) = #select(x->(ispow(x) && (gcd(n, x) == 1)), [1..n-1]); \\ Michel Marcus, May 17 2018

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

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

A304573 Number of non-perfect powers (A007916) less than n and relatively prime to n.

Original entry on oeis.org

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

Gus Wiseman, May 14 2018

nonn

			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}.

Cf. A000005, A000010, A000961, A001597, A005117, A007916, A008683, A073311, A139555, A304326, A304362, A304574, A304575, A304576.

Table[Length[Select[Range[2,n],And[GCD@@FactorInteger[#][[All,2]]==1,GCD[n,#]==1]&]],{n,50}]

a(n) = sum(k=2, n-1, !ispower(k) && (gcd(n, k) == 1)); \\ Michel Marcus, May 15 2018

cp's OEIS Frontend

A304575 a(n) = Sum_{d|n} #{k < d, k squarefree and relatively prime to d}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A304574 Number of perfect powers (A001597) less than n and relatively prime to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Extensions

A304573 Number of non-perfect powers (A007916) less than n and relatively prime to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI