cp's OEIS Frontend

A051034 Minimal number of primes needed to sum to n.

%I A051034 #44 Feb 16 2025 08:32:41
%S A051034 1,1,2,1,2,1,2,2,2,1,2,1,2,2,2,1,2,1,2,2,2,1,2,2,2,3,2,1,2,1,2,2,2,3,
%T A051034 2,1,2,2,2,1,2,1,2,2,2,1,2,2,2,3,2,1,2,2,2,3,2,1,2,1,2,2,2,3,2,1,2,2,
%U A051034 2,1,2,1,2,2,2,3,2,1,2,2,2,1,2,2,2,3,2,1,2,2,2,3,2,3,2,1,2,2,2,1,2,1,2,2,2,1,2,1,2,2,2
%N A051034 Minimal number of primes needed to sum to n.
%H A051034 T. D. Noe, <a href="/A051034/b051034.txt">Table of n, a(n) for n = 2..10000</a>
%H A051034 Olivier Ramaré, <a href="http://www.numdam.org/item/ASNSP_1995_4_22_4_645_0.pdf">On Šnirel'man's constant</a>, Annali della Scuola Normale Superiore di Pisa, Classe di Scienze 4e série, 22:4 (1995), pp. 645-706.
%H A051034 Yannick Saouter, <a href="https://citeseerx.ist.psu.edu/pdf/5622d8da1147f7f0cccf215b1b05bef3973c3ed4">Vinogradov's theorem is true up to 10^20</a>
%H A051034 Terence Tao, <a href="https://arxiv.org/abs/1201.6656">Every odd number greater than 1 is the sum of at most five primes</a>, arXiv:1201.6656 [math.NT], 2012 preprint, to appear in Mathematics of Computation.
%H A051034 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimePartition.html">Prime Partition</a>
%H A051034 <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>
%F A051034 a(n) = 1 iff n is prime. a(2n) = 2 (for n > 1) if Goldbach's conjecture is true. a(2n+1) = 2 (for n >= 1) if 2n+1 is not prime, but 2n-1 is. a(2n+1) >= 3 (for n >= 1) if both 2n+1 and 2n-1 are not primes (for sufficiently large n, a(2n+1) = 3 by Vinogradov's theorem, 1937). - _Franz Vrabec_, Nov 30 2004
%F A051034 a(n) <= 3 for all n, assuming the Goldbach conjecture. - _N. J. A. Sloane_, Jan 20 2007
%F A051034 a(2n+1) <= 5, see Tao 2012. - _Charles R Greathouse IV_, Jul 09 2012
%F A051034 Assuming Goldbach's conjecture, a(n) <= 3. In particular, a(p)=1; a(2*n)=2 for n>1; a(p+2)=2 provided p+2 is not prime; otherwise a(n)=3. - _Sean A. Irvine_, Jul 29 2019
%F A051034 a(2n+1) <= 3 by Helfgott's proof of Goldbach's ternary conjecture, and hence a(n) <= 4 in general. - _Charles R Greathouse IV_, Oct 24 2022
%e A051034 a(2) = 1 because 2 is already prime.
%e A051034 a(4) = 2 because 4 = 2+2 is a partition of 4 into 2 prime parts and there is no such partition with fewer terms.
%e A051034 a(27) = 3 because 27 = 3+5+19 is a partition of 27 into 3 prime parts and there is no such partition with fewer terms.
%t A051034 (* Assuming Goldbach's conjecture *) a[p_?PrimeQ] = 1; a[n_] := If[ Reduce[ n == x + y, {x, y}, Primes] === False, 3, 2]; Table[a[n], {n, 2, 112}] (* _Jean-François Alcover_, Apr 03 2012 *)
%o A051034 (PARI) issum(n,k)=if(k==1,isprime(n),k--;forprime(p=2,n,if(issum(n-p,k),return(1)));0)
%o A051034 a(n)=my(k);while(!issum(n,k++),);k \\ _Charles R Greathouse IV_, Jun 01 2011
%Y A051034 Cf. A025583, A004526, A007944, A007962, A000607, A051036, A010051, A061358, A068307, A103765.
%Y A051034 Different from A072491.
%K A051034 nonn,nice
%O A051034 2,3
%A A051034 _Eric W. Weisstein_
%E A051034 More terms from _Naohiro Nomoto_, Mar 16 2001