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,2

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.

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]

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

Example

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.

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

Prog

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

Crossrefs

Cf. A068524, A007924, A066352, A200947.

Sequence in context: A091440 A175211 A330028 * A213968 A213967 A128695

Adjacent sequences: A075055 A075056 A075057 * A075059 A075060 A075061

Keyword

nonn

Author

Amarnath Murthy, Sep 07 2002

Extensions

Entry revised by Frank M Jackson, Dec 03 2011

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

Status

approved