1,2

Is there a closed or better recursive formula for a(n)? Can someone prove that a(n) > 2*a(n-1) for every n? Is there a polynomial-time algorithm for a(n)? The given Maple program is exponential in time and use of storage and hence not suitable to compute higher elements of the sequence.

Proof that a(n) > 2*a(n-1) [AK, Feb 15 2002]: Each of the integers in range 1 .. a(n-1) can be represented as a sum of some subset of the terms {a(1),a(2),...,a(n-1)} plus at most one of the terms a(1)-a(n-1) added second time (e.g. 16=8+8, 18=18, 22=18+3+1, 25=18+3+1+3, 28=18+8+1+1), thus each of the integers in range a(n-1)+1 .. 2*a(n-1) can be represented as a similar "dirty" subset sum with also a(n-1) included, that is, there are no pure 1-subsets, i.e. no terms of A066425 in the latter range. Note that neither is 2*a(n-1) possible candidate because it is a(n-1)+a(n-1).

A. Karttunen, Scheme functions for computing A066425 and related sequences.

a(1)=1, a(n) the smallest integer > a(n-1) so that a(n)-a(k_1)-a(k_2)- .. -a(k_m) is not in the sequence for any non-empty subset {k_1, .., k_m} of {1, .., n-1}

a(1)=1, a(n)=2*a(n-1) + A068058(n-1) [AK]

With a(1)=1 and a(2)=3 a(3) cannot be 4, 5, 6 or 7, since 4-a(1), 5-a(1)-a(2), 6-a(2) and 7-a(1)-a(2) are in the sequence, but 8-a(1), 8-a(2) and 8-a(1)-a(2) are not, hence a(3)=8

a(1) := 1: setofelms := {1}: setofsums := {1}: for n from 2 to 15 do: for i from a(n-1)+1 do: check := 0: for elsum in setofsums while check = 0 do: if member(i-elsum, setofelms) then check := 1: fi: od: if check = 1 then next: fi: a(n) := i: print (n, a(n)): setofsumsn := {}: for elsum in setofsums do: setofsumsn := setofsumsn union {elsum+a(n)}: od: setofsums := (setofsumsn union setofsums) union {a(n)}: setofelms := setofelms union {a(n)}: break: od: od:

(C++) #include <iostream> #include <vector> using namespace std ; int main(int argc, char *argv[]) { vector<unsigned long long> a ; a.push_back(1LL) ; for(; ; ) { int n = a.size() ; bool found= false ; for(unsigned long long nexta = 2LL*a[n-1]+1LL; !found ; nexta++) { bool foundComb=false ; for(unsigned long long bmask = 1LL<<n ; bmask > 0 && !foundComb; ) { bmask -- ; unsigned long long tstsum=0LL ; for(int maskpo=0; maskpo < n ; maskpo++) if ( (1LL << maskpo) & bmask) tstsum += a[maskpo] ; unsigned long long tstsumM=0LL ; if( tstsum == nexta) { foundComb=true ; break ; } for(int maskpo=0; maskpo < n && ! foundComb ; maskpo++) if ( (1 << maskpo) & bmask) { unsigned long long tstsum2 = tstsum+a[maskpo] ; tstsumM=max(tstsumM, tstsum2) ; if ( tstsum2 == nexta ) { foundComb=true ; break ; } } if( tstsumM < nexta) break ; } if ( foundComb==false ) { a.push_back(nexta) ; cout << nexta << endl ; found=true ; break ; } } } } - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), May 24 2006

Cf. A068054, A068055, A068056, A068057, A068058, A068059, A068221-A068224.

Adjacent sequences: A066422 A066423 A066424 this_sequence A066426 A066427 A066428

Sequence in context: A036384 A080692 A117080 this_sequence A026679 A026756 A026384

nonn,nice

Ulrich Schimke (ulrschimke(AT)aol.com), Dec 26 2001

Terms 16-21 computed (with the Scheme-code linked above) by Antti Karttunen (firstname.surname ), Feb 26 2002

More terms from John W. Layman (layman(AT)math.vt.edu), Mar 19 2002

More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), May 24 2006