cp's OEIS Frontend

Since A003022 is the most important sequence dealing with Golomb rulers, it seems best to define this sequence in terms of that one.

Original name was: Maximum label within a minimal labeling of 2 identical n-sided dice yielding the most possible sums. For example, two hexahedra labeled (1, 3, 8, 14, 17, 18) yield the 21 possible sums 2, 4, 6, 9, 11, 15, 16, 17, 18, 19, 20, 21, 22, 25, 26, 28, 31, 32, 34, 35, 36. No more sums can be obtained by different labelings, and no labeling with labels < 18 yields 21 possible sums. Therefore a(6) = 18.

Bounded above by A005282. - James Wilcox, Jul 27 2013

Minimum greatest integer in a set of n positive integers with all the differences between any two of its elements being different. - Javier Múgica, Jul 31 2015

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) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of triples (of not necessarily distinct elements) of which are distinct.

a(11) = 445 or a(11) < 440, but disproving the latter will take many cpu-years with the given program. - John Tromp, Aug 28 2013