login
a(n) = ceiling( log_3( binomial(n,2) ) ).
0

%I #16 Sep 08 2022 08:46:13

%S 0,1,2,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,

%T 6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,

%U 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9

%N a(n) = ceiling( log_3( binomial(n,2) ) ).

%C A lower bound on the number of weighings which suffice to determine the counterfeit (heavier) coins in a set of n coins given a balance scale and the information that there are exactly two heavier coins present.

%C Records occur at n=2, 3, 4, 5, 8, 14, 23, 39, 67, 116, 199, 345, 596,...

%H Anping Li, <a href="http://dx.doi.org/10.1016/0097-3165(94)90052-3">Three counterfeit coins problem</a>, J. Comb. Theory A 66 (1994) 93-101 eq. (3).

%H Anping Li, <a href="http://dx.doi.org/10.1016/0012-365X(94)90038-8">On the conjecture at two counterfeit coins</a>, Discr. Math. 133 (1-3) (1994) 301-306

%H Wen An Liu, Qi Min Zhang, Zan Kan Nie, <a href="http://dx.doi.org/10.1016/j.jspi.2005.06.008">Optimal search procedure on coin-weighing problem</a>, J. Statl. Plan. Inf. 136 (2006) 4419-4435.

%H R. Tosic, <a href="http://dx.doi.org/10.1016/0012-365X(83)90123-1">Two counterfeit coins</a>, Discr. Math. 46 (3) (1993) 295-298, eq. (2).

%p seq(ceil(log[3](binomial(n,2))),n=2..120) ;

%t Ceiling[Log[3,Binomial[Range[2,120],2]]] (* _Harvey P. Dale_, Dec 13 2016 *)

%o (PARI) first(m)=vector(m,i,i++;ceil(log(binomial(i,2))/log(3))) \\ _Anders Hellström_, Sep 10 2015

%o (Magma) [Ceiling(Log(3,Binomial(n,2))): n in [2..120]]; // _Bruno Berselli_, Sep 10 2015

%Y Cf. A080342 (single counterfeit coin).

%K nonn,easy

%O 2,3

%A _R. J. Mathar_, Sep 10 2015