A347570 -id:A347570 - cp's OEIS frontend

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

N. J. A. Sloane and Simon Plouffe

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)

			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.

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

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.

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.

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

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

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

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

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

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

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

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

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

A014206 a(n) = n^2 + n + 2.

Original entry on oeis.org

2, 4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158, 184, 212, 242, 274, 308, 344, 382, 422, 464, 508, 554, 602, 652, 704, 758, 814, 872, 932, 994, 1058, 1124, 1192, 1262, 1334, 1408, 1484, 1562, 1642, 1724, 1808, 1894, 1982, 2072, 2164, 2258, 2354, 2452, 2552

Offset: 0

N. J. A. Sloane

Draw n + 1 circles in the plane; sequence gives maximal number of regions into which the plane is divided. Cf. A051890, A386480.
Number of binary (zero-one) bitonic sequences of length n + 1. - Johan Gade (jgade(AT)diku.dk), Oct 15 2003
Also the number of permutations of n + 1 which avoid the patterns 213, 312, 13452 and 34521. Example: the permutations of 4 which avoid 213, 312 (and implicitly 13452 and 34521) are 1234, 1243, 1342, 1432, 2341, 2431, 3421, 4321. - Mike Zabrocki, Jul 09 2007
If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is equal to the number of (n-3)-subsets and (n-1)-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007
With a different offset, competition number of the complete tripartite graph K_{n, n, n}. [Kim, Sano] - Jonathan Vos Post, May 14 2009. Cf. A160450, A160457.
A related sequence is A241119. - Avi Friedlich, Apr 28 2015
From Avi Friedlich, Apr 28 2015: (Start)
This sequence, which also represents the number of Hamiltonian paths in K_2 X P_n (A200182), may be represented by interlacing recursive polynomials in arithmetic progression (discriminant =-63). For example:
a(3*k-3) = 9*k^2 - 15*k + 8,
a(3*k-2) = 9*k^2 - 9*k  + 4,
a(3*k-1) = 9*k^2 - 3*k  + 2,
a(3*k)   = 3*(k+1)^2  - 1. (End)
a(n+1) is the area of a triangle with vertices at (n+3, n+4), ((n-1)*n/2, n*(n+1)/2),((n+1)^2, (n+2)^2) with n >= -1. - J. M. Bergot, Feb 02 2018
For prime p and any integer k, k^a(p-1) == k^2 (mod p^2). - Jianing Song, Apr 20 2019
From Bernard Schott, Jan 01 2021: (Start)
For n >= 1, a(n-1) is the number of solutions x in the interval 0 <= x <= n of the equation x^2 - [x^2] = (x - [x])^2, where [x] = floor(x). For n = 3, the a(2) = 8 solutions in the interval [0, 3] are 0, 1, 3/2, 2, 9/4, 5/2, 11/4 and 3.
This is a variant of the 4th problem proposed during the 20th British Mathematical Olympiad in 1984 (see A002061). The interval [1, n] of the Olympiad problem becomes here [0, n], and only the new solution x = 0 is added. (End)
See A386480 for the almost identical sequence 1, 2, 4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, ... which is the maximum number of regions that can be formed in the plane by drawing n circles, and the maximum number of regions that can be formed on the sphere by drawing n great circles. - N. J. A. Sloane, Aug 01 2025

			a(0) = 0^2 + 0 + 2 = 2.
a(1) = 1^2 + 1 + 2 = 4.
a(2) = 2^2 + 2 + 2 = 8.
a(6) = 4*5/5 + 5*6/5 + 6*7/5 + 7*8/5 + 8*9/5 = 44. - _Bruno Berselli_, Oct 20 2016

K. E. Batcher, Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, pp. 307-314 (1968). [for bitonic sequences]
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 73, Problem 3.
T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms. MIT Press / McGraw-Hill (1990) [for bitonic sequences]
Indiana School Mathematics Journal, vol. 14, no. 4, 1979, p. 4.
D. E. Knuth, The Art of Computer Programming, vol3: Sorting and Searching, Addison-Wesley (1973) [for bitonic sequences]
J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 177.
Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.
A. M. Yaglom and I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964)

N. J. A. Sloane, Table of n, a(n) for n = 0..1000
A. Burstein, S. Kitaev, and T. Mansour, Partially ordered patterns and their combinatorial interpretations, PU. M. A. Vol. 19 (2008), No. 2-3, pp. 27-38.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
S.-R. Kim and Y. Sano, The competition numbers of complete tripartite graphs, Discrete Appl. Math., 156 (2008) 3522-3524.
Hans Werner Lang, Bitonic sequences.
Daniel Q. Naiman and Edward R. Scheinerman, Arbitrage and Geometry, arXiv:1709.07446 [q-fin.MF], 2017.
Jean-Christoph Novelli and Anne Schilling, The Forgotten Monoid, arXiv 0706.2996 [math.CO], 2007.
Parabola, Problem #Q736, 24(1) (1988), p. 22.
Franck Ramaharo, Enumerating the states of the twist knot, arXiv:1712.06543 [math.CO], 2017.
Franck Ramaharo, Statistics on some classes of knot shadows, arXiv:1802.07701 [math.CO], 2018.
Franck Ramaharo, A generating polynomial for the two-bridge knot with Conway's notation C(n,r), arXiv:1902.08989 [math.CO], 2019.
Yoshio Sano, The competition numbers of regular polyhedra, arXiv:0905.1763 [math.CO], 2009.
Jeffrey Shallit, Recursivity: An Interesting but Little-Known Function, 2012. [Mentions this function in a blog post as the solution for small n to a problem involving Boolean matrices whose values for larger n are unknown.]
Eric Weisstein's World of Mathematics, Plane Division by Circles.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A014206 (dim 2), A046127 (dim 3), A059173 (dim 4), A059174 (dim 5).
A row of A059250.
Cf. A000124, A051890, A002522, A241119, A033547 (partial sums).
Cf. A002061 (central polygonal numbers).
Cf. A003682, A160450, A160457, A200182, A386480.
Column 4 of A347570.

[n^2+n+2: n in [0..50]]; // Vincenzo Librandi, Apr 29 2015

Maple
```
A014206 := n->n^2+n+2;
```

Table[n^2 + n + 2, {n, 0, 50}] (* Stefan Steinerberger, Apr 08 2006 *)
LinearRecurrence[{3, -3, 1}, {2, 4, 8}, 50] (* Harvey P. Dale, May 14 2011 *)
CoefficientList[Series[2 (x^2 - x + 1)/(1 - x)^3, {x, 0, 50}], x] (* Vincenzo Librandi, Apr 29 2015 *)

a(n)=n^2+n+2 \\ Charles R Greathouse IV, Jul 31 2011

x='x+O('x^100); Vec(2*x*(x^2-x+1)/(1-x)^3) \\ Altug Alkan, Nov 01 2015

G.f.: 2*(x^2 - x + 1)/(1 - x)^3.
n hyperspheres divide R^k into at most C(n-1, k) + Sum_{i = 0..k} C(n, i) regions.
a(n) = A002061(n+1) + 1 for n >= 0. - Rick L. Shepherd, May 30 2005
Equals binomial transform of [2, 2, 2, 0, 0, 0, ...]. - Gary W. Adamson, Jun 18 2008
a(n) = A003682(n+1), n > 0. - R. J. Mathar, Oct 28 2008
a(n) = a(n-1) + 2*n (with a(0) = 2). - Vincenzo Librandi, Nov 20 2010
a(0) = 2, a(1) = 4, a(2) = 8, a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n >= 3. - Harvey P. Dale, May 14 2011
a(n + 1) = n^2 + 3*n + 4. - Alonso del Arte, Apr 12 2015
a(n) = Sum_{i=n-2..n+2} i*(i + 1)/5. - Bruno Berselli, Oct 20 2016
Sum_{n>=0} 1/a(n) = Pi*tanh(Pi*sqrt(7)/2)/sqrt(7). - Amiram Eldar, Jan 09 2021
From Amiram Eldar, Jan 29 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(11)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=0} (1 - 1/a(n)) = cosh(sqrt(3)*Pi/2)*sech(sqrt(7)*Pi/2). (End)
a(n) = 2*A000124(n). - R. J. Mathar, Mar 14 2021
E.g.f.: exp(x)*(2 + 2*x + x^2). - Stefano Spezia, Apr 30 2022

More terms from Stefan Steinerberger, Apr 08 2006

A365515 Table read by antidiagonals upward: the n-th row gives the lexicographically earliest infinite B_n sequence starting from 0.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 3, 3, 0, 1, 4, 7, 4, 0, 1, 5, 13, 12, 5, 0, 1, 6, 21, 32, 20, 6, 0, 1, 7, 31, 55, 71, 30, 7, 0, 1, 8, 43, 108, 153, 124, 44, 8, 0, 1, 9, 57, 154, 366, 368, 218, 65, 9, 0, 1, 10, 73, 256, 668, 926, 856, 375, 80, 10, 0, 1, 11, 91, 333, 1153, 2214, 2286, 1424, 572, 96, 11

Offset: 1

Chai Wah Wu, Sep 07 2023

A B_n sequence is a sequence such that all sums a(x_1) + a(x_2) + ... + a(x_n) are distinct for 1 <= x_1 <= x_2 <= ... <= x_n. Analogous to A347570 except that here the B_n sequences start from a(1) = 0.

			Table begins:
n\k | 1  2   3   4    5     6      7      8       9
----+---------------------------------------------------
  1 | 0, 1,  2,  3,   4,    5,     6,     7,      8, ...
  2 | 0, 1,  3,  7,  12,   20,    30,    44,     65, ...
  3 | 0, 1,  4, 13,  32,   71,   124,   218,    375, ...
  4 | 0, 1,  5, 21,  55,  153,   368,   856,   1424, ...
  5 | 0, 1,  6, 31, 108,  366,   926,  2286,   5733, ...
  6 | 0, 1,  7, 43, 154,  668,  2214,  6876,  16864, ...
  7 | 0, 1,  8, 57, 256, 1153,  4181, 14180,  47381, ...
  8 | 0, 1,  9, 73, 333, 1822,  8043, 28296, 102042, ...
  9 | 0, 1, 10, 91, 500, 3119, 13818, 59174, 211135, ...

Chai Wah Wu, Table of n, a(n) for n = 1..242
Eric Weisstein's World of Mathematics, B2 Sequence.

Cf. A001477 (n=1), A025582 (n=2), A051912 (n=3), A365300 (n=4), A365301 (n=5), A365302 (n=6), A365303 (n=7), A365304 (n=8), A365305 (n=9), A002061 (k=4), A369817 (k=5), A369818 (k=6), A369819 (k=7), A347570.

from itertools import count, islice, combinations_with_replacement
def A365515_gen(): # generator of terms
    asets, alists, klist = [set()], [[]], [0]
    while True:
        for i in range(len(klist)-1,-1,-1):
            kstart, alist, aset = klist[i], alists[i], asets[i]
            for k in count(kstart):
                bset = set()
                for d in combinations_with_replacement(alist+[k],i):
                    if (m:=sum(d)+k) in aset:
                        break
                    bset.add(m)
                else:
                    yield k
                    alists[i].append(k)
                    klist[i] = k+1
                    asets[i].update(bset)
                    break
        klist.append(0)
        asets.append(set())
        alists.append([])
A365515_list = list(islice(A365515_gen(),30))

a(n) = A347570(n)-1.

A096772 A B3-sequence: a(1) = 1; for n>1, a(n) = smallest number > a(n-1) such that the sums of any three terms are all distinct.

Original entry on oeis.org

1, 2, 5, 14, 33, 72, 125, 219, 376, 573, 745, 1209, 1557, 2442, 3098, 4048, 5298, 6704, 7839, 10987, 12332, 15465, 19144, 24546, 28974, 34406, 37769, 45864, 50877, 61372, 68303, 77918, 88545, 101917, 122032, 131625, 148575, 171237, 197815, 201454

Offset: 1

Rick L. Shepherd, Aug 15 2004

nonn

This is the B3-sequence analog of the Mian-Chowla B2-sequence (A005282): Let a(1)=1; then use the greedy algorithm to choose the smallest a(n) > a(n-1) such that all sums a(i) + a(j) + a(k) are distinct for 1 <= i <= j <= k <= n. The reciprocal sum of the sequence for the first forty terms is 1.837412....

Chai Wah Wu, Table of n, a(n) for n = 1..176
Eric Weisstein's World of Mathematics, B2-Sequence.
Eric Weisstein's World of Mathematics, Mian-Chowla Sequence.

Row 3 of A347570.

Cf. A005282 (Mian-Chowla B2-sequence). A051912.

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

a(n) = A051912(n-1) + 1. - Peter Kagey, Oct 20 2021

A370754 a(n) = 2 + n^2floor((n+3)/2) + floor(3n/2).

Original entry on oeis.org

5, 13, 33, 56, 109, 155, 257, 334, 501, 617, 865, 1028, 1373, 1591, 2049, 2330, 2917, 3269, 4001, 4432, 5325, 5843, 6913, 7526, 8789, 9505, 10977, 11804, 13501, 14447, 16385, 17458, 19653, 20861, 23329, 24680, 27437, 28939, 32001, 33662, 37045, 38873, 42593, 44596

Offset: 1

Chai Wah Wu, Feb 29 2024

{1, 2, n+2, n^2+n+2, a(n)} is the lexicographically first set of 5 positive integers with the property that the sum of any n nondecreasing terms (repetitions allowed) is unique.

Paolo Xausa, Table of n, a(n) for n = 1..10000
M. B. Nathanson, The third positive element in the greedy B_h-set, arXiv:2310.14426 [math.NT], 2023.
M. B. Nathanson and Kevin O'Bryant, The fourth positive element in the greedy B_h-set, arXiv:2311.14021 [math.NT], 2023.
Kevin O'Bryant, B_h-sets and Rigidity, arXiv:2312.10910 [math.NT], 2023.
Index entries for linear recurrences with constant coefficients, signature (1,3,-3,-3,3,1,-1).

Cf. A347570, A365515, A369817.

A370754[n_] := 2 + n^2*Floor[(n+3)/2] + Floor[3*n/2]; Array[A370754, 50] (* or *)
LinearRecurrence[{1, 3, -3, -3, 3, 1, -1}, {5, 13, 33, 56, 109, 155, 257}, 50] (* Paolo Xausa, Mar 08 2024 *)

Column 5 of A347570.
a(n) = A369817(n) + 1.
a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3) - 3*a(n-4) + 3*a(n-5) + a(n-6) - a(n-7) for n > 7.
G.f.: x*(-2*x^6 + x^5 + 8*x^4 - x^3 + 5*x^2 + 8*x + 5)/((x - 1)*(x^2 - 1)^3).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A014206 a(n) = n^2 + n + 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A365515 Table read by antidiagonals upward: the n-th row gives the lexicographically earliest infinite B_n sequence starting from 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A096772 A B3-sequence: a(1) = 1; for n>1, a(n) = smallest number > a(n-1) such that the sums of any three terms are all distinct.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A370754 a(n) = 2 + n^2*floor((n+3)/2) + floor(3*n/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A370754 a(n) = 2 + n^2floor((n+3)/2) + floor(3n/2).