A004136 -id:A004136 - cp's OEIS frontend

A004135 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 distinct elements) of which add up to a different sum (in Z_k).

1, 2, 3, 6, 11, 19, 28, 40, 56, 72, 96, 114, 147, 178, 183, 252, 255

Offset: 1

From Fausto A. C. Cariboni, Oct 08 2017: (Start)
Lexicographically first basis that yields a(n) for n=16:
a(16) = 252 from {0,1,2,4,32,47,54,65,94,120,128,145,169,196,217,240}
(End)
From Fausto A. C. Cariboni, Mar 12 2018: (Start)
Lexicographically first basis that yields a(n) for n=17:
a(17) = 255 from {0,1,2,4,8,16,27,32,54,64,99,108,128,141,177,198,216}
(End)

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

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

Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Problem C.61.
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404.
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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.
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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) [gives the term 183].

Cf. A004136, A004133, A260998, A260999.

More terms and comments from Harri Haanpaa (Harri.Haanpaa(AT)hut.fi), Nov 01 2000
a(16) from Fausto A. C. Cariboni, Oct 08 2017
a(17) from Fausto A. C. Cariboni, Mar 12 2018

A325787 Number of perfect strict necklace compositions of n.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, May 22 2019

nonn

A strict necklace composition of n is a finite sequence of distinct positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. In other words, it is a strict composition of n starting with its least part. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence. For example, the composition (1,2,6,4) is perfect because it has the following circular subsequences and sums:
(1)
(2)
(1,2)
(4)
(4,1)
(6)
(4,1,2)
(2,6)
(1,2,6)
(6,4)
(6,4,1)
(2,6,4)
(1,2,6,4)
a(n) > 0 iff n = A002061(k) = A004136(k) for some k. - Bert Dobbelaere, Nov 11 2020

			The a(1) = 1 through a(31) = 10 perfect strict necklace compositions (empty columns not shown):
  (1)  (1,2)  (1,2,4)  (1,2,6,4)  (1,3,10,2,5)  (1,10,8,7,2,3)
              (1,4,2)  (1,3,2,7)  (1,5,2,10,3)  (1,13,6,4,5,2)
                       (1,4,6,2)                (1,14,4,2,3,7)
                       (1,7,2,3)                (1,14,5,2,6,3)
                                                (1,2,5,4,6,13)
                                                (1,2,7,4,12,5)
                                                (1,3,2,7,8,10)
                                                (1,3,6,2,5,14)
                                                (1,5,12,4,7,2)
                                                (1,7,3,2,4,14)
From _Bert Dobbelaere_, Nov 11 2020: (Start)
Compositions matching nonzero terms from a(57) to a(273), up to symmetry.
a(57) = 12:
  (1,2,10,19,4,7,9,5)
  (1,3,5,11,2,12,17,6)
  (1,3,8,2,16,7,15,5)
  (1,4,2,10,18,3,11,8)
  (1,4,22,7,3,6,2,12)
  (1,6,12,4,21,3,2,8)
a(73) = 8:
  (1,2,4,8,16,5,18,9,10)
  (1,4,7,6,3,28,2,8,14)
  (1,6,4,24,13,3,2,12,8)
  (1,11,8,6,4,3,2,22,16)
a(91) = 12:
  (1,2,6,18,22,7,5,16,4,10)
  (1,3,9,11,6,8,2,5,28,18)
  (1,4,2,20,8,9,23,10,3,11)
  (1,4,3,10,2,9,14,16,6,26)
  (1,5,4,13,3,8,7,12,2,36)
  (1,6,9,11,29,4,8,2,3,18)
a(133) = 36:
  (1,2,9,8,14,4,43,7,6,10,5,24)
  (1,2,12,31,25,4,9,10,7,11,16,5)
  (1,2,14,4,37,7,8,27,5,6,13,9)
  (1,2,14,12,32,19,6,5,4,18,13,7)
  (1,3,8,9,5,19,23,16,13,2,28,6)
  (1,3,12,34,21,2,8,9,5,6,7,25)
  (1,3,23,24,6,22,10,11,18,2,5,8)
  (1,4,7,3,16,2,6,17,20,9,13,35)
  (1,4,16,3,15,10,12,14,17,33,2,6)
  (1,4,19,20,27,3,6,25,7,8,2,11)
  (1,4,20,3,40,10,9,2,15,16,6,7)
  (1,5,12,21,29,11,3,16,4,22,2,7)
  (1,7,13,12,3,11,5,18,4,2,48,9)
  (1,8,10,5,7,21,4,2,11,3,26,35)
  (1,14,3,2,4,7,21,8,25,10,12,26)
  (1,14,10,20,7,6,3,2,17,4,8,41)
  (1,15,5,3,25,2,7,4,6,12,14,39)
  (1,22,14,20,5,13,8,3,4,2,10,31)
a(183) = 40:
  (1,2,13,7,5,14,34,6,4,33,18,17,21,8)
  (1,2,21,17,11,5,9,4,26,6,47,15,12,7)
  (1,2,28,14,5,6,9,12,48,18,4,13,16,7)
  (1,3,5,6,25,32,23,10,18,2,17,7,22,12)
  (1,3,12,7,20,14,44,6,5,24,2,28,8,9)
  (1,3,24,6,12,14,11,55,7,2,8,5,16,19)
  (1,4,6,31,3,13,2,7,14,12,17,46,8,19)
  (1,4,8,52,3,25,18,2,9,24,6,10,7,14)
  (1,4,20,2,12,3,6,7,33,11,8,10,35,31)
  (1,5,2,24,15,29,14,21,13,4,33,3,9,10)
  (1,5,23,27,42,3,4,11,2,19,12,10,16,8)
  (1,6,8,22,4,5,33,21,3,20,32,16,2,10)
  (1,8,3,10,23,5,56,4,2,14,15,17,7,18)
  (1,8,21,45,6,7,11,17,3,2,10,4,23,25)
  (1,9,5,40,3,4,21,35,16,18,2,6,11,12)
  (1,9,14,26,4,2,11,5,3,12,27,34,7,28)
  (1,9,21,25,3,4,8,5,6,16,2,36,14,33)
  (1,10,22,34,27,12,3,4,2,14,24,5,8,17)
  (1,10,48,9,19,4,8,6,7,17,3,2,34,15)
  (1,12,48,6,2,38,3,22,7,10,11,5,4,14)
a(273) = 12:
  (1,2,4,8,16,32,27,26,11,9,45,13,10,29,5,17,18)
  (1,3,12,10,31,7,27,2,6,5,19,20,62,14,9,28,17)
  (1,7,3,15,33,5,24,68,2,14,6,17,4,9,19,12,34)
  (1,7,12,44,25,41,9,17,4,6,22,33,13,2,3,11,23)
  (1,7,31,2,11,3,9,36,17,4,22,6,18,72,5,10,19)
  (1,21,11,50,39,13,6,4,14,16,25,26,3,2,7,8,27)
(End)

Bert Dobbelaere, Table of n, a(n) for n = 1..306

Cf. A002033, A002061, A004136, A008965, A032153, A103300, A126796, A325680, A325682, A325780, A325782, A325786, A325788, A325789.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]],{n,30}]

More terms from Bert Dobbelaere, Nov 11 2020

A004133 Additive bases: a(n) is the least integer such that there is an n-element set of nonnegative integers, the sums of pairs (of distinct elements) of which are distinct and at most a(n).

Original entry on oeis.org

1, 3, 6, 11, 19, 31, 43, 63, 80, 110, 138, 169, 202, 241, 288, 330

Offset: 2

N. J. A. Sloane

a(11) = 110 from the basis {0 1 2 4 8 15 24 29 34 46 64}. a(12)<=138 from {0 1 2 4 19 30 37 42 50 58 64 74} or {0 1 2 7 12 22 37 40 54 63 67 71} or {0 2 4 18 26 34 49 54 55 61 64 74}, for example. a(13) <= 169 from {0 1 2 5 16 30 38 47 59 65 71 78 91} or {0 1 2 5 18 28 35 50 59 65 71 79 90}. a(14) <= 202 from {0 1 2 4 7 24 38 47 56 66 74 82 95 107}. a(15) <= 250 from {0 1 2 4 13 40 61 67 83 90 98 108 113 118 132}. - R. J. Mathar, Mar 17 2007
From Jon E. Schoenfield, Aug 24 2009: (Start)
Lexicographically first basis that yields a(n) for n = 2..13:
a(2) = 1 from {0 1}
a(3) = 3 from {0 1 2}
a(4) = 6 from {0 1 2 4}
a(5) = 11 from {0 1 2 4 7}
a(6) = 19 from {0 1 2 4 7 12}
a(7) = 31 from {0 1 2 4 8 13 18}
a(8) = 43 from {0 1 2 4 8 14 19 24}
a(9) = 63 from {0 1 2 4 8 15 24 29 34}
a(10) = 80 from {0 1 2 4 8 15 24 29 34 46}
a(11) = 110 from {0 1 2 4 8 15 24 29 34 46 64}
a(12) = 138 from {0 1 2 4 19 30 37 42 50 58 64 74}
a(13) = 169 from {0 1 2 5 16 30 38 47 59 65 71 78 91}
(End)
From Lars Blomberg, Oct 31 2015: (Start)
Lexicographically first basis that yields a(n) for n=14..16:
a(14) = 202 from {0,1,2,4,7,24,38,47,56,66,74,82,95,107}
a(15) = 241 from {0,1,2,22,26,36,43,50,82,90,95,98,101,113,128}
a(16) = 288 from {0,4,5,10,31,43,55,58,92,100,111,120,122,129,136,152}
(End)
Lexicographically first basis that yields a(17) = 330 is {0,5,9,10,11,43,62,75,88,112,115,129,136,143,151,159,171}. - Fausto A. C. Cariboni, Oct 24 2017

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

R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), pp. 382-404 (v_alpha).
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs [alternate link]
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).

Cf. A004135, A004136. See A232234 for a slight variation.

a(11) from R. J. Mathar, Mar 17 2007
Two more terms from Jon E. Schoenfield, Aug 24 2009
202 and 241 from Skupien et al. - N. J. A. Sloane, Nov 24 2013
a(16) from Lars Blomberg, Oct 31 2015
a(17) from Fausto A. C. Cariboni, Oct 24 2017

A260998 Maximal size of a subset of Z_n with distinct sums of pairs (of distinct elements).

Original entry on oeis.org

1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 1

N. J. A. Sloane, Aug 10 2015

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..254
Fausto A. C. Cariboni, S_2-sets that yield a(n) for n = 2..254, Mar 24 2018.
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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]
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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.

Cf. A004135, A004136, A260999.

By the pigeonhole principle, C(a(n),2) <= n, yielding upper bound a(n) <= floor((1+sqrt(8*n+1))/2). - Rob Pratt, Nov 27 2017

a(1)-a(90) from H. Haanpaa, A. Huima and Patric R. J. Östergård (see link), Nov 08 2000

a(1)-a(90) confirmed by Fausto A. C. Cariboni, Nov 09 2017

A260999 Maximal size of a subset of Z_n with distinct sums of any two elements.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8

Offset: 1

N. J. A. Sloane, Aug 10 2015

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..295
Fausto A. C. Cariboni, Sets that yield a(n) for n = 2..295, Jan 27 2018.
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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]
H. Haanpaa, A. Huima and Patric R. J. Östergård, 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.

Cf. A004135, A004136, A260998.

By the pigeonhole principle, C(a(n)+1,2) <= n, yielding upper bound a(n) <= floor((-1+sqrt(8*n+1))/2). - Rob Pratt, Nov 27 2017

More terms from Rob Pratt, Nov 27 2017

cp's OEIS Frontend

A004135 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 distinct elements) of which add up to a different sum (in Z_k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A325787 Number of perfect strict necklace compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A004133 Additive bases: a(n) is the least integer such that there is an n-element set of nonnegative integers, the sums of pairs (of distinct elements) of which are distinct and at most a(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A260998 Maximal size of a subset of Z_n with distinct sums of pairs (of distinct elements).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A260999 Maximal size of a subset of Z_n with distinct sums of any two elements.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions