A174541 Baron Münchhausen's Sequence.

0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1

Offset: 1

Author

Tanya Khovanova, Konstantin Knop, and Alexey Radul, Mar 21 2010

Keywords

• nonn
• nice
• changed

Comments

Let n coins weighing 1, 2, ..., n grams be given. Suppose Baron Münchhausen knows which coin weighs how much, but his audience does not. Then a(n) is the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.

After a(1) = 0, a(n) is either 1 or 2 for all n.

a(n) = 1 for n triangular, n triangular-plus-one, T_n a square, and T_n a square-plus-one, where T_n is the n-th triangular number; a(n) = 2 for all other n > 1.

Examples

			a(7) = 1 because the weighing 1 + 2 + 3 < 7 conclusively demonstrates the weight of the seven-gram coin.
		

Links

• M. Brand, Tightening the bounds on the Baron's Omni-sequence, Discrete Math., 312 (2012), 1326-1335.
• Tanya Khovanova, Konstantin Knop and A. Radul, Baron Münchhausen's Sequence, arXiv:1003.3406 [math.CO], 2010.
• Tanya Khovanova, Konstantin Knop, and A. Radul, Baron Münchhausen's Sequence, J. Int. Seq. 13 (2010) # 10.8.7.
• Tanya Khovanova and A. Radul, Another Coins Sequence

Crossrefs

Cf. A000217, A000124, A001108, A072221, A186313.

Programs

Mathematica

triangularQ[n_] := IntegerQ[ Sqrt[8n+1]]; a[1] = 0; a[n_ /; triangularQ[n] || triangularQ[n-1] || IntegerQ[ Sqrt[n*(n+1)/2]] || IntegerQ[ Sqrt[n*(n+1)/2 - 1]]] = 1; a[] = 2; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover, Jul 30 2012, after comments *)

Scheme

;;; The following Scheme program generates terms of Baron
;;; Münchhausen's Sequence.
(define (acceptable? n)
  (or (triangle? n)
      (= n 2)
      (triangle? (- n 1))
      (square? (triangle n))
      (square? (- (triangle n) 1))))
(stream-map
 (lambda (n)
   (if (= n 1)
       0
       (if (acceptable? n)
           1
           2)))
 (the-integers))