%I #30 Dec 28 2023 11:31:48
%S 2,3,5,7,17,19,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
%T 103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,
%U 193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283
%N a(1) = 2, a(2) = 3; for n > 2, a(n) = least prime equal to the sum of two or more previous terms.
%C A heuristic argument suggests that all primes except 11, 13 and 23 are included in this sequence (tested on first million primes). - Ryan Murphy (murphy(AT)minegoboom.com), Jan 24 2006
%C Except for 17 which uses all 4 of the previous terms, all the other terms so far use only two or three of the previous terms. This is a more restrictive application of the Goldbach conjecture. - _Robert G. Wilson v_, Apr 08 2007, May 05 2007
%C Up to 10^4, all a(n) requiring 4 terms are of the form a(n)=2+7+m+p with m=5 or m=19, i.e., of the form 14+p or 28+p; no a(n)<10^6 requires more than 4 terms. - _M. F. Hasler_, May 04 2007
%C Ryan Murphy's heuristic is correct: a(n) = prime(n+3) for n > 6. It suffices to check that all n in 36..72 are the sum of one or more members of this sequence. Thus, all n > 72 are the sum of two or more distinct members of this sequence, since by Bertrand's postulate there is a prime n/2 < p < n. - _Charles R Greathouse IV_, Aug 22 2011
%e 5 = 2+3 follows 3, 7 = 5+2 follows 5, 17 = 2+3+5+7 follows 7.
%t (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) f[lst_List] := Block[{k = Length@ lst, p = Infinity, q}, lmt = If[k > 5, Sum[Binomial[k, i], {i, 2, 4}], 2^k + 1]; k++; While[k < lmt, q = Plus @@ NthSubset[k, lst]; If[ ! MemberQ[lst, q] && PrimeQ@q && q < p, p = q]; k++ ]; Append[lst, p]]; Nest[f, {2, 3}, 58] (* _Robert G. Wilson v_, Apr 08 2007 *)
%o (PARI) prevprime(p)={ if( nextprime(p-1)<p || p<3, return((p-1)*(p>2))); p=bitor(p-3,1); while( nextprime(p) > p, p-=2 ); p } \ decomp(n,p)={local(d);if(!p,if(n==2 || n==3,return([n]),p=n),p=min(n,p)); while( p=prevprime(p), if( bittest(disallowed,p), next); if( (n<2*p && isprime(n-p) && !bittest(disallowed,n-p) && d=[n-p]) || d=decomp( n-p,p ), return(concat(d,p)) ))} \ disallowed=0;forprime(p=1,10^4,if(decomp(p),print1(p", "),disallowed+=1<<p)) \\ _M. F. Hasler_, May 04 2007
%o (PARI) a(n)=if(n>6,prime(n+3),[2, 3, 5, 7, 17, 19][n]) \\ _Charles R Greathouse IV_, Aug 22 2011
%o (Python)
%o from sympy import isprime; P = [2, 3]; B = {2, 3, 5}
%o while P[-1] < 300:
%o S = set()
%o for i in B:
%o if isprime(i) and i > P[-1]: P.append(i); break
%o for j in B: S.add(j+P[-1])
%o B = B|S
%o print(*P, sep = ', ') # _Ya-Ping Lu_, Dec 27 2023
%K easy,nonn
%O 1,1
%A _Amarnath Murthy_, Jan 03 2006
%E More terms from Ryan Murphy (murphy(AT)minegoboom.com), Jan 24 2006
%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, May 14 2007
|