

A007600


Minimal number of subsets in a separating family for a set of n elements.
(Formerly M0456)


2



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, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Let j = ceil(log3(n))1. Then a(n) = 3j+1 if 3^j < n <= 4*3^(j1); 3j+2 if 4*3^(j1) < n <= 2*3^j; 3j+3 if 2*3^j < n <= 3^(j+1).  Ralf Stephan, Apr 28 2003
"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 MaoCheng (Academia Sinica, Peking), during an extended visit to the University of Waterloo." [Honsberger]
Honsberger gives a misattribution: the problem was first solved by Andrew ChiChih Yao.  Vincent Vatter, Apr 24 2006
a(A000792(n)) = n; Andrew ChiChih Yao attributes this observation to D. E. Muller.  Vincent Vatter, Apr 24 2006


REFERENCES

J.P. Allouche and J. Shallit, The ring of kregular sequences, II, Theoret. Computer Sci., 307 (2003), 329.
MC. Cai, Solutions to Edmonds' and Katona's problems on families of separating sets, Discrete Math., 47 (1983) 1321.
Ross Honsberger, Mathematical Gems III, Dolciani Mathematical Expositions No. 9, Mathematical Association of America, 1985, Cai MaoCheng's Solution to Katona's Problem on Families of Separating Subsets, Chapter 18, pages 224  239.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
V. Vatter, Maximal independent sets and separating covers, Amer. Math. Monthly, 118 (2011), 418423. [From N. J. A. Sloane, May 05 2011]
A. C.C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193199.


LINKS

Table of n, a(n) for n=1..78.
J.P. Allouche and J. Shallit, The Ring of kregular Sequences, II
Gyula O. H. Katona, Home page.
J. Shallit, kregular Sequences
Eric Weisstein's World of Mathematics, Katona's Problem.
Eric Weisstein's World of Mathematics, Separating Family.


FORMULA

a(n) = min{2p + 3 ceiling(log_3(n/2^p))  p=0, 1, 2 }.


MAPLE

for n from 1 to 5 do C[n]:=n; od; C[6]:=5;
for i from 2 to 5 do
for m from 2*3^(i1)+1 to 3^i do C[m]:=3*i; od:
for m from 3^i+1 to 4*3^(i1) do C[m]:=3*i+1; od:
for m from 4*3^(i1)+1 to 2*3^i do C[m]:=3*i+2; od:
od:
[seq(C[i], i=1..120)]; # N. J. A. Sloane, May 05 2011


MATHEMATICA

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 *)


CROSSREFS

Positions of increases are in A007601. This is a left inverse of A000792.
Sequence in context: A096365 A319412 A200311 * A195872 A091333 A293771
Adjacent sequences: A007597 A007598 A007599 * A007601 A007602 A007603


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane, Robert G. Wilson v, Mira Bernstein


STATUS

approved



