Search: id:A007600
Results 1-1 of 1 results found.

%I A007600 M0456
%S A007600 0,2,3,4,5,5,6,6,6,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,10,10,10,10,10,
%T A007600 10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
%U A007600 12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12
%N A007600 Minimal number of subsets in a separating family for a set of n elements.
%C A007600 Let j = ceil(log3(n))-1. Then a(n) = 3j+1 if 3^j < n <= 4*3^(j-1); 3j+2 
               if 4*3^(j-1) < n <= 2*3^j; 3j+3 if 2*3^j < n <= 3^(j+1). - Ralf Stephan, 
               Apr 28 2003
%C A007600 "In 1973, The Hungarian mathematician G. O. H. Katona posed the general 
               problem of determining, for a set of n elements, the minimum number 
               f(n) of subsets in a separating family. This problem was solved in 
               early Feb, 1982, by the gifted Chinese mathematician Cai Mao-Cheng 
               (Academia Sinica, Peking), during an extended visit to the University 
               of Waterloo." [Honsberger]
%C A007600 Honsberger gives a misattribution: the problem was first solved by Andrew 
               Chi-Chih Yao. - Vince Vatter (vince(AT)mcs.st-and.ac.uk), Apr 24 
               2006
%C A007600 A007600(A000792(n)) = n; Andrew Chi-Chih Yao attributes this observation 
               to D. E. Muller. - Vince Vatter (vince(AT)mcs.st-and.ac.uk), Apr 
               24 2006
%D A007600 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. 
               Computer Sci., 307 (2003), 3-29.
%D A007600 Ross Honsberger, Mathematical Gems III, Dolciani Mathematical Expositions 
               No. 9, Mathematical Association of America, 1985, Cai Mao-Cheng's 
               Solution to Katona's Problem on Families of Separating Subsets, Chapter 
               18, pages 224 - 239.
%D A007600 M-C. Cai, Solutions to Edmonds' and Katona's problems on families of 
               separating sets, Discrete Math., 47 (1983) 13-21.
%D A007600 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A007600 A. C.-C. Yao, On a problem of Katona on minimal separating systems, Discrete 
               Math., 15 (1976), 193-199.
%H A007600 J.-P. Allouche and J. Shallit, <a href="http://www.lri.fr/~allouche/kreg2.ps">
               The Ring of k-regular Sequences, II</a>
%H A007600 Gyula O. H. Katona, <a href="http://www.renyi.hu/~ohkatona/">Home page</
               a>.
%H A007600 J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Talks/kreg7.ps">
               k-regular Sequences</a>
%H A007600 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               KatonasProblem.html">Link to a section of The World of Mathematics.</
               a>
%H A007600 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               SeparatingFamily.html">Link to a section of The World of Mathematics.</
               a>
%F A007600 a(n) = min{2p + 3 ceiling(log_3(n/2^p)) | p=0, 1, 2 }.
%t A007600 f[n_] := Min[ Table[2p + 3Ceiling[Log[3, n/2^p]], {p, 0, 2}]]; Table[ 
               f[n], {n, 80}] (from Robert G. Wilson v Jan 15 2005)
%Y A007600 Positions of increases are in A007601.
%Y A007600 Sequence in context: A091334 A025280 A096365 this_sequence A091333 A005245 
               A061373
%Y A007600 Adjacent sequences: A007597 A007598 A007599 this_sequence A007601 A007602 
               A007603
%K A007600 nonn,easy,nice
%O A007600 1,2
%A A007600 N. J. A. Sloane (njas(AT)research.att.com), Robert G. Wilson v (rgwv(AT)rgwv.com), 
               Mira Bernstein (mira(AT)math.berkeley.edu)

Search completed in 0.001 seconds