cp's OEIS Frontend

A259545 Minimum number k such that, for every m >= k, there exists a set of n positive integers whose largest element is m and whose subsets all have distinct arithmetic means.

%I A259545 #42 Mar 15 2019 14:48:52
%S A259545 1,2,4,7,16,34,78,178
%N A259545 Minimum number k such that, for every m >= k, there exists a set of n positive integers whose largest element is m and whose subsets all have distinct arithmetic means.
%C A259545 Let a set of integers be called "of different average" if it satisfies that the arithmetic mean of any two different subsets of it is different (the empty set ignored). 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.
%C A259545 In order for a set to be of different average it is obvious that all its elements have to 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. We have by definition a(n)>=A259544(n).
%C A259545 If we already have a different average sequence of (n-1) terms: 1<a_2<...<a_(n-1) and add a term a_n satisfying: (i) The average of any set including a_n is greater than a_(n-1) and (ii) If two sets include a_n, the one having more elements will have a lower average, then any a_n greater than this particular a_n will also satisfy these properties and therefore it provides an upper bound for a(n). It can be easily proved that, by constructing the bound for a(n) recursively this way, the resulting sequence is Sum_{j=1..n-1} j!.
%C A259545 But a much better upper bound can be found by considering the upper bound for A259544(n-1). This is 4^(n-2), and indeed the bound 4^(k-1), for 1<=k<=n-1, applies to all the terms of the sequence. Therefore a different average sequence of n-1 elements exists in which 1=a_1=4^0, a_2<4^1, a3<4_2, etc., until a_(n-1)<4^(n-2). We see that, for this sequence, condition (ii) is more restrictive than (i), in the worst possible scenario for both, and it provides the bound: a(n) < (n-1)4^(n-1)/3, n>=3.
%C A259545 Conjecture: a(n)=A259544(n) only for a finite number of n. Supposing this to be true, what is the order of growth of a(n)-A259544(n)?
%C A259545 Conjecture: lim_{n->inf} a(n)/A259544(n)=1, and indeed the bound <4^(n-1), n>1, is also valid for a(n).
%C A259545 Conjecture: a(n) < A259544(n+1). (This seems obvious, but lacks a proof.)
%H A259545 Javier Múgica, <a href="/A259545/a259545.txt">different average sets up to 219</a> from where the values of this sequence up to the 8th were obtained (there are much more different average sets.)
%Y A259545 Cf. A259544.
%K A259545 nonn,more,hard
%O A259545 1,2
%A A259545 _Javier Múgica_, Jun 30 2015