A075058 Lexicographically earliest infinite sequence of distinct positive numbers with the property that every positive integer is a sum of distinct terms (see algorithm below).

1, 2, 3, 7, 13, 23, 47, 97, 193, 383, 769, 1531, 3067, 6133, 12269, 24533, 49069, 98129, 196247, 392503, 785017, 1570007, 3140041, 6280067, 12560147, 25120289, 50240587, 100481167, 200962327, 401924639, 803849303, 1607698583, 3215397193, 6430794373

Offset: 0

Author

Amarnath Murthy, Sep 07 2002

Keywords

• nonn

Comments

This sequence starts with a(0)=1, subsequent terms a(n) for n > 0 being obtained by selecting the greatest prime <= 1 + Sum_{i=0..n-1} a(i). This ensures that the sequence has the required property because Sum_{i=0..n-1} a(i) >= a(n) - 1, for all n >= 0 and a(0)=1, is a necessary and sufficient condition for it to hold.

Examples

			Given that the first 7 terms of the sequence are 1,2,...,23,47 then a(8)=(greatest prime) <= (1+2+...+23,47) + 1 = 97, hence a(8)=97.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..1000
• Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]

Crossrefs

Cf. A068524, A007924, A066352, A200947.

Programs

Mathematica

prevprime[n_Integer] := (j=n; While[!PrimeQ[j], j--]; j) aprime[0]=1; aprime[n_Integer] := (aprime[n] = prevprime[Sum[aprime[m], {m, 0, n - 1}] + 1]); Table[aprime[p], {p, 0, 50}]
a[0] = 1; a[n_] := a[n] = NextPrime[Sum[a[k], {k, 0, n-1}]+2, -1]; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Sep 30 2013 *)

PARI

print1(s=1);for(n=1,20,k=precprime(s+1);print1(", "k);s+=k) \\ Charles R Greathouse IV, Apr 05 2013

Formula

a(n) = (greatest prime) <= 1 + Sum_{i=0..n-1} a(i).

a(n) ~ k*2^n, with k roughly 0.748643. - Charles R Greathouse IV, Apr 05 2013

Extensions

Entry revised by Frank M Jackson, Dec 03 2011

Edited by N. J. A. Sloane, May 20 2023