cp's OEIS Frontend

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

%I A004136 M2639 #41 Feb 02 2020 20:10:55
%S A004136 1,3,7,13,21,31,48,57,73,91,120,133,168,183,255,255,273,307
%N 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).
%C A004136 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.
%C A004136 From _Fausto A. C. Cariboni_, Aug 13 2017: (Start)
%C A004136 Lexicographically first basis that yields a(n) for n=15..18:
%C A004136 a(15) = 255 from {0,1,3,7,15,26,31,53,63,98,107,127,140,176,197}
%C A004136 a(16) = 255 from {0,1,3,7,15,26,31,53,63,98,107,127,140,176,197,215}
%C A004136 a(17) = 273 from {0,1,3,7,15,31,63,90,116,127,136,181,194,204,233,238,255}
%C A004136 a(18) = 307 from {0,1,3,21,25,31,68,77,91,170,177,185,196,212,225,257,269,274}
%C A004136 (End)
%C A004136 Such sets are also known as modular Golomb rulers, or circular Golomb rulers. - _Andrey Zabolotskiy_, Sep 11 2017
%D A004136 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A004136 Bela Bajnok, <a href="https://arxiv.org/abs/1705.07444">Additive Combinatorics: A Menu of Research Problems</a>, arXiv:1705.07444 [math.NT], May 2017. See p. 162.
%H A004136 R. L. Graham and N. J. A. Sloane, <a href="http://neilsloane.com/doc/RLG/073.pdf">On Additive Bases and Harmonious Graphs</a>, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404 (v_delta).
%H A004136 H. Haanpaa, A. Huima and Patric R. J. Östergård, <a href="https://doi.org/10.1016/S0166-218X(03)00273-7">Sets in Z_n with Distinct Sums of Pairs</a>, in Optimal discrete structures and algorithms (ODSA 2000). Discrete Appl. Math. 138 (2004), no. 1-2, 99-106.
%H A004136 H. Haanpaa, A. Huima and Patric R. J. Östergård, <a href="/A004135/a004135.pdf">Sets in Z_n with Distinct Sums of Pairs</a>, 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 above]
%H A004136 Z. Skupien, A. Zak, Pair-sums packing and rainbow cliques, in <a href="http://www.math.uiuc.edu/~kostochk/Zykov90-Topics_in_Graph_Theory.pdf">Topics In Graph Theory</a>, 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).
%e A004136 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.
%Y A004136 Cf. A004133, A004135, A260998, A260999, A003022.
%K A004136 nonn,nice,more
%O A004136 1,2
%A A004136 _N. J. A. Sloane_
%E A004136 More terms and comments from Harri Haanpaa (Harri.Haanpaa(AT)hut.fi), Oct 30 2000
%E A004136 a(15)-a(18) from _Fausto A. C. Cariboni_, Aug 13 2017