%I M1094 #104 Aug 29 2024 11:28:30
%S 1,2,4,8,13,21,31,45,66,81,97,123,148,182,204,252,290,361,401,475,565,
%T 593,662,775,822,916,970,1016,1159,1312,1395,1523,1572,1821,1896,2029,
%U 2254,2379,2510,2780,2925,3155,3354,3591,3797,3998,4297,4433,4779,4851
%N 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.
%C 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]
%C 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
%C Let S denote the reciprocal sum of a(n). Then 2.158452685 <= S <= 2.158532684. - _Raffaele Salvia_, Jul 19 2014
%C From _Thomas Ordowski_, Sep 19 2014: (Start)
%C Known estimate: n^2/2 + O(n) < a(n) < n^3/6 + O(n^2).
%C Conjecture: a(n) ~ n^3 / log(n)^2.
%C (End)
%D P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.20.2.
%D R. K. Guy, Unsolved Problems in Number Theory, E28.
%D A. M. Mian and S. D. Chowla, On the B_2-sequences of Sidon, Proc. Nat. Acad. Sci. India, A14 (1944), 3-4.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005282/b005282.txt">Table of n, a(n) for n=1..5818</a> (terms less than 2*10^9)
%H Thomas Bloom, <a href="https://www.erdosproblems.com/340">Problem 340</a>, Erdős Problems.
%H Yin Choi Cheng, <a href="https://doi.org/10.1016/j.jnt.2024.07.010">Greedy Sidon sets for linear forms</a>, J. Num. Theor. (2024).
%H Rachel Lewis, <a href="/A005282/a005282.pdf">Mian-Chowla and B2 sequences</a>, 1999. [Thanks to _Steven Finch_ for providing this document. Included with permission. - _N. J. A. Sloane_, Jan 02 2020]
%H Kevin O'Bryant, <a href="https://arxiv.org/abs/2312.10910">B_h-Sets and Rigidity</a>, arXiv:2312.10910 [math.NT], 2023.
%H Raffaele Salvia, <a href="/A005282/a005282.txt">Table of n, a(n) for n=1...25000</a>
%H R. Salvia, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Salvia/salvia3.html">A New Lower Bound for the Distinct Distance Constant</a>, J. Int. Seq. 18 (2015) # 15.4.8.
%H N. J. A. Sloane, <a href="/A001149/a001149.pdf">Handwritten notes on Self-Generating Sequences, 1970</a> (note that A1148 has now become A005282)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/B2-Sequence.html">B2 Sequence.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Mian-ChowlaSequence.html">Chowla Sequence.</a>
%H Zhang Zhen-Xiang, <a href="http://dx.doi.org/10.1090/S0025-5718-1993-1181334-7">A B_2-sequence with larger reciprocal sum</a>, Math. Comp. 60 (1993), 835-839.
%H <a href="/index/Br#B_2">Index entries for B_2 sequences.</a>
%F a(n) = A025582(n) + 1.
%F a(n) = (A034757(n)+1)/2.
%e The second term is 2 because the 3 pairwise sums 1+1=2, 1+2=3, 2+2=4 are all distinct.
%e 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 a[1]:= 1: P:= {2}: A:= {1}:
%p for n from 2 to 100 do
%p for t from a[n-1]+1 do
%p Pt:= map(`+`,A union {t},t);
%p if Pt intersect P = {} then break fi
%p od:
%p a[n]:= t;
%p A:= A union {t};
%p P:= P union Pt;
%p od:
%p seq(a[n],n=1..100); # _Robert Israel_, Sep 21 2014
%t 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 *)
%o (Haskell)
%o import Data.Set (Set, empty, insert, member)
%o a005282 n = a005282_list !! (n-1)
%o a005282_list = sMianChowla [] 1 empty where
%o sMianChowla :: [Integer] -> Integer -> Set Integer -> [Integer]
%o sMianChowla sums z s | s' == empty = sMianChowla sums (z+1) s
%o | otherwise = z : sMianChowla (z:sums) (z+1) s
%o where s' = try (z:sums) s
%o try :: [Integer] -> Set Integer -> Set Integer
%o try [] s = s
%o try (x:sums) s | (z+x) `member` s = empty
%o | otherwise = try sums $ insert (z+x) s
%o -- _Reinhard Zumkeller_, Mar 02 2011
%o (PARI) A005282_vec(N, A=[1], U=[0], D(A, n=#A)=vector(n-1, k, A[n]-A[n-k]))={ while(#A<N, my(k=1); A=concat(A,A[#A]+U[1]); until(!setintersect(U,D(A)), A[#A]++); U=setunion(U,D(A)); while(k<#U && U[k++]<U[1]+k,); k>2 && U=U[k-1..-1]);A} \\ _M. F. Hasler_, Oct 09 2019
%o (Python)
%o from itertools import count, islice
%o def A005282_gen(): # generator of terms
%o aset1, aset2, alist = set(), set(), []
%o for k in count(1):
%o bset2 = {k<<1}
%o if (k<<1) not in aset2:
%o for d in aset1:
%o if (m:=d+k) in aset2:
%o break
%o bset2.add(m)
%o else:
%o yield k
%o alist.append(k)
%o aset1.add(k)
%o aset2 |= bset2
%o A005282_list = list(islice(A005282_gen(),30)) # _Chai Wah Wu_, Sep 05 2023
%Y Row 2 of A347570.
%Y Cf. A051788, A080200 (for differences between terms).
%Y Different from A046185. Cf. A011185.
%Y See also A003022, A227590.
%Y A259964 has a greater sum of reciprocals.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_ and _Simon Plouffe_
%E Examples added by _N. J. A. Sloane_, Jun 01 2008