A034463 Maximal number of residue classes mod n such that no subset adds to 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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• changed

Comments

From Jon E. Schoenfield, 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 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)

Examples

			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).
		

References

• R. K. Guy, Unsolved Problems in Number Theory, Sect. C15.

Links

• Thomas Bloom, Problem 540, Erdős Problems.

Programs

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

Extensions

The reference gives a(5)=3, but this is incorrect, a(5)=2.

More terms from John W. Layman, Oct 02 2002

Terms a(36)-a(87) from Jon E. Schoenfield, Jun 13 2010