

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

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 sum(1..k)<n; for any n>0, this yields a set of k residue classes where k=round(sqrt(2n))1, which serves as a first lower bound for a(n).
For n>5, another simple method is to select the residue classes 1, n2, 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(2n+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(2n3)) 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/21).
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(2n + 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(2n))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(n1) 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

Table of n, a(n) for n=1..87.


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^(n1)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

Sequence in context: A162988 A143824 A182009 * A259899 A071996 A072747
Adjacent sequences: A034460 A034461 A034462 * A034464 A034465 A034466


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane.


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


STATUS

approved



