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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004136 Additive bases: a(n) is the least integer k such that in the cyclic group Z_k there is a subset of n elements all pairs (of not necessarily distinct elements) of which add up to a different sum (in Z_k).
(Formerly M2639)
4
1, 3, 7, 13, 21, 31, 48, 57, 73, 91, 120, 133, 168, 183, 255, 255, 273, 307 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) >= n^2-n+1 by a volume bound. A difference set construction by Singer shows that equality holds when n-1 is a prime power. When n is a prime power, a difference set construction by Bose shows that a(n) <= n^2-1. By computation, equality holds in the latter bound at least for 7, 11, 13 and 16.

From Fausto A. C. Cariboni, Aug 13 2017: (Start)

Lexicographically first basis that yields a(n) for n=15..18:

a(15) = 255 from {0,1,3,7,15,26,31,53,63,98,107,127,140,176,197}

a(16) = 255 from {0,1,3,7,15,26,31,53,63,98,107,127,140,176,197,215}

a(17) = 273 from {0,1,3,7,15,31,63,90,116,127,136,181,194,204,233,238,255}

a(18) = 307 from {0,1,3,21,25,31,68,77,91,170,177,185,196,212,225,257,269,274}

(End)

REFERENCES

R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404 (v_delta).

H. Haanpaa, A. Huima and P. R. J. Ostergard, Sets in Z_n with Distinct Sums of Pairs, in Optimal discrete structures and algorithms (ODSA 2000). Discrete Appl. Math. 138 (2004), no. 1-2, 99-106.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

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

Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See p. 162.

R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs

H. Haanpaa, A. Huima and P. R. J. Ostergard, Sets in Z_n with Distinct Sums of Pairs, in Optimal discrete structures and algorithms (ODSA 2000). Discrete Appl. Math. 138 (2004), no. 1-2, 99-106. [Annotated scanned copies of four pages only from preprint of paper]

Z. Skupien, A. Zak, Pair-sums packing and rainbow cliques, in Topics In Graph Theory, A tribute to A. A. and T. E. Zykovs on the occasion of A. A. Zykov's 90th birthday, ed. R. Tyshkevich, Univ. Illinois, 2013, pages 131-144, (in English and Russian).

EXAMPLE

a(3)=7: the set {0,1,3} is such a subset of Z_7, since 0+0, 0+1, 0+3, 1+1, 1+3 and 3+3 are all distinct in Z_7; also, no such 3-element set exists in any smaller cyclic group.

CROSSREFS

Cf. A004133, A004135, A260998, A260999.

Sequence in context: A171965 A011898 A098577 * A147409 A147342 A172310

Adjacent sequences:  A004133 A004134 A004135 * A004137 A004138 A004139

KEYWORD

nonn,nice,more,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms and comments from Harri Haanpaa (Harri.Haanpaa(AT)hut.fi), Oct 30 2000

a(15)-a(18) from Fausto A. C. Cariboni, Aug 13 2017

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 16 11:12 EDT 2017. Contains 290623 sequences.