cp's OEIS Frontend

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)

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 not necessarily distinct elements) of which are distinct.

From David W. Wilson, Aug 17 2007: (Start)

An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.

An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.

A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)

Positions where A143824 increases (see also A227590). - N. J. A. Sloane, Apr 08 2016

From Gus Wiseman, May 17 2019: (Start)

Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:

0: ()

1: (1)

3: (2,1)

6: (2,3,1)

11: (3,1,5,2)

17: (4,2,3,7,1)

Representatives of corresponding Golomb rulers are:

{0}

{0,1}

{0,2,3}

{0,2,5,6}

{0,3,4,9,11}

{0,4,6,9,16,17}

(End)

When the set {x(1),x(2),...,x(k)} satisfies the property that all differences |x(i)-x(j)| are distinct (or alternately, all the sums are distinct), then it is called a Sidon set. So a(n) is the maximum cardinality of a dense Sidon subset of {1,2,...,n}. - Sayan Dutta, Aug 29 2024

See A143823 for the number of subsets of {1, 2, ..., n} with the required property.

See A003022 (and A227590) for the values of n such that a(n+1) > a(n). - Boris Bukh, Jul 28 2013

Can be formulated as an integer linear program: maximize sum {i = 1 to n} z[i] subject to z[i] + z[j] - 1 <= y[i,j] for all i < j, sum {i = 1 to n - d} y[i,i+d] <= 1 for d = 1 to n - 1, z[i] in {0,1} for all i, y[i,j] in {0,1} for all i < j. - Rob Pratt, Feb 09 2010

If the zeroth term is removed, the run-lengths are A270813 with 1 prepended. - Gus Wiseman, Jun 07 2019

Let a set of integers be called "of different average" if any two distinct, nonempty subsets of it have distinct arithmetic means. E.g., the set {1,2,5} is of different average because 1 != 2 != 5 != (1+2)/2 != (1+5)/2 != (2+5)/2 != (1+2+5)/3.

In order for a set to be of different average it is obvious that all its elements must be different. Also, if a set is of different average and a constant k is added to all the terms, the resulting set will also be of different average. Because of this, in order to study such sets it is convenient to select an arbitrary first element, say 1. Therefore the terms of this sequence are defined as: the least a_n such that the set 1 = a_1 < a_2 < a_3 < ... < a_n is of different average.

The set {1,2,4,...,2^(n-1)} satisfies that any natural number can only be written in one way as a sum of elements of the set (each element being allowed to enter only once into the sum), so it is a good candidate as a different average set, and it is so up to 1,2,4,8,16,32, but it fails for 1,...,64, since (4+8+16+64)/4 = (1+2+16+32+64)/5 = 23. Other than by brute force, this can easily be found by noting that the number 23, written in binary notation: 10111, has four ones, hence 4 times the number obviously has four ones too, while 5 times the number = 1110011 has five ones, and those are the subsets.

Conjecture: The only term that is < 2^(n-1) is a(4)=7.

It may be proved that, for n>1, a(n) < 4^(n-1):

Suppose we already have a set of n-1 numbers satisfying the property. If an element a_n is added, 2^n possible sets can be formed, hence fewer than 2^n * 2^n / 2 = 4^n/2 pairs of sets. If a certain value of a_n gives the same average for two such subsets, any other value will yield different averages. It is easy to see that only half the pairs need be considered; hence there is at least one value of a_n < 4^(n-1) that yields different averages for all pairs of subsets.

If more set pairs are excluded, viz. sets that both include a_n and that either have the same number of elements (because the set a_1,...,a_(n-1) is presumed to already satisfy the property) or the set having more elements has a lower average than the other with a_n excluded from both (a_n will eventually be greater than all the other a_i; if not, interchange the a_n found with one of the a_i and "run" the reasoning again), the 4^(n-1) bound may be improved slightly. Note that the latter property of set pairs is transitive, in the sense that if any such pair satisfies the property, the pair formed by adding a_n to both sets also satisfies the property.

What is lim_sup a(n)^(1/n)? The upper bound above proves it is <=4.

Conjecture: lim a(n)/2^n = infinity. (Note that this is weaker than lim_inf a(n)^(1/n) > 2.)

Does lim a(n)^(1/n) exist?

A259545 provides the values of N such that all k>=N can be the greatest element of a different average set of n elements.

A set of different average with n elements has A001405(n) ~ 2^n * sqrt(2/(Pi*n)) subsets of size floor(n/2) which must have different sums, so the largest such sum is at least A001405(n), and thus the largest element is at least A001405(n)*2/n. This shows that lim inf a(n)^(1/n) >= 2. - Robert Israel, Aug 02 2015

a(10) <= 1303, as shown by the example {1, 43, 151, 235, 421, 981, 1093, 1161, 1266, 1303}. - Robert Israel, Jan 20 2016

a(10) <= 1252, as shown by the example {1, 76, 181, 211, 293, 727, 1126, 1196, 1216, 1252}. - Robert Israel, Jan 25 2016

Changing this sequence's requirement of "distinct arithmetic means" to "distinct sums" gives sequence A276661. - Jon E. Schoenfield, Nov 05 2016

a(n) <= A066720(n) and a(n+1) >= a(n) + 1