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,5

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

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

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.

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

Example

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

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

Prog

(Haskell)
a098983 n = sum $ map (a008966 . (n -)) $ takeWhile (< n) a000040_list
-- Reinhard Zumkeller, Sep 14 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

Crossrefs

Sequence in context: A153437 A023153 A023159 * A097576 A029250 A341584

Adjacent sequences: A098980 A098981 A098982 * A098984 A098985 A098986

Keyword

nonn,nice

Author

N. J. A. Sloane, Oct 24 2004

Status

approved