%I M0456 #54 Jan 21 2023 02:25:36
%S 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 10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
%U 12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12
%N Minimal number of subsets in a separating family for a set of n elements.
%C Let j = ceiling(log_3(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 "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 Honsberger gives a misattribution: the problem was first solved by Andrew Chi-Chih Yao. - _Vincent Vatter_, Apr 24 2006
%D 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>, preprint, 2003.
%H J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H M-C. Cai, <a href="https://doi.org/10.1016/0012-365X(83)90068-7">Solutions to Edmonds' and Katona's problems on families of separating sets</a>, Discrete Math., 47 (1983) 13-21.
%H Gyula O. H. Katona, <a href="http://www.renyi.hu/~ohkatona/">Home page</a>.
%H Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Talks/kreg7.ps">k-regular Sequences</a>, Colloque Mendès-France, Bordeaux 12 September 2000.
%H Vincent Vatter, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.118.05.418">Maximal independent sets and separating covers</a>, Amer. Math. Monthly, 118 (2011), 418-423. [_N. J. A. Sloane_, May 05 2011]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KatonasProblem.html">Katona's Problem</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SeparatingFamily.html">Separating Family</a>.
%H A. C.-C. Yao, <a href="https://doi.org/10.1016/0012-365X(76)90085-6">On a problem of Katona on minimal separating systems</a>, Discrete Math., 15 (1976), 193-199.
%F a(n) = Min_{k=0..2} 2*k + 3*ceiling(log_3(n/2^k)).
%F a(A000792(n)) = n, for n>1; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - _Vincent Vatter_, Apr 24 2006
%F a(n) = ceiling(3*log_3(n)) if n belongs to A000792. - _Mehmet Sarraç_, Dec 17 2022
%p for n from 1 to 5 do C[n]:=n; od; C[6]:=5;
%p for i from 2 to 5 do
%p for m from 2*3^(i-1)+1 to 3^i do C[m]:=3*i; od:
%p for m from 3^i+1 to 4*3^(i-1) do C[m]:=3*i+1; od:
%p for m from 4*3^(i-1)+1 to 2*3^i do C[m]:=3*i+2; od:
%p od:
%p [seq(C[i],i=1..120)]; # _N. J. A. Sloane_, May 05 2011
%t f[n_] := Min[ Table[2p + 3Ceiling[Log[3, n/2^p]], {p, 0, 2}]]; Table[ f[n], {n, 80}] (* _Robert G. Wilson v_, Jan 15 2005 *)
%o (PARI) a(n) = vecmin(vector(3, i, my(k=i-1); 2*k + 3*ceil(log(n/2^k)/log(3)))); \\ _Michel Marcus_, Dec 18 2022
%Y Positions of increases are in A007601. This is a left inverse of A000792.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_, _Robert G. Wilson v_, and _Mira Bernstein_