login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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 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(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) a possible candidate because it is a(n-1) + a(n-1).

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(n-1) 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, .., n-1}

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

EXAMPLE

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.

MAPLE

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:

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, n-1], {2, Infinity}]; For[an = 2*a[n-1] + 1, True, an++, diffs = an - sums; If[Intersection[aa, diffs] == {}, Return[an]]]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 25}] (* Jean-Fran├ž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[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, May 24 2006 */

(Python) def solve(n, arr, dupl):

..s = [i for i in seq if i <= n and i > n//(3-dupl)]

..if n in s: return 1

..for i in s:

....if i in arr and dupl: continue

....ar = arr.copy() + [i]

....if solve(n-i, 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, A068221-A068224.

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 Scheme-code 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 02:54 EDT 2019. Contains 328244 sequences. (Running on oeis4.)