A004135 -id:A004135 - 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).

1, 3, 7, 13, 21, 31, 48, 57, 73, 91, 120, 133, 168, 183, 255, 255, 273, 307

Offset: 1

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)
Such sets are also known as modular Golomb rulers, or circular Golomb rulers. - Andrey Zabolotskiy, Sep 11 2017

			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.

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 p. 162.
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 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 above]
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. A004133, A004135, A260998, A260999, A003022.

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

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

A288583 Related to study of weak Sidon sets.

Original entry on oeis.org

1, 2, 3, 6, 11, 19, 28, 42, 56

Offset: 1

N. J. A. Sloane, Jul 06 2017

From Bernd Mulansky, Jun 23 2021: (Start)
Additive bases: a(n) is the least integer k such that in each cyclic group Z_j with j>=k there is a subset of n elements all pairs (of distinct elements) of which add up to a different sum (in Z_j).
Such subsets are known as (modular) weak Sidon sets, weak B_2 sets, or well-spread sequences.
(End)

			Z_j contains a weak Sidon set of size 8 for j=40 and for every j>=42, but not for j=41, hence a(8)=42.

Bela Bajnok, Additive Combinatorics: A Menu of Research Problems. Chapman & Hall/CRC, 2018. See Problem C.65.
A. Maturo and D. Yager-Elorriaga, Finding Sidon sets in abelian groups. Research Papers in Mathematics, B. Bajnok, ed., Gettysburg College, Vol. 7 (2008).

Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], 2017. See Problem C.65 p. 166.

Cf. A004135.

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

Original entry on oeis.org

1, 2, 4, 7, 12, 18, 24, 34, 45, 57, 71, 86, 105, 126, 148

Offset: 2

Bernd Mulansky, Jun 25 2021

Such sets are known as weak Sidon sets, weak B_2 sets, or well-spread sequences.

n - 1 <= a(n) <= A003022(n). - Michael S. Branicky, Jun 25 2021

			a(6)=12 because 0-1-2-4-7-12 (0-5-8-10-11-12) resp. 0-1-2-6-9-12 (0-3-6-10-11-12) are shortest weak Sidon sets of size 6.
a(16)=148: [0, 3, 5, 6, 32, 49, 59, 68, 93, 106, 118, 126, 130, 134, 141, 148]. - _Zhao Hui Du_, Jul 27 2025

Alison M. Marr and W. D. Wallis, Magic Graphs, Birkhäuser, 2nd ed., 2013. See Section 2.3.
Xiaodong Xu, Meilian Liang, and Zehui Shao, On weak Sidon sequences, The Journal of Combinatorial Mathematics and Combinatorial Computing (2014), 107--113

A. Lladó, Largest cliques in connected supermagic graphs, European Journal of Combinatorics, Vol. 28, No. 8 (2007), 2240-2247.

See A003022, A004133, and A004135 for other versions.

a[n_Integer?NonNegative] := Module[{k = n - 1}, While[SelectFirst[Subsets[Range[0, k - 1], {n - 1}], Length@Union[Plus @@@ Subsets[#~Join~{k}, {2}]] >= (n*(n - 1))/2 &] === Missing["NotFound"], k++]; k];
Table[a[n], {n, 2, 8}] (* Robert P. P. McKone, Nov 05 2023 *)

from itertools import combinations, count
def a(n):
    for k in count(n-1):
        for c in combinations(range(k), n-1):
            c = c + (k,)
            ss = set()
            for s in combinations(c, 2):
                if sum(s) in ss: break
                else: ss.add(sum(s))
            if len(ss) == n*(n-1)//2: return k # use (k, c) for sets
print([a(n) for n in range(2, 9)]) # Michael S. Branicky, Jun 25 2021

a(16) corrected and a(17) deleted by Zhao Hui Du, Jul 27 2025

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

A288583 Related to study of weak Sidon sets.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions