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

%I #35 Apr 12 2022 11:33:28

%S 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,

%T 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,

%U 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

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

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

%H T. D. Noe, <a href="/A098983/b098983.txt">Table of n, a(n) for n = 0..10000</a>

%H Adrian Dudek, <a href="http://arxiv.org/abs/1410.7459">On the Sum of a Prime and a Square-free Number</a>, arXiv:1410.7459 [math.NT], 2014.

%H T. Estermann, <a href="https://doi.org/10.1112/jlms/s1-6.3.219">On the representations of a number as the sum of a prime and a quadratfrei number</a>, J. London Math. Soc., S1-6(3):219, 1931.

%H Forrest J. Francis and Ethan S. Lee, <a href="http://math.colgate.edu/~integers/w14/w14.pdf">Additive Representations of Natural Numbers</a>, #A14 INTEGERS 22 (2022).

%H A. Page, <a href="https://doi.org/10.1112/plms/s2-39.1.116">On the Number of Primes in an Arithmetic Progression</a>, Proc London Math Soc (1935) s2-39 (1): 116-141.

%H A. Walfisz, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002376350">Zur additiven Zahlentheorie II</a>, Math. Z. 40 (1936), 592-607.

%F 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+...).

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

%F Dudek shows that a(n) > 0 for n > 2. - _Charles R Greathouse IV_, Dec 23 2020

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

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

%o (Haskell)

%o a098983 n = sum $ map (a008966 . (n -)) $ takeWhile (< n) a000040_list

%o -- _Reinhard Zumkeller_, Sep 14 2011

%o (PARI) a(n)=my(s);forprime(p=2,n,s+=issquarefree(n-p));s \\ _Charles R Greathouse IV_, Jun 20 2013

%o (PARI) a(n)=my(s);forsquarefree(k=1,n-2,if(isprime(n-k[1]),s++));s \\ _Charles R Greathouse IV_, Dec 23 2020

%K nonn,nice

%O 0,5

%A _N. J. A. Sloane_, Oct 24 2004