login
Number of partitions of n into a prime and a square.
(Formerly M0073 N0025)
12

%I M0073 N0025 #35 Jan 29 2022 01:06:25

%S 0,1,2,1,1,2,2,1,1,0,3,2,1,2,1,1,2,2,2,2,2,1,3,1,0,1,3,2,2,2,1,3,2,0,

%T 2,1,1,4,2,1,3,2,2,2,2,1,4,2,1,1,2,2,3,3,1,3,2,0,3,2,1,4,2,0,2,3,3,4,

%U 2,1,3,3,2,1,3,1,4,2,2,3,1

%N Number of partitions of n into a prime and a square.

%C a(A014090(n))=0; a(A014089(n))>0; a(A143989(n))=1. - _Reinhard Zumkeller_, Sep 07 2008

%D Selmer, Ernst S.; Eine numerische Untersuchung ueber die Darstellung der natuerlichen Zahlen als Summe einer Primzahl und einer Quadratzahl. Arch. Math. Naturvid. 47, (1943). no. 2, 21-39.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A002471/b002471.txt">Table of n, a(n) for n = 1..10000</a>

%F G.f.: (Sum_{i>=0} x^(i^2))*(Sum_{j>=1} x^prime(j)). - _Ilya Gutkovskiy_, Feb 07 2017

%p n->nops(select(isprime,[ seq(n-i^2,i=0..trunc(sqrt(n))) ])):

%p with(combstruct): specM0073 := {N=Prod(P, S),P=Set(Z,card>=1), S=Set(Z,card>=0)}: `combstruct/compile`(specM0073,unlabeled): `combstruct/Count`[ specM0073,unlabeled ][ P ] := proc(p) option remember; if isprime(p) then 1 else 0 fi end: `combstruct/Count`[ specM0073,unlabeled ][ S ] := proc(p) option remember; if type(sqrt(p), integer) then 1 else 0 fi end: M0073 := n->count([ N,specM0073,unlabeled ],size=n):

%t a[n_] := Count[p /. {ToRules[ Reduce[ p > 1 && q >= 0 && n == p + q^2, {p, q}, Integers]]}, _?PrimeQ]; Table[ a[n], {n, 1, 81}] (* from Jean-François Alcover, Sep 30 2011 *)

%o (Haskell)

%o a002471 n = sum $ map (a010051 . (n -)) $ takeWhile (< n) a000290_list

%o -- _Reinhard Zumkeller_, Jul 23 2013, Sep 30 2011

%o (PARI) a(n)=if(n>1, sum(k=0,sqrtint(n-2), isprime(n-k^2)), 0) \\ _Charles R Greathouse IV_, Feb 08 2017

%Y Cf. A064272, A010051, A000290.

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_

%E Sequence corrected by _Paul Zimmermann_, Mar 15 1996