A005282 Mian-Chowla sequence (a B_2 sequence): a(1) = 1; for n>1, a(n) = smallest number > a(n-1) such that the pairwise sums of elements are all distinct.

1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851

Offset: 1

Author

N. J. A. Sloane and Simon Plouffe

Keywords

• nonn
• nice

Comments

An alternative definition is to start with 1 and then continue with the least number such that all pairwise differences of distinct elements are all distinct. - Jens Voß, Feb 04 2003. [However, compare A003022 and A227590. - N. J. A. Sloane, Apr 08 2016]

Rachel Lewis points out [see link] that S, the sum of the reciprocals of this sequence, satisfies 2.158435 <= S <= 2.158677. Similarly, the sum of the squares of reciprocals of this sequence converges to approximately 1.33853369 and the sum of the cube of reciprocals of this sequence converges to approximately 1.14319352. - Jonathan Vos Post, Nov 21 2004; comment changed by N. J. A. Sloane, Jan 02 2020

Let S denote the reciprocal sum of a(n). Then 2.158452685 <= S <= 2.158532684. - Raffaele Salvia, Jul 19 2014

From Thomas Ordowski, Sep 19 2014: (Start)

Known estimate: n^2/2 + O(n) < a(n) < n^3/6 + O(n^2).

Conjecture: a(n) ~ n^3 / log(n)^2. (End)

Examples

			The second term is 2 because the 3 pairwise sums 1+1=2, 1+2=3, 2+2=4 are all distinct.
The third term cannot be 3 because 1+3 = 2+2. But it can be 4, since 1+4=5, 2+4=6, 4+4=8 are distinct and distinct from the earlier sums 1+1=2, 1+2=3, 2+2=4.
		

References

• P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique (1980).
• S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.20.2.
• R. K. Guy, Unsolved Problems in Number Theory, E28.
• A. M. Mian and S. D. Chowla, On the B_2-sequences of Sidon, Proc. Nat. Acad. Sci. India, A14 (1944), 3-4.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..5818 (terms less than 2*10^9)
• Thomas Bloom, Problem 340, Erdős Problems.
• Yin Choi Cheng, Greedy Sidon sets for linear forms, J. Num. Theor. (2024).
• Rachel Lewis, Mian-Chowla and B2 sequences, 1999. [Thanks to _Steven Finch_ for providing this document. Included with permission. - _N. J. A. Sloane_, Jan 02 2020]
• Kevin O'Bryant, B_h-Sets and Rigidity, arXiv:2312.10910 [math.NT], 2023.
• Raffaele Salvia, Table of n, a(n) for n=1...25000
• R. Salvia, A New Lower Bound for the Distinct Distance Constant, J. Int. Seq. 18 (2015) # 15.4.8.
• N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970 (note that A1148 has now become A005282)
• Eric Weisstein's World of Mathematics, B2 Sequence.
• Eric Weisstein's World of Mathematics, Chowla Sequence.
• Zhang Zhen-Xiang, A B_2-sequence with larger reciprocal sum, Math. Comp. 60 (1993), 835-839.
• Index entries for B_2 sequences.

Crossrefs

Row 2 of A347570.

Cf. A051788, A080200 (for differences between terms).

Different from A046185. Cf. A011185.

See also A003022, A227590.

A259964 has a greater sum of reciprocals.

Cf. A002858.

Programs

Haskell

import Data.Set (Set, empty, insert, member)
a005282 n = a005282_list !! (n-1)
a005282_list = sMianChowla [] 1 empty where
   sMianChowla :: [Integer] -> Integer -> Set Integer -> [Integer]
   sMianChowla sums z s | s' == empty = sMianChowla sums (z+1) s
                        | otherwise   = z : sMianChowla (z:sums) (z+1) s
      where s' = try (z:sums) s
            try :: [Integer] -> Set Integer -> Set Integer
            try []     s                      = s
            try (x:sums) s | (z+x) `member` s = empty
                           | otherwise        = try sums $ insert (z+x) s
-- Reinhard Zumkeller, Mar 02 2011

Maple

a[1]:= 1: P:= {2}: A:= {1}:
for n from 2 to 100 do
  for t from a[n-1]+1 do
    Pt:= map(`+`,A union {t},t);
    if Pt intersect P = {} then break fi
  od:
  a[n]:= t;
  A:= A union {t};
  P:= P union Pt;
od:
seq(a[n],n=1..100); # Robert Israel, Sep 21 2014

Mathematica

t = {1}; sms = {2}; k = 1; Do[k++; While[Intersection[sms, k + t] != {}, k++]; sms = Join[sms, t + k, {2 k}]; AppendTo[t, k], {49}]; t (* T. D. Noe, Mar 02 2011 *)

PARI

A005282_vec(N, A=[1], U=[0], D(A, n=#A)=vector(n-1, k, A[n]-A[n-k]))={ while(#A2 && U=U[k-1..-1]);A} \\ M. F. Hasler, Oct 09 2019

PARI

aupto(L)= my(S=vector(L), A=[1]); for(i=2, L, for(j=1, #A, if(S[i-A[j]], next(2))); for(j=1, #A, S[i-A[j]]=1); A=concat(A, i)); A \\ Ruud H.G. van Tol, Jun 30 2025

Python

from itertools import count, islice
def A005282_gen(): # generator of terms
    aset1, aset2, alist = set(), set(), []
    for k in count(1):
        bset2 = {k<<1}
        if (k<<1) not in aset2:
            for d in aset1:
                if (m:=d+k) in aset2:
                    break
                bset2.add(m)
            else:
                yield k
                alist.append(k)
                aset1.add(k)
                aset2 |= bset2
A005282_list = list(islice(A005282_gen(),30)) # Chai Wah Wu, Sep 05 2023

Formula

a(n) = A025582(n) + 1.

a(n) = (A034757(n)+1)/2.

Extensions

Examples added by N. J. A. Sloane, Jun 01 2008