A014090 -id:A014090 - cp's OEIS frontend

A002471 Number of partitions of n into a prime and a square.

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, 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, 2, 1, 3, 3, 2, 1, 3, 1, 4, 2, 2, 3, 1

Offset: 1

N. J. A. Sloane

a(A014090(n))=0; a(A014089(n))>0; a(A143989(n))=1. - Reinhard Zumkeller, Sep 07 2008

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A064272, A010051, A000290.

a002471 n = sum $ map (a010051 . (n -)) $ takeWhile (< n) a000290_list
-- Reinhard Zumkeller, Jul 23 2013, Sep 30 2011

n->nops(select(isprime,[ seq(n-i^2,i=0..trunc(sqrt(n))) ])):
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):

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

a(n)=if(n>1, sum(k=0,sqrtint(n-2), isprime(n-k^2)), 0) \\ Charles R Greathouse IV, Feb 08 2017

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

Sequence corrected by Paul Zimmermann, Mar 15 1996

A064233 Numbers that are not the sum of a prime number and a nonzero square.

Original entry on oeis.org

1, 2, 5, 10, 13, 25, 31, 34, 37, 58, 61, 64, 85, 91, 121, 127, 130, 169, 196, 214, 226, 289, 324, 370, 379, 400, 439, 526, 529, 571, 625, 676, 706, 730, 771, 784, 829, 841, 991, 1024, 1089, 1225, 1255, 1351, 1414, 1444, 1521, 1549, 1681, 1849, 1906, 1936, 2116

Offset: 1

Axel Harvey, Sep 22 2001

The sequence is infinite, cf. A014090. Subsequence of squares = A053726^2. Subsequence of nonsquares is disjoint union of A020495 and A065377 and so is probably finite. - Vladeta Jovovic, Apr 02 2005

			5 = 1+4 or 2+3; a prime and a square do not appear together in either sum.

T. D. Noe, Table of n, a(n) for n = 1..1000
I. V. Poljakov, On the exceptional set for the sum of a prime and a perfect square, 1982 Math. USSR Izv. 19 611.

Complement of A058654.

Cf. A014090, A053726, A020495, A065377.

Complement[ Table[ n, {n, 1, 10000} ], Union[ Flatten[ Table[ Prime[ i ] + j^2, {i, 1, 1230}, {j, 1, 100} ] ] ] ]
nspQ[n_]:=Length[Select[IntegerPartitions[n,{2}],(PrimeQ[#[[1]]] && IntegerQ[ Sqrt[ #[[2]]]])||(PrimeQ[#[[2]]]&&IntegerQ[Sqrt[#[[1]]]])&]] == 0; Select[ Range[ 2200],nspQ] (* Harvey P. Dale, Jun 18 2021 *)

list(lim)=my(v=vectorsmall(lim\1,i,1),u=List(),b);forprime(p=2,#v, b=0; while((t=p+b++^2)<=#v,v[t]=0));for(i=1,#v,if(v[i],listput(u,i))); Vec(u) \\ Charles R Greathouse IV, May 29 2012

More terms from Vladeta Jovovic, Robert G. Wilson v and Felice Russo, Sep 23 2001

A100570 Numbers that are not the sum of a square and a semiprime.

Original entry on oeis.org

1, 2, 3, 12, 17, 28, 32, 72, 108, 117, 297, 657

Offset: 1

Jonathan Vos Post, Nov 29 2004

No others up to 300000. Computed in collaboration with Ray Chandler. It appears that this sequence is finite, that is, that almost every positive integer is the sum of a semiprime and a square number. There are probably no further exceptions after a(12)=657.
The statement about the finiteness of this sequence (namely, a(n)<=657) is much stronger than the Goldbach binary conjecture. Indeed, a much weaker conjecture, that this sequence contains no perfect squares >1, already implies the Goldbach conjecture. Cf. comment in A241922. - Vladimir Shevelev, May 01 2014
From Daniel Mikhail, Nov 23 2020: (Start)
There are no new terms in this sequence between 658 and 2^28.
Notably, A014090 (numbers that are not the sum of a square and one prime) is a known infinite sequence. (End)

			From _Daniel Mikhail_, Nov 23 2020: (Start)
An integer m is in this set if, for any primes, p and q, there does not exist a natural k, such that m-k^2 = p*q.
Consider m=12 and all k such that k^2 < 12: k is either 0,1,4, or 9.
  12 - 0 = 12 = 2*2*2*3 => not semiprime;
  12 - 1 = 11 => not semiprime;
  12 - 4 = 8 = 2*2*2 => not semiprime;
  12 - 9 = 3 => not semiprime.
Therefore, 12 is a term. (End)

Daniel Mikhail, Brief glance of the search for integer solutions to a(n)-k^2 = semiprime

Cf. A000290, A001358, A046903, A241922, A014090.

lim = 657; Complement[Range[lim],Select[Flatten[Outer[Plus,Select[Range[lim], PrimeOmega[#] == 2 &],Table[i^2, {i, 0, Sqrt[lim]}]]], # <= lim &]] (* Robert Price, Apr 10 2019 *)

An integer is not an element for any integers i, j of the pairwise sum of {A001358(i)} and {A000290(j)}.

A014089 Sum of a square and a prime.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 60, 61, 62

Offset: 1

N. J. A. Sloane

A002471(a(n))>0; complement of A014090; A143989 is a subsequence. [From Reinhard Zumkeller, Sep 07 2008]

Cf. A058654.

isok(n) = for (i = 0, sqrtint(n), if (isprime(n - i^2), return (1))); 0 \\ Michel Marcus, Sep 04 2013

A365166 Numbers that are not the sum of a prime number and a fourth power of a nonnegative integer.

Original entry on oeis.org

1, 9, 10, 15, 16, 22, 25, 26, 28, 34, 36, 40, 46, 49, 50, 51, 52, 55, 56, 58, 64, 65, 66, 70, 76, 78, 81, 82, 85, 91, 93, 96, 106, 111, 115, 116, 120, 121, 126, 130, 133, 135, 136, 141, 144, 145, 146, 156, 159, 161, 162, 166, 169, 171, 172, 175, 176, 177, 185, 186, 187, 196

Offset: 1

Ilya Gutkovskiy, Aug 24 2023

nonn

Cf. A014090, A045911, A356295, A365126, A365127, A365169.

nmax = 197; Position[CoefficientList[Series[Sum[x^Prime[i], {i, 1, nmax}] Sum[x^j^4, {j, 0, nmax^(1/4)}], {x, 0, nmax}], x] // Rest, 0] // Flatten

A111908 Numbers that are not the sum of a prime and a nonzero triangular number.

Original entry on oeis.org

1, 2, 7, 36, 61, 105, 171, 210, 211, 216, 325, 351, 406, 528, 561, 630, 741, 780, 990, 1081, 1176, 1275, 1596, 1711, 1830, 1953, 2016, 2145, 2346, 2628, 2775, 3003, 3081, 3240, 3321, 3655, 3741, 3916, 4278, 4371, 4465, 4560, 4851, 5253, 5460, 5565, 5886

Offset: 1

Stefan Steinerberger, Nov 25 2005

nonn

Can anybody prove or disprove a(n) = O(n^c) for some constant c?

Jonathan Vos Post has observed that every term in A076768 also occurs in this sequence.

			7 = 1+6 = 2+5 = 3+4; 7 is in the sequence because there is no sum where the first element is a prime and the second one a triangular number.

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A064233, A000217, A076768, A020756, A072386, A014089, A014090, A000404, A001481, A002654, A100570, A101181.

lim=6000;plim=PrimePi[lim];tlim=Ceiling[Sqrt[2lim]];Complement[Range[lim],Union[Flatten[Table[Prime[i]+PolygonalNumber[j],{i,plim},{j,tlim}]]]] (* James C. McMahon, Jun 04 2024 *)

a(47) and offset corrected by Donovan Johnson, Feb 09 2013

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 0, 1, 1, 4, 2, 2, 2, 1, 3, 2, 2, 3, 1, 2, 4, 4, 2, 2, 1, 2, 2, 4, 2, 3, 1, 3, 2, 4, 2, 2, 2, 3, 4, 2, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 4, 2, 2, 2, 2, 1, 5, 1, 4, 2, 3, 3, 2, 1, 5, 2, 1, 4, 4, 3, 2, 1, 2, 4, 3, 2, 3, 2, 2, 4, 2, 2, 2, 2, 3, 2, 6, 2, 4, 2, 2, 4, 5, 2, 3, 1, 3, 3, 5, 2, 3, 1, 2, 4, 4, 3, 3, 2, 1, 6

Offset: 1

Eric Chen, May 17 2015

In this sequence, "perfect power" does not include 0 or 1, "prime" does not include 1. Both "perfect power" and "prime" must be positive.
In the past, I conjectured that a(n) > 0 for all n>24, but this is not true. My PARI program found that a(1549) = 0.
I also asked which a(n) are 1. For example, 331 is a de Polignac number (A006285), so it cannot be written as 2^n+p with p prime, and 331-6^n must divisible by 5, 331-10^n must divisible by 3, ..., 331-18^2 = 331-324 = 7 is prime (and it is the only prime of the form 331-m^n, with m, n natural numbers, m>1, n>1), so a(331) = 1. Similarly, a(3319) = 1. Conjecture: a(n) > 1 for all n > 3319.
This conjecture is not true: a(1771561) = 0. (See A119748)
Another conjecture: For every number m>=0, there is a number k such that a(n)>=m for all n>=k.
Another conjecture: Except for k=2, first occurrence of k must be earlier then first occurrence of k+1.
For n such that a(n) = 0, see A119748.
For n such that a(n) = 1, see the following a-file of this sequence.

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 3000 terms from Chen)
Eric Chen, The unique way to write n as a sum of a perfect power (>1) and a prime for those n such a(n)=1

Cf. A196228, A119748, A109925, A118954, A064272, A064233, A002471, A014090.

nn = 128; pwrs = Flatten[Table[Range[2, Floor[nn^(1/ex)]]^ex, {ex, 2, Floor[Log[2, nn]]}]]; pp = Prime[Range[PrimePi[nn]]]; t = Table[0, {nn}]; Do[ t[[i[[1]]]] = i[[2]], {i, Tally[Sort[Select[Flatten[Outer[Plus, pwrs, pp]], # <= nn &]]]}]; t

a(n) = sum(k=1, n-1, ispower(k) && isprime(n-k))

a(n)=sum(e=2,log(n)\log(2),sum(b=2,sqrtnint(n,e),isprime(n-b^e)&&!ispower(b))) \\ Charles R Greathouse IV, May 28 2015

A356295 Numbers that are not the sum of a nonnegative cube and a prime.

Original entry on oeis.org

1, 9, 16, 22, 26, 28, 33, 35, 36, 52, 57, 63, 65, 76, 78, 82, 85, 92, 96, 99, 112, 118, 119, 120, 122, 126, 129, 133, 141, 146, 155, 160, 169, 170, 183, 185, 188, 202, 209, 210, 216, 217, 225, 236, 244, 246, 248, 267, 273, 280, 286, 300, 302, 309, 326, 328, 330, 342

Offset: 1

Jianing Song, Aug 03 2022

nonn

It is conjectured that the subsequence of noncube terms, A045911, is finite (has 6195 terms). But there are infinitely many cubes in this sequence: k^3 if a term if and only if k^3 - (k-1)^3 = 3*k^2 - 3*k + 1 is a nonprime (k-1 is in A257772). For example, for k == 2, 6 (mod 7), 3*k^2 - 3*k + 1 is divisible by 7, so k^3 is a term for k == 2, 6 (mod 7) and k > 2.

			9 is a term since neither 9 - 0^3 = 9 nor 9 - 1^3 = 8 is a prime.

Indices of 0 in A302354.
Equals A045911 U {(A257772(n)+1)^3}.
Cf. A014090.

isA356295(n) = for(m=0, sqrtnint(n,3), if(isprime(n-m^3), return(0))); return(1)

A308516 Odd numbers which are not squares and cannot be written as a sum of a prime and a square.

Original entry on oeis.org

85, 91, 771, 1255, 1351, 21679

Offset: 1

Daniel Starodubtsev, Jun 03 2019

The sequence is probably finite. a(7) > 2000000 (if it exists).

a(7) > 1.5*10^11, if it exists. - Giovanni Resta, Jul 16 2019

A subsequence of A020495.

Cf. A014090, A065377.

cp's OEIS Frontend

A002471 Number of partitions of n into a prime and a square.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A064233 Numbers that are not the sum of a prime number and a nonzero square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A100570 Numbers that are not the sum of a square and a semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A014089 Sum of a square and a prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A365166 Numbers that are not the sum of a prime number and a fourth power of a nonnegative integer.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A111908 Numbers that are not the sum of a prime and a nonzero triangular number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A356295 Numbers that are not the sum of a nonnegative cube and a prime.

Views

Author

Keywords