login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080342 Number of weighings required to identify a single bad coin out of n coins, using a two-pan balance. 4
0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

It is known that there is exactly one bad coin, which is heavier than the others. No weights are used in the weighings.

0 appears once, 1 twice, 2 6 times, 3 18 times, 4 54 times, ... which is the same as the number of base-3 numbers of length n; see A007089. - Jonathan Vos Post, Apr 20 2011

Records appear at positions 3^n+1 (=A034472(n)). - Robert G. Wilson v, Aug 06 2012

The "Heavy Marble" section of "Brainteaser Problems" in the Mongan et al. reference describes the n = 8 case in detail and then derives the general formula given below. Of course this sequence applies also when the single, unlike object is lighter than all the others. If the unlike object is only known to have a different weight (that is, to be lighter than all the others or heavier than all the others), use A064099. - Rick L. Shepherd, Sep 05 2013

If it is unknown whether the bad coin is heavier or lighter, then the minimum number of weighings is A029837(n) and the number of coins that must be used in the first weighing is A004526(n), for n > 2. - Ivan N. Ianakiev, Apr 13 2017

REFERENCES

J. Mongan, N. Suojanen, and E. Giguère, Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition, Wiley Publishing, Inc., 2007, pp. 169-172.

LINKS

Rick L. Shepherd, Table of n, a(n) for n = 1..10000

R. K. Guy, R. J. Nowakowski, Coin-weighing problems, Am. Math. Monthly 102 (2) (1995) 164-167.

B. Manvel, Counterfeit coin problems, Math. Mag. 50 (2) (1977) 90-92, theorem 1.

FORMULA

a(n) = floor(L) - floor(2^(-f(L))) + 1, where L = log_3(n) and f() = fractional part.

a(n) = ceiling(log_3(n)). - Rick L. Shepherd, Sep 05 2013

A064235(n) = 3 ^ a(n). - Reinhard Zumkeller, Sep 02 2015

EXAMPLE

a(1) = 0 since no weighings are needed - the coin is bad. a(2) = 1 since one weighing is needed.

MATHEMATICA

f[n_] := Floor[ Log[3, n]] - Floor[2^-FractionalPart[ Log[3, n]]] + 1; Array[f, 105] (* Robert G. Wilson v, Aug 05 2012 *)

PROG

(PARI) a(n) = ceil(log(n)/log(3)) \\ Rick L. Shepherd, Sep 05 2013

(Haskell)

import Data.List (transpose)

a080342 n = genericIndex a080342_list (n - 1)

a080342_list = 0 : zs where

   zs = 1 : 1 : (map (+ 1) $ concat $ transpose [zs, zs, zs])

-- Reinhard Zumkeller, Sep 02 2015

CROSSREFS

Cf. A000244, A007089, A025192, A064235.

Cf. also A004526, A029837, A064099.

Sequence in context: A211664 A182434 A185679 * A081604 A123119 A099396

Adjacent sequences:  A080339 A080340 A080341 * A080343 A080344 A080345

KEYWORD

nonn,easy

AUTHOR

Artemario Tadeu Medeiros da Silva (artemario(AT)uol.com.br), Mar 19 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 17:18 EST 2019. Contains 329879 sequences. (Running on oeis4.)