A071068 Number of ways to write n as a sum of two unordered squarefree numbers.

0, 1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 4, 3, 3, 3, 5, 4, 4, 3, 6, 4, 5, 4, 7, 5, 5, 5, 7, 5, 5, 5, 8, 6, 7, 6, 11, 7, 7, 7, 11, 8, 8, 9, 13, 10, 8, 8, 13, 10, 8, 7, 14, 10, 10, 7, 13, 10, 11, 9, 15, 11, 11, 11, 15, 11, 11, 11, 18, 12, 13, 11, 21, 13, 14, 13, 20, 14, 13, 14, 20, 16, 13, 13, 22, 15

Offset: 1

Author

Benoit Cloitre, May 26 2002

Keywords

• easy
• nonn

Comments

The natural density of the squarefree numbers is 6/Pi^2, so An < a(n) < Bn for all large enough n with A < 6/Pi^2 - 1/2 and B > 3/Pi^2. The Schnirelmann density of the squarefree numbers is 53/88 > 1/2, and so a(n) > 0 for all n > 1 (in fact, a(n+1) >= 9n/88). It follows from Theoreme 3 bis. in Cohen, Dress, & El Marraki along with finite checking up to 16089908 that 0.10792n < a(n) < 0.303967n for n > 36. (The lower bound holds for n > 1.) - Charles R Greathouse IV, Feb 02 2016

Examples

			12=1+11=2+10=5+7=6+6 hence a(12)=4.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Henri Cohen, Francois Dress, and Mahomed El Marraki, Explicit estimates for summatory functions linked to the Möbius μ-function, Funct. Approx. Comment. Math. 37:1 (2007), pp. 51-63.

Crossrefs

Cf. A005117, A008683 (mu), A008966, A098235, A262991, A294101.

Programs

Mathematica

Table[Sum[Abs[MoebiusMu[i] MoebiusMu[n - i]],{i, 1, Floor[n/2]}],{n, 1, 85}] (* Indranil Ghosh, Mar 10 2017 *)
Table[Count[IntegerPartitions[n,{2}],?(AllTrue[#,SquareFreeQ]&)],{n,90}] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale, Aug 13 2020 *)

PARI

a(n)=sum(i=1,n\2,issquarefree(i)&&issquarefree(n-i)) \\ Charles R Greathouse IV, May 21 2013

PARI

list(lim)=my(n=lim\1); concat(0, ceil(Vec((Polrev(vector(n, k, issquarefree(k-1))) + O('x^(n+1)))^2)/2)) \\ Charles R Greathouse IV, May 21 2013

PARI

a(n)=my(s); forsquarefree(k=1,n\2, issquarefree(n-k[1]) && s++); s \\ Charles R Greathouse IV, Dec 20 2024

Formula

a(n) = Sum_{k=1..floor(n/2)} mu(k)^2 * mu(n-k)^2. - Wesley Ivan Hurt, May 20 2013

a(n) = (A262991(n) - A294101(n))/2. - Wesley Ivan Hurt, Jul 16 2025