|
| |
|
|
A034463
|
|
Maximal number of residue classes mod n such that no subset adds to 0.
|
|
0
|
|
|
|
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, 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, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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).
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).
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).
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.
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.
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, ...).
Does there exist any value of n for which none of the four methods above yields a maximal solution? (End)
|
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems in Number Theory, Sect. C15.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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).
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
The reference gives a(5)=3, but this is incorrect, a(5)=2.
|
|
|
STATUS
|
approved
|
| |
|
|
