|
%I #49 Dec 15 2021 01:52:36
%S 1,3,8,18,41,84,181,364,751,1512,3037,6107,12216,24547,49117,98236,
%T 196544,393178,786407,1573201,3146426,6292969,12586763,25173709,
%U 50347996,100696725,201393664,402788102,805576428,1611153169,3222306562
%N a(1) = 1; thereafter a(n) is the smallest number > a(n-1) such that a(n) minus any sum of distinct earlier terms is not already in the sequence.
%C 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.
%C 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).
%C 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
%C 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
%H Charlie Neder, <a href="/A066425/b066425.txt">Table of n, a(n) for n = 1..70</a>
%H Ethan D. Bolker, Samuel A. Feuer and Catalin Zara, <a href="https://doi.org/10.1080/0025570X.2021.1979369">Balance Weighing, Variations on a Theme</a>, Mathematics Magazine, October 22, 2021; <a href="https://www.cs.umb.edu/~eb/weighing.pdf">author's copy</a>.
%H Antti Karttunen, <a href="/A066425/a066425s.txt">Scheme functions for computing A066425 and related sequences.</a>
%F 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}
%F a(1)=1, a(n) = 2*a(n-1) + A068058(n-1). [AK]
%e 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.
%p 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:
%t (* 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 *)
%o (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 */
%o (Python) def solve(n,arr,dupl):
%o ..s = [i for i in seq if i <= n and i > n//(3-dupl)]
%o ..if n in s: return 1
%o ..for i in s:
%o ....if i in arr and dupl: continue
%o ....ar = arr.copy() + [i]
%o ....if solve(n-i,ar,i in arr or dupl): return 1
%o ..return 0
%o seq = [0]
%o for n in range(70):
%o ..k = 2*seq[-1]+1
%o ..while solve(k,[],0): k += 1
%o ..print(n+1,k)
%o ..seq.append(k)
%o # _Charlie Neder_, Jan 09 2019
%Y Cf. A068054, A068055, A068056, A068057, A068058, A068059, A068221-A068224.
%K nonn,nice
%O 1,2
%A Ulrich Schimke (ulrschimke(AT)aol.com), Dec 26 2001
%E Terms a(16)-a(21) computed (with the Scheme-code linked above) by _Antti Karttunen_, Feb 26 2002
%E More terms from _John W. Layman_, Mar 19 2002
%E More terms from _R. J. Mathar_, May 24 2006
%E Definition edited by _N. J. A. Sloane_, Dec 15 2021
|
