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
The optimal sequence of weights to balance an unknown integral weight when you may place at most one weight on the pan along with the unknown, or, equivalently, use two of any single weight on the opposite pan. - Ethan D. Bolker, Oct 28 2021
LINKS
Charlie Neder, Table of n, a(n) for n = 1..70
Ethan D. Bolker, Samuel A. Feuer and Catalin Zara, Balance Weighing, Variations on a Theme, Mathematics Magazine, October 22, 2021; author's copy.
Antti 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
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
Definition edited by N. J. A. Sloane, Dec 15 2021
STATUS
approved