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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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^(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

"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]

Honsberger gives a misattribution: the problem was first solved by Andrew Chi-Chih Yao. - Vincent Vatter, Apr 24 2006

a(A000792(n)) = n; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - Vincent Vatter, Apr 24 2006

REFERENCES

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

M-C. Cai, Solutions to Edmonds' and Katona's problems on families of separating sets, Discrete Math., 47 (1983) 13-21.

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.

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), 418-423. [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), 193-199.

LINKS

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

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II

Gyula O. H. Katona, Home page.

J. Shallit, k-regular 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^(i-1)+1 to 3^i do C[m]:=3*i; od:

   for m from 3^i+1 to 4*3^(i-1) do C[m]:=3*i+1; od:

   for m from 4*3^(i-1)+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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 08:42 EDT 2018. Contains 316405 sequences. (Running on oeis4.)