

A066425


Smallest increasing sequence (with a(1) = 1) such that a(n) minus any sum of distinct earlier terms is not already in the sequence.


9



1, 3, 8, 18, 41, 84, 181, 364, 751, 1512, 3037, 6107, 12216, 24547, 49117, 98236, 196544, 393178, 786407, 1573201, 3146426, 6292969, 12586763, 25173709, 50347996, 100696725, 201393664, 402788102, 805576428, 1611153169, 3222306562
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Is there a closed or better recursive formula for a(n)? Can someone prove that a(n) > 2*a(n1) for every n? Is there a polynomialtime 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(n1) [AK, Feb 15 2002]: Each of the integers in range 1 .. a(n1) can be represented as a sum of some subset of the terms {a(1),a(2),...,a(n1)} plus at most one of the terms a(1)a(n1) added a 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 the range a(n1)+1 .. 2*a(n1) can be represented as a similar "dirty" subset sum with also a(n1) included, that is, there are no pure 1subsets, i.e., no terms of A066425 in the latter range. Note that neither is 2*a(n1) a possible candidate because it is a(n1) + a(n1).
The set of possible decompositions of a number k forms a tree with edges corresponding to terms a(m). Since each term is greater than the sum of all lesser terms, the sum of any decomposition is less than three times the highest term (the highest term may appear twice), so the branches at any node only contain terms in the interval (k/3,k], of which there are at most two. If a branch corresponds to a decomposition with a repeated term, the sum of the remaining terms is at most twice the next term and the branches at this node correspond to terms in the interval (k/2,k] of which there are at most one. This tree can be traversed in O((log k)^2) = O(n^2) time, but a full time complexity analysis of this sequence would require bounds on A068058(n), the number of trees checked per term.  Charlie Neder, Jan 09 2019


LINKS

Charlie Neder, Table of n, a(n) for n = 1..70
A. Karttunen, Scheme functions for computing A066425 and related sequences.


FORMULA

a(1)=1, a(n) the smallest integer > a(n1) so that a(n)  a(k_1)  a(k_2) ...  a(k_m) is not in the sequence for any nonempty subset {k_1, ..., k_m} of {1, .., n1}
a(1)=1, a(n) = 2*a(n1) + A068058(n1). [AK]


EXAMPLE

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


MAPLE

a(1) := 1: setofelms := {1}: setofsums := {1}: for n from 2 to 15 do: for i from a(n1)+1 do: check := 0: for elsum in setofsums while check = 0 do: if member(ielsum, 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:


MATHEMATICA

(* This program is not convenient to compute a large number of terms *) a[1] = 1; a[n_] := a[n] = Module[{aa, sums, an, diffs}, sums = Total /@ Subsets[aa = Array[a, n1], {2, Infinity}]; For[an = 2*a[n1] + 1, True, an++, diffs = an  sums; If[Intersection[aa, diffs] == {}, Return[an]]]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 25}] (* JeanFrançois Alcover, Sep 27 2013 *)


PROG

(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[n1]+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, May 24 2006 */
(Python) def solve(n, arr, dupl):
..s = [i for i in seq if i <= n and i > n//(3dupl)]
..if n in s: return 1
..for i in s:
....if i in arr and dupl: continue
....ar = arr.copy() + [i]
....if solve(ni, ar, i in arr or dupl): return 1
..return 0
seq = [0]
for n in range(70):
..k = 2*seq[1]+1
..while solve(k, [], 0): k += 1
..print(n+1, k)
..seq.append(k)
# Charlie Neder, Jan 09 2019


CROSSREFS

Cf. A068054, A068055, A068056, A068057, A068058, A068059, A068221A068224.
Sequence in context: A080692 A117080 A240135 * A026679 A191524 A026756
Adjacent sequences: A066422 A066423 A066424 * A066426 A066427 A066428


KEYWORD

nonn,nice


AUTHOR

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


EXTENSIONS

Terms a(16)a(21) computed (with the Schemecode linked above) by Antti Karttunen, Feb 26 2002
More terms from John W. Layman, Mar 19 2002
More terms from R. J. Mathar, May 24 2006


STATUS

approved



