A098983 Number of ways of writing n as a sum of a prime and a squarefree number.

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

Offset: 0

Author

N. J. A. Sloane, Oct 24 2004

Keywords

• nonn
• nice

Comments

From a posting by Hugh Montgomery to the Number Theory mailing list, Oct 05 2004: "Estermann, JLMS (1931), established an asymptotic formula for a(n). Page, PLMS (1935), gave a quantitative version of this, with an error term roughly (log n)^5 smaller than the main term. Walfisz, Zur additiven Zahlentheorie II, Math. Z. 40 (1936), 592-607, established what we know today as the "Siegel-Walfisz theorem" in a series of lemmas and used this new tool to give the formula for a(n) with an error term that is smaller by a factor (log n)^c for any c."

Examples

			a(8) = 4: 8=2+6=3+5=5+3=7+1.
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..10000
• Adrian Dudek, On the Sum of a Prime and a Square-free Number, arXiv:1410.7459 [math.NT], 2014.
• T. Estermann, On the representations of a number as the sum of a prime and a quadratfrei number, J. London Math. Soc., S1-6(3):219, 1931.
• Forrest J. Francis and Ethan S. Lee, Additive Representations of Natural Numbers, #A14 INTEGERS 22 (2022).
• Shehzad Hathi and Daniel R. Johnston, On the sum of a prime and a square-free number with divisibility conditions, Journal of Number Theory Volume 256, March 2024, pp. 354-372. arXiv:2109.11883 [math.NT]
• A. Page, On the Number of Primes in an Arithmetic Progression, Proc London Math Soc (1935) s2-39 (1): 116-141.
• A. Walfisz, Zur additiven Zahlentheorie II, Math. Z. 40 (1936), 592-607.

Programs

Haskell

a098983 n = sum $ map (a008966 . (n -)) $ takeWhile (< n) a000040_list
-- Reinhard Zumkeller, Sep 14 2011

Mathematica

m = 90; sf = Total[ x^Select[Range[m], SquareFreeQ] ]; pp = Sum[x^Prime[n], {n, 1, PrimePi @ Exponent[sf[[-1]], x]}]; CoefficientList[Series[pp * sf, {x, 0, m-1}], x] (* Jean-François Alcover, Jul 20 2011 *)

PARI

a(n)=my(s);forprime(p=2,n,s+=issquarefree(n-p));s \\ Charles R Greathouse IV, Jun 20 2013

PARI

a(n)=my(s);forsquarefree(k=1,n-2,if(isprime(n-k[1]),s++));s \\ Charles R Greathouse IV, Dec 23 2020

Formula

G.f.: (x^2+x^3+x^5+x^7+x^11+x^13+x^17+x^19+...)(x+x^2+x^3+x^5+x^6+x^7+x^10+x^11+x^13+x^14+x^15+x^17+x^19+...).

a(n+1) = Sum_{k=1..n} A008966(k)*A010051(n-k+1) for n>0. [Reinhard Zumkeller, Nov 04 2009]

Dudek shows that a(n) > 0 for n > 2. - Charles R Greathouse IV, Dec 23 2020