login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A280432 Maximum size of a set whose integrity can be checked with n weighings. 0
2, 4, 10, 30, 114, 454 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

This sequence arises in the following problem: Given a set of binary elements (e.g., coins that may have one of the two weights), determine whether all of them are the same by weighing equally sized non-overlapping subsets n times. a(n) is the maximum size of a set whose integrity can be checked with n weighings.

The next terms are probably a(7) = 2234 and a(8) = 9966 (from the Kozlov/Vu reference). - Konstantin Knop, Oct 18 2017

((3^n-1)/2)*(n+1)*n^((n-1)/2) >= a(n) >= 2^((1/2)*n*log(n)-n*(2+o(1))) [Alon&Vu]. - Andrey Zabolotskiy, Oct 23 2017

LINKS

Table of n, a(n) for n=1..6.

Noga Alon, Dmitry N. Kozlov, Coins with Arbitrary Weights, Journal of Algorithms, Volume 25, Issue 1, October 1997, Pages 162-176.

Noga Alon, Van H. Vu, Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs, Journal of Combinatorial Theory, Series A, Volume 79, Issue 1, July 1997, Pages 133-160.

IBM Research, Ponder This December 2016 challenge

IBM Research, Solutions for n=4 and 5

Dmitry N. Kozlov, Van H. Vu, Coins and Cones, Journal of Combinatorial Theory, Series A, Volume 78, Issue 1, April 1997, Pages 1-14 [gives lower bounds for a(n) up to n=15].

CROSSREFS

Sequence in context: A173940 A101901 A124384 * A001647 A007177 A328815

Adjacent sequences:  A280429 A280430 A280431 * A280433 A280434 A280435

KEYWORD

nonn,more,hard

AUTHOR

Serge Batalov, Jan 02 2017

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 January 27 14:39 EST 2020. Contains 331295 sequences. (Running on oeis4.)