|
%I #13 Jul 14 2019 18:04:52
%S 0,1,1,2,2,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,
%T 8,8,8,8,8,8,8,9,8,9,9,9,9,9,9,9,9,10,9,10,10,10,10,10,10,10,10,11,10,
%U 11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,13,12
%N Maximal number of residue classes mod n such that no subset adds to 0.
%C From _Jon E. Schoenfield_, Jun 13 2010: (Start)
%C Given a value of n, one way to obtain a set of residue classes having no zero subset sum is simply to select the first k positive integers, where k is the largest integer such that 1+2+3+...+k < n; for any n > 0, this yields a set of k residue classes where k = round(sqrt(2*n)) - 1, which serves as a first lower bound for a(n).
%C For n > 5, another simple method is to select the residue classes 1, n-2, and 3..k, where k is the largest integer such that (1+2+3+...+k) - 2 < n; this yields a set of k residue classes where k = round(sqrt(2*n+4)) - 1. This second lower bound for a(n) is an improvement over the first bound at n = 6, 9, 10, 14, 15, 20, 21, ... (i.e., values of n that are triangular numbers or one less than triangular numbers; these are the terms of A117142 that exceed 5).
%C For even values of n, a third method is to select residue classes m = n/2, 1, m+1, 2, m+2, 3, m+3, etc., until k = floor(sqrt(2n-3)) residue classes have been selected. This third lower bound for a(n) is an improvement over the other two for n = 26, 34, 42, 52, 62, 64, 74, 76, 86, 88, 100, 102, 114, 116, 118, ... (i.e., even numbers whose difference d from the next higher triangular number T(k) = k*(k+1)/2 satisfies 1 < d < k/2-1).
%C Let S = {25, 75, 375, 525, 1125, 1375, ...} be the set of numbers that are 25 times an odd triangular number, i.e., numbers of the form 25*T(j) = 25*j*(j+1)/2 where (j+3) mod 4 < 2. For values of n in S, a fourth method is to let m = n/5 and select residue classes 1..j, m+1..m+j, 2*m+1..2*m+j, 3*m+1..3*m+j, 4*m+1..4*m+j, m, and 2*m; this yields a set of 5*j+2 residue classes, which gives sqrt(2*n + 25/4) - 1/2 as an improved lower bound for a(n) for n in S: a(25) >= 7, a(75) >= 12, a(375) >= 27, a(525) >= 32, a(1125) >= 47, a(1375) >= 52, etc.
%C For each of the first 87 terms in the sequence, an exhaustive search determined that a(n) either equals the first lower bound (round(sqrt(2*n))-1) or exceeds it by only 1, and that at least one of the four methods above yields a maximal solution.
%C The sequence is not nondecreasing; a(n) < a(n-1) at n = 43, 53, 63, and 87 (and, if it continues to be the case that at least one of the four methods above yields a maximal solution, the next decreases occur at n = 89, 101, 103, 115, 117, 131, 133, 147, 149, 151, ...).
%C Does there exist any value of n for which none of the four methods above yields a maximal solution? (End)
%D R. K. Guy, Unsolved Problems in Number Theory, Sect. C15.
%e For n=20, {1,-2,3,4,5,6} shows a(20)>= 6 (in fact a(20)=6). For n=30, {1,2,3,4,5,6,7} shows that a(30)>=7 (in fact a(30)=7).
%o (PARI) a(n)=my(v=vector(n,i,i),t,w,r);for(i=1,2^(n-1)-1, if(hammingweight(i)<=r,next); t=vecextract(v,i); w=vector(n); w[1]=1; for(j=1,#t,w+=concat(w[t[j]+1..n],w[1..t[j]]); if(w[1]>1, next(2))); r=hammingweight(i)); r \\ _Charles R Greathouse IV_, Oct 16 2013
%K nonn,nice
%O 1,4
%A _N. J. A. Sloane_
%E The reference gives a(5)=3, but this is incorrect, a(5)=2.
%E More terms from _John W. Layman_, Oct 02 2002
%E Terms a(36)-a(87) from _Jon E. Schoenfield_, Jun 13 2010
|
