A073311 -id:A073311 - cp's OEIS frontend

A008966 a(n) = 1 if n is squarefree, otherwise 0.

1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0

Offset: 1

N. J. A. Sloane

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).

The infinite lower triangular matrix with A008966 on the main diagonal and the rest zeros is the square of triangle A143255. - Gary W. Adamson, Aug 02 2008

Daniel Forgues, Table of n, a(n) for n = 1..100000
Eric Weisstein's World of Mathematics, Moebius Function
Index entries for characteristic functions
Index entries for sequences computed from exponents in factorization of n

Cf. A005117, A008836 (Dirichlet inverse), A013928 (partial sums).
Cf. A179211, A179212, A179213, A179214, A179215.
Cf. A020639, A073576, A087188.
Cf. A124010, A212793, A085357, A156552.
Parity of A002033.
Cf. A047999, A036987
Cf. A082020 (Dgf at s=2), A157289 (Dgf at s=3), A157290 (Dgf at s=4).

a008966 = abs . a008683
-- Reinhard Zumkeller, Dec 13 2015, Dec 15 2014, May 27 2012, Jan 25 2012

Magma
```
[ Abs(MoebiusMu(n)) : n in [1..100]];
```

A008966 := proc(n) if numtheory[issqrfree](n) then 1 ; else 0 ; end if; end proc: # R. J. Mathar, Mar 14 2011

A008966[n_] := Abs[MoebiusMu[n]]; Table[A008966[n], {n, 100}] (* Enrique Pérez Herrero, Apr 15 2010 *)
Table[If[SquareFreeQ[n],1,0],{n,100}] (* or *) Boole[SquareFreeQ/@ Range[ 100]] (* Harvey P. Dale, Feb 28 2015 *)

MuPAD
```
func(abs(numlib::moebius(n)), n):
```
PARI
```
a(n)=if(n<1,0,direuler(p=2,n,1+X))[n]
```

a(n)=issquarefree(n) \\ Michel Marcus, Feb 22 2015

from sympy import factorint
def A008966(n): return int(max(factorint(n).values(),default=1)==1) # Chai Wah Wu, Apr 05 2023

Dirichlet g.f.: zeta(s)/zeta(2s).
a(n) = abs(mu(n)), where mu is the Moebius function (A008683).
a(n) = 0^(bigomega(n) - omega(n)), where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003
Multiplicative with p^e -> 0^(e - 1), p prime and e > 0. - Reinhard Zumkeller, Jul 15 2003
a(n) = 0^(A046951(n) - 1). - Reinhard Zumkeller, May 20 2007
a(n) = 1 - A107078(n). - Reinhard Zumkeller, Oct 03 2008
a(n) = floor(rad(n)/n), where rad() is A007947. - Enrique Pérez Herrero, Nov 13 2009
A175046(n) = a(n)*A073311(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = floor(A000005(n^2)/A007425(n)). - Enrique Pérez Herrero, Apr 15 2010
a(A005117(n)) = 1; a(A013929(n)) = 0; a(n) = A013928(n + 1) - A013928(n). - Reinhard Zumkeller, Jul 05 2010
a(n) * A112526(n) = A063524(n). - Reinhard Zumkeller, Sep 16 2011
a(n) = mu(n) * lambda(n) = A008836(n) * A008683(n). - Enrique Pérez Herrero, Nov 29 2013
a(n) = Sum_{d|n} 2^omega(d)*mu(n/d). - Geoffrey Critzer, Feb 22 2015
a(n) = A085357(A156552(n)). - Antti Karttunen, Mar 06 2017
Limit_{n->oo} (1/n)*Sum_{j=1..n} a(j) = 6/Pi^2. - Andres Cicuttin, Aug 13 2017
a(1) = 1; a(n) = -Sum_{d|n, d < n} (-1)^bigomega(n/d) * a(d). - Ilya Gutkovskiy, Mar 10 2021

Deleted an unclear comment. - N. J. A. Sloane, May 30 2021

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

Original entry on oeis.org

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

A073312 Number of nonsquarefree numbers in the reduced residue system of n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 0, 2, 1, 3, 0, 4, 1, 2, 1, 5, 0, 6, 1, 4, 1, 7, 0, 7, 2, 5, 3, 11, 0, 11, 3, 7, 3, 9, 1, 13, 3, 7, 2, 14, 1, 14, 3, 6, 4, 16, 1, 16, 3, 11, 5, 20, 2, 15, 4, 13, 5, 22, 1, 23, 5, 10, 6, 18, 2, 25, 6, 15, 2, 26, 2, 27, 6, 11, 7, 24, 2, 29, 4, 17, 8, 31, 1, 23, 8, 17, 8, 33, 1, 28

Offset: 1

Reinhard Zumkeller, Jul 25 2002

nonn

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; two of them are not squarefree: 4 and 8, therefore a(15)=2.

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

Cf. A073311, A013929, A000010, A048864, A048865.

Cf. A065463, A104141.

a[n_] := EulerPhi[n] - Module[{rad = Times @@ (First@# & /@ FactorInteger[n])}, Sum[MoebiusMu[k*rad]^2, {k, 1, n}]]; Array[a, 100] (* Amiram Eldar, Mar 08 2020 *)

a(n) + A073311(n) = A000010(n).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (3/Pi^2) * (1 - A065463) = 0.0898387... . - Amiram Eldar, Dec 07 2023

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

A304576 a(n) = Sum_{k < n, k squarefree and relatively prime to n} (-1)^(k-1).

Original entry on oeis.org

1, 1, 0, 2, 1, 2, 1, 4, 2, 3, 1, 4, 2, 5, 2, 7, 3, 6, 4, 7, 4, 9, 5, 8, 5, 10, 3, 9, 5, 8, 5, 13, 5, 13, 5, 11, 7, 15, 5, 14, 8, 11, 8, 17, 6, 18, 8, 15, 8, 17, 7, 19, 10, 16, 9, 20, 9, 23, 12, 15, 13, 25, 8, 26, 10, 18, 13, 26, 11, 22, 14, 22, 15, 30, 9, 29

Offset: 1

Gus Wiseman, May 14 2018

nonn

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

l[n_]:=Sum[(-1)^(k-1),{k,Select[Range[n],And[SquareFreeQ[#],GCD[n,#]==1]&]}];
Table[l[n],{n,100}]

a(n) = sum(k=1, n, if (issquarefree(k) && (gcd(n,k)==1), (-1)^(k-1))); \\ Michel Marcus, May 15 2018

A007457 Number of (j,k): j+k=n, (j,n)=(k,n)=1, j,k squarefree.

Original entry on oeis.org

0, 1, 2, 2, 2, 2, 4, 4, 2, 2, 4, 4, 6, 4, 4, 6, 8, 6, 6, 6, 4, 8, 8, 8, 8, 8, 8, 6, 10, 8, 10, 10, 8, 12, 8, 10, 14, 12, 10, 12, 16, 10, 18, 14, 12, 14, 16, 14, 16, 14, 10, 16, 20, 14, 12, 16, 14, 20, 18, 14, 22, 20, 16, 20

Offset: 1

N. J. A. Sloane, Robert G. Wilson v

Terms are even or 1: range = A004275. [Reinhard Zumkeller, Sep 26 2011]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ernesto Bruno Cossi, Joachim Herzog, Paul R. Smith and Richard Stong, Problem 6623, Amer. Math. Monthly, 99 (1992), 573-575.
R. G. Wilson v, Letter to N. J. A. Sloane, Oct. 1993

Cf. A004275, A073311.

a007457 n = length [k | k <- [1..n-1], gcd k n == 1, a008966 k == 1,
                        let j = n - k, gcd j n == 1, a008966 j == 1]
-- Reinhard Zumkeller, Sep 26 2011

f:=func; [0] cat [#[i:i in [1..n-1]| f(i,n) and f(n-i,n) ]:n in [2..70]]; // Marius A. Burtea, Nov 19 2019

[0] cat [&+[MoebiusMu(i*(n-i))^2:i in [1..n-1]]:n in [2..70]]; // Marius A. Burtea, Nov 19 2019

with(numtheory): seq(add(mobius(i*(n-i))^2, i=1..n-1), n=1..80); # Ridouane Oudra, Nov 18 2019

a[n_] := Count[ Table[ If[ SquareFreeQ[j] && GCD[j, n] == 1, If[k = n-j; SquareFreeQ[k] && GCD[k, n] == 1, 1]], {j, 1, n-1}], 1]; Table[a[n], {n, 1, 64}](* Jean-François Alcover, Nov 28 2011 *)

a(n) = Sum_{i=1..n-1} mu(i*(n-i))^2. - Ridouane Oudra, Nov 18 2019

A091813 Number of positive squarefree integers k<=n satisfying gcd_(k,n)=1, where gcd_(k,n) is the greatest divisor of k that is also a unitary divisor of n.

Original entry on oeis.org

1, 1, 2, 3, 3, 2, 5, 6, 6, 3, 7, 6, 8, 5, 6, 11, 11, 8, 12, 10, 8, 9, 15, 12, 16, 10, 17, 14, 17, 8, 19, 20, 13, 13, 15, 23, 23, 15, 17, 21, 26, 11, 28, 26, 24, 18, 30, 23, 31, 20, 21, 29, 32, 22, 25, 29, 23, 23, 36, 23, 37, 25, 34, 39, 30, 18, 41, 39, 29, 22, 44, 45, 45, 30, 35, 44

Offset: 1

Steven Finch, Mar 07 2004

nonn

			a(4)=3 because each of 1, 2, 3 are squarefree and gcd_*(2,4)=1. The latter follows since 2 is not a unitary divisor of 4. a(5)=3 because 4 is not squarefree.

Steven R. Finch, Mathematical Constants II, Cambridge University Press, 2018, section 1.7, Unitarism and Infinitarism, pp. 49-56.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]

Cf. A047994, A073311.

udiv[n_] := Select[Divisors[n], GCD[#, n/#] == 1 &]; uGCD[a_, b_] := Max[Intersection[Divisors[a], udiv[b]]]; a[n_] := Sum[MoebiusMu[k]^2 * Boole[uGCD[k, n] == 1], {k, 1, n}]; Array[a, 76] (* Amiram Eldar, Oct 01 2019 *)

A169646 Number of squarefree numbers of form k*n, 1 <= k <= n.

Original entry on oeis.org

1, 1, 2, 0, 3, 2, 5, 0, 0, 3, 7, 0, 8, 5, 6, 0, 11, 0, 12, 0, 8, 9, 15, 0, 0, 10, 0, 0, 17, 8, 19, 0, 13, 13, 15, 0, 23, 15, 17, 0, 26, 11, 28, 0, 0, 18, 30, 0, 0, 0, 21, 0, 32, 0, 25, 0, 23, 23, 36, 0, 37, 25, 0, 0, 30, 18, 41, 0, 29, 22, 44, 0, 45, 30, 0, 0, 36, 22, 49, 0, 0, 32, 51, 0, 41, 34

Offset: 1

Reinhard Zumkeller, Apr 05 2010

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..3000

Cf. A000040, A008966, A065473, A073311, A112929, A118259.

[&+[MoebiusMu(k*n)^2: k in [1..n]]: n in [1..80]]; // Vincenzo Librandi, Jul 25 2019

with(numtheory): seq(add(mobius(n*i)^2, i = 1 .. n), n = 1 .. 90); # Ridouane Oudra, Jul 24 2019

Count[#,?SquareFreeQ]&/@Table[k*n,{n,90},{k,n}] (* _Harvey P. Dale, Sep 05 2012 *)
Table[Sum[MoebiusMu[i n]^2, {i, n}], {n, 100}] (* Vincenzo Librandi, Jul 25 2019 *)

a(n) = sum(i = 1, n, issquarefree(i*n)); \\ Amiram Eldar, May 12 2025

a(n) = A008966(n)*A073311(n).
a(A000040(n)) = A112929(n).
a(n) = Sum_{i=1..n} A008966(n*i). - Ridouane Oudra, Jul 24 2019
a(n) = (A118259(n) - A118259(n-1))/2, for n>1. - Ridouane Oudra, May 04 2025
Sum_{k=1..n} a(k) ~ c * n / 2, where c = Product_{p prime} (1 - (3*p-2)/(p^3)) (A065473). - Amiram Eldar, May 12 2025

A231117 Number of positive integers <= n and relatively prime to n which are squarefree if and only if n is squarefree.

Original entry on oeis.org

1, 1, 2, 0, 3, 2, 5, 0, 2, 3, 7, 0, 8, 5, 6, 1, 11, 0, 12, 1, 8, 9, 15, 0, 7, 10, 5, 3, 17, 8, 19, 3, 13, 13, 15, 1, 23, 15, 17, 2, 26, 11, 28, 3, 6, 18, 30, 1, 16, 3, 21, 5, 32, 2, 25, 4, 23, 23, 36, 1, 37, 25, 10, 6, 30, 18, 41, 6, 29, 22, 44, 2, 45, 30, 11, 7, 36, 22, 49, 4, 17, 32

Offset: 1

Irina Gerasimova, Nov 03 2013

nonn

			a(4) = 0 because 4 is not squarefree and phi(4) - A073311(4) = 2 - 2 = 0.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A005117, A073311, A073312.

a(n)=my(s=sum(i=1,n,gcd(n,i)==1&&issquarefree(i))); if(issquarefree(n), s, eulerphi(n)-s) \\ Charles R Greathouse IV, Nov 05 2013

a(n) = A073311(n) if n is squarefree or phi(n) - A073311(n) otherwise. (Where phi is given by A000010)

a(n) = A008966(n)*A073311(n) + A107078(n)*A073312(n). - Antti Karttunen, Nov 26 2013

a(4) corrected and a(54) inserted by Charles R Greathouse IV, Nov 05 2013

cp's OEIS Frontend

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

PARI

Python

Formula

Extensions

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

A073312 Number of nonsquarefree numbers in the reduced residue system of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A304576 a(n) = Sum_{k < n, k squarefree and relatively prime to n} (-1)^(k-1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

A007457 Number of (j,k): j+k=n, (j,n)=(k,n)=1, j,k squarefree.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

A091813 Number of positive squarefree integers k<=n satisfying gcd_(k,n)=1, where gcd_(k,n) is the greatest divisor of k that is also a unitary divisor of n.