login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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(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(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(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(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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 21:02 EDT 2019. Contains 323499 sequences. (Running on oeis4.)