|
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Contribution from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Jun 13 2010: (Start)
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 sum(1..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 sum(1..k)-2<n; this yields a set of k residue classes where k=Round(Sqrt(2*(n+2)))-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=Int(Sqrt(2*n-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.
|
|
|
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).
|
|
|
CROSSREFS
| Sequence in context: A036042 A162988 A143824 * A071996 A072747 A194295
Adjacent sequences: A034460 A034461 A034462 * A034464 A034465 A034466
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| The reference gives a(5)=3, but this is incorrect, a(5)=2.
More terms from John W. Layman (layman(AT)math.vt.edu), Oct 02 2002
Terms a(36)-a(87) from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Jun 13 2010
|
| |
|
|
