Squarefree

Author

Eric W. Weisstein
September 1, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/Squarefree.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Squarefree.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Definition

?SquareFreeQ

SquareFreeQ/@{0,1}

SquareFreeQ/@Range[-5,0]

Examples

SquareFreeQ[0]

SquareFreeQ[1]

...contradicts docs...

SquareFreeQ[4]

SquareFreeQ[x]

SquareFreeQ[x^2]

SquareFreeQ[-1.]

SquareFreeQ[I]

Enumeration

Position[Range[10],_?SquareFreeQ]//Flatten

Sums

(∑_n^∞)((Boole[SquareFreeQ[n]])/(n^s))==((ζ(s))/(ζ(2 s)))

Sum[((Boole[SquareFreeQ[n]])/(n^s)),{n,∞}]

Sum[((Piecewise[{{1,SquareFreeQ[n]}}])/(n^s)),{n,∞}]

(∑_n^∞)(((Piecewise[{{1, (MoebiusMu[n])≠0}}]))/(n^s))==((ζ(s))/(ζ(2 s)))

Sum[((Piecewise[{{1,MoebiusMu[n]≠0}}])/(n^s)),{n,∞}]//InputForm

{Sum[Piecewise[{{1, MoebiusMu[n] != 0}}, 0]/n^s, {n, 100}],Zeta[s]/Zeta[2s]}/.s->3.2

Summatory

Q[n] == s.f. < n

Accumulate[Table[Boole[SquareFreeQ[n-1]],{n,20}]]

Q(n)==(∑_k^(n-1))((MoebiusMu[k])^2)

Sum[((MoebiusMu[k])^2),{k,n-1}]

Table[Sum[((MoebiusMu[k])^2),{k,n-1}],{n,21}]

Q(n)==(∑_k^(n-1))|(MoebiusMu[k])|

Sum[Abs[MoebiusMu[k]],{k,n-1}]

Table[Sum[Abs[MoebiusMu[k]],{k,n-1}],{n,21}]

Q(n)==(∑_d^(⌊(Sqrt[n-1])⌋))(MoebiusMu[d]) ⌊((n-1)/(d^2))⌋

Sum[MoebiusMu[d]Floor[((n-1)/(d^2))],{d,Floor[Sqrt[n-1]]}]

Table[Sum[MoebiusMu[d]Floor[((n-1)/(d^2))],{d,Floor[Sqrt[n-1]]}],{n,21}]

Q(n)==(∑_k^(n-1))(MoebiusMu[n-k]) mod 2

Sum[Mod[MoebiusMu[n-k],2],{k,n-1}]

Table[Sum[Mod[MoebiusMu[n-k],2],{k,n-1}],{n,21}]

Q(n)==(∑_k^(n-1))|(MoebiusMu[n-k])|

Sum[Abs[MoebiusMu[n-k]],{k,n-1}]

Table[Sum[Abs[MoebiusMu[n-k]],{k,n-1}],{n,21}]

Counts

N[6/Pi^2,10]

s=If[SquareFreeQ[#],1,0]&/@Range[1+10^6];//Timing

c=Accumulate[s];

c[[10^#]]&/@Range[6]

-Subtract@@@Partition[{7,61,608,6083,60794,607926,6079291},2,1]

a=FoldList[Plus,1,{6,54,547,5475,54711,547132,5471365,54713403,547134430,5471343818}]

N[MapIndexed[#1/10^#2[[1]]&,a],10]

Plot

<<Utilities`Plot`

With[{nn=150},
IntegerListPlot[Take[c,nn],Epilog->{Dashing[{.02}],Blue,Line[{{0,0},{nn,6 nn/Pi^2}}]},
AxesLabel->TraditionalForm/@{n,Q[n]}
]]

Squareful are shown in black

ListDensityPlot[Partition[If[#,1,0]&/@SquareFreeQ/@Range[0,100^2],100],
Mesh->False,
FrameLabel->TraditionalForm/@{Mod[n,100],Floor[n/100]}]

ListDensityPlot[Partition[If[#,1,0]&/@SquareFreeQ/@Range[0,250^2],250],
Mesh->False,
FrameLabel->TraditionalForm/@{Mod[n,250],Floor[n/250]}]

KroneckerDelta[1]

Asymptotic Density

N[6/Pi^2,20]

<<Utilities`Typesetting`

ListPlot[MapIndexed[{#2[[1]],#1}&,c/Range[Length[c]]][[1;;All;;100]],PlotStyle->Red,Joined->True,
Epilog->{Blue,Line[{{0,#},{10^6,#}}]&[6/Pi^2]},
AxesLabel->{n,InlineFraction[Q[n],n]}]

Probability that Two Consecutive numbers are Squarefree

(∏_(n=1)^∞)(1-(2/(Subscript[p, n]^2)))

Times@@(N[1,20]-2/#^2&/@Prime[Range[10^5]])

Times@@(N[1,20]-2/#^2&/@Prime[Range[10^6]])

l=BitAnd@@@Partition[s,2,1];

t=Accumulate[l];

two={#,#+1}&/@Flatten[Position[Take[l,10],1]]

Map[SquareFreeQ,two,{2}]

t[[10^#]]&/@Range[Floor[Log[10,Length[t]]]]

-Subtract@@@Partition[{5,33,323,3230,32269,322619},2,1]

a2=FoldList[Plus,1,{4,28,290,2907,29039,290350,2903724,29037034,290370904,2903706615}]

ListPlot[MapIndexed[{#2[[1]],#1}&,t/Range[Length[t]]][[1;;All;;100]],Joined->True,
PlotStyle->Red,Epilog->{Blue,Line[{{0,#},{Length[l],#}}]&[0.322642294581787]},
AxesLabel->TraditionalForm/@{n,InlineFraction[(Subscript[Q, 2])[n],n]}]

Gaussian Integers

GaussianSquareFreeQ[c_]:=Times@@(Last/@FactorInteger[c,GaussianIntegers->True])===1

FactorInteger[2,GaussianIntegers->True]

SquareFreeQ[2]

GaussianSquareFreeQ[2]

N[6/Pi^2/Catalan,10]

With[{n=200},
Count[Flatten[Table[GaussianSquareFreeQ[x+I y],{x,-n,n},{y,-n,n}]],True]/(2n+1)^2
]//N//Timing

With[{n=500},
Count[Flatten[Table[GaussianSquareFreeQ[x+I y],{x,-n,n},{y,-n,n}]],True]/(2n+1)^2
]//N//Timing

With[{n=200},pts=Flatten[Table[x+I y,{x,-n,n},{y,-Floor[Sqrt[n^2-x^2]],Floor[Sqrt[n^2-x^2]]}]
];
Count[pts,_?GaussianSquareFreeQ]/Length[pts]
]//N//Timing

With[{n=500},pts=Flatten[Table[x+I y,{x,-n,n},{y,-Floor[Sqrt[n^2-x^2]],Floor[Sqrt[n^2-x^2]]}]
];
Count[pts,_?GaussianSquareFreeQ]/Length[pts]
]//N//Timing