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

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

Offset

1,2

Comments

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

"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

References

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

Links

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

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

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.

Gyula O. H. Katona, Home page.

Jeffrey Shallit, k-regular Sequences, Colloque Mendès-France, Bordeaux 12 September 2000.

Vincent Vatter, Maximal independent sets and separating covers, Amer. Math. Monthly, 118 (2011), 418-423. [N. J. A. Sloane, May 05 2011]

Eric Weisstein's World of Mathematics, Katona's Problem.

Eric Weisstein's World of Mathematics, Separating Family.

A. C.-C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193-199.

Formula

a(n) = Min_{k=0..2} 2*k + 3*ceiling(log_3(n/2^k)).

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

a(n) = ceiling(3*log_3(n)) if n belongs to A000792. - Mehmet Sarraç, Dec 17 2022

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

Prog

(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

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, and Mira Bernstein

Status

approved