A286874 -id:A286874 - cp's OEIS frontend

A303977 Number of inequivalent solutions to problem discussed in A286874.

1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 5, 2, 5, 2

Offset: 0

Zhao Hui Du, May 03 2018

If one solution can be transformed to another by reordering the bits, they are considered to be equivalent.

			List of inequivalent solutions (in hexadecimal format):
  0: {0}
  1: {0 1}
  2: {1 2}
  3: {1 2 4}
  4: {1 2 4 8}
  5: {1 2 4 8 10}
  6: {1 2 4 8 10 20}
  7: {1 2 4 8 10 20 40}
      {7 19 2a 34 4c 52 61}
  8: {1 2 4 8 10 20 40 80}
     {1 e 32 54 68 98 a4 c2}
     {3 d 31 54 68 98 a4 c1}
     {7 19 2a 4c 70 92 a4 c1}
  9: {7 19 2a 4c 70 92 a4 c1 114 121 142 188}
 10: {1 e 32 54 98 e0 124 148 182 228 242 284 310}
      {3 d 31 54 98 e0 124 148 181 228 241 284 310}
      {7 19 2a 34 4c 92 c1 121 142 184 250 2a0 308}
      {7 19 2a 34 4c 92 c1 121 142 188 250 2a0 304}
      {7 19 2a 4c 92 e0 121 150 184 234 241 288 302}
 11: {7 19 2a 34 4c 92 c1 121 142 184 250 2a0 308 460 488 510 601}
      {7 19 2a 34 4c 92 c1 121 142 188 250 2a0 304 460 484 510 601}
 12: {7 19 2a 34 4c 92 121 1c0 241 284 302 442 488 510 620 850 8a0 904 a08 c01}
      {7 19 2a 34 4c 92 121 1c0 241 284 302 442 488 510 620 860 881 908 a10 c04}
      {7 19 2a 34 4c 92 121 1c0 241 284 308 442 488 510 620 860 881 902 a10 c04}
      {7 19 2a 34 4c 92 121 1c0 241 284 308 442 4a0 504 610 850 881 902 a20 c08}
      {7 19 2a 34 4c 92 121 1c0 241 284 308 442 4a0 504 610 850 888 902 a20 c01}
 13: {7 19 2a 34 4c 92 121 1c0 241 284 302 442 488 510 620 850 8a0 904 a08 c01 1060 1081 1108 1210 1404 1802}
      {7 19 2a 34 4c 92 121 1c0 241 284 308 442 4a0 504 610 850 888 902 a20 c01 1060 1081 1110 1202 1408 1804}

Cf. A286874.

a(12) by Steinar H. Gunderson, Jul 08 2025

a(13) by Steinar H. Gunderson, Jul 17 2025

A054961 Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 13, 17

Offset: 0

N. J. A. Sloane, May 24 2000

Maximal number of subsets of an n-set such that the unions of any 2 distinct subsets are all distinct.
The concatenation of these vectors produces a 2-separable matrix.
It follows from the Erdős-Frankl-Füredi paper that a(n) grows exponentially with n.
a(9) >= 17. Here is a candidate solution: {011010001 001001010 101000110 100000001 000010110 110010100 010000011 000110000 001001101 010000100 110001000 000101100 100100010 001000000 010100101 111100000 000011001}. - Dmitry Kamenetsky, Jul 17 2017
a(10) >= 22. Here is a candidate solution: {1010110000 1110000000 0010011000 0110100001 1000010101 0011000101 1001000000 0000000010 0001110100 0001001000 0010101010 1100010010 0000010001 0000101101 0100010100 0000011110 0100101000 0001100011 0000100100 0101000001 0101000110 1010000011}. - Dmitry Kamenetsky, Jul 17 2017
a(11) >= 31. Here is a candidate solution: {00101010010 01100101000 00001101100 00001010101 00100110100 00101001001 01000100101 00010101001 10001100001 11010000010 01001001010 00000001111 01111000000 00110010001 10000111000 11100000001 10010000101 00011110000 01000011001 00100100011 01010010100 01000110010 10110100000 10101000100 11001010000 00011000110 10000010011 10000100110 10100001010 00010011010 00000000100}. - Dmitry Kamenetsky, Jul 21 2017
a(12) >= 46. Here is a candidate solution: {011000011000 000000001000 000110100001 111000000010 110100000100 000010110100 010100010010 000011000011 010001001010 000111001000 010000101100 001001100010 100010000110 000001010110 001010101000 010010100010 001001001001 101000100100 000001100101 100011100000 000100011100 001000010011 010100001001 101100001000 100110010000 001110000010 100001001100 010101100000 110001000001 110010001000 011000100001 001100110000 001000001110 000010001101 110000110000 000100100110 000010011010 101001010000 000101010001 001100000101 100000010101 000001111000 101010000001 100101000010 010000000111 010010010001}. - Dmitry Kamenetsky, Jul 21 2017
From Zhao Hui Du, Mar 30 2018: (Start)
Library "Nauty and Traces" is used to filter automorphism graph to verify a(9)=17.
a(13) to a(27) are >= 55,62,70,90,112,140,180,226,279,353,444,558,679,879,1059. (End)
a(13) to a(27) are >= 55,63,72,91,112,145,182,230,281,359,447,566,685,891,1065. - Zhao Hui Du, Apr 19 2018
1.134^n <= a(n) <= ceiling(2^((n+1/2))). The lower bound follows from Theorem 2 of the Erdős-Frankl-Füredi paper and the upper bound is because the union of any two vectors must be unique so a(n)*(a(n)-1)/2 <= 2^n. - Sarosh Adenwalla, May 25 2024

			Solutions for n=4..8:
{0000 0001 0010 0100 1000};
{00000 00001 00010 00100 01000 10000};
{000000 000011 001100 010101 011010 100110 101001 110000};
{0000000 0000011 0000101 0001001 0010010 0100100 0111000 1001000 1010100 1100010};
{00000000 00000011 00001100 00010101 00100110 00111000 01001001 01010010 01100000 10001010 10010000 10100001 11000100}.

Computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), Jud McCranie, David W. Wilson, May 24 2000. a(8) >= 13.

Background: D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2nd ed., 2000; see Chap. 7.
Asymptotic results: P. Erdos, P. Frankl and Z. Füredi, Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory, A33 (1982), 158-166.
Math Stack Exchange, Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints
Wikipedia, Disjunct Matrix

Cf. A054962 (number of solutions), A304041 (number of distinct solutions), A286874.

Cf. A290492 (3-separable), A361928.

a(8) from Giovanni Resta, Mar 30 2006

a(9) from Zhao Hui Du, Mar 30 2018

cp's OEIS Frontend

A303977 Number of inequivalent solutions to problem discussed in A286874.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions