%I #43 Aug 06 2024 08:56:49
%S 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 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 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 Minimal number of primes needed to sum to n.
%H T. D. Noe, <a href="/A051034/b051034.txt">Table of n, a(n) for n = 2..10000</a>
%H 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 Yannick Saouter, <a href="https://citeseerx.ist.psu.edu/pdf/5622d8da1147f7f0cccf215b1b05bef3973c3ed4">Vinogradov's theorem is true up to 10^20</a>
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePartition.html">Prime Partition</a>
%H <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>
%F 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 a(n) <= 3 for all n, assuming the Goldbach conjecture. - _N. J. A. Sloane_, Jan 20 2007
%F a(2n+1) <= 5, see Tao 2012. - _Charles R Greathouse IV_, Jul 09 2012
%F 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 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 a(2) = 1 because 2 is already prime.
%e 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 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 (* 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 (PARI) issum(n,k)=if(k==1,isprime(n),k--;forprime(p=2,n,if(issum(n-p,k),return(1)));0)
%o a(n)=my(k);while(!issum(n,k++),);k \\ _Charles R Greathouse IV_, Jun 01 2011
%Y Cf. A025583, A004526, A007944, A007962, A000607, A051036, A010051, A061358, A068307, A103765.
%Y Different from A072491.
%K nonn,nice
%O 2,3
%A _Eric W. Weisstein_
%E More terms from _Naohiro Nomoto_, Mar 16 2001