6
$\begingroup$

Split the integers 1 to 36 into two sets, A and B, such that any number in set A has a common divisor greater than 1 with no more than two other numbers in A, but for every number in B there are at least three numbers in A with which it has a common divisor.

How large can set A be?

In general, for which N is such a splitting of the integers 1 to N possible?

$\endgroup$
2

2 Answers 2

7
$\begingroup$

Via integer linear programming, the largest $|A|$ is

$17$, attained by $A=\{1,2,3,5,7,9,11,13,16,17,19,23,25,27,29,31,32\}$

and the smallest $|A|$ is

$14$, attained by $A=\{1,5,7,11,12,13,17,18,19,23,25,29,31,36\}$.

$\endgroup$
2
$\begingroup$

If B can be empty, using this strategy would get us this partition

$A$ includes 1, all prime numbers <= $N$ and largest 2 exponents for each prime <= $N$

Examples

$ N = 1, A = \{1\}$
$ N = 2, A = \{1, 2\}$
$ N = 3, A = \{1, 2, 3\}$
$ N = 4, A = \{1, 2, 3, 4\}$
$ N = 5, A = \{1, 2, 3, 4, 5\}$
$ N = 6, A = \{1, 2, 3, 4, 5\}$
$ N = 7, A = \{1, 2, 3, 4, 5, 7\}$
$ N = 8, A = \{1, 2, 3, 4, 5, 7, 8\}$
$ N = 9, A = \{1, 2, 3, 4, 5, 7, 8, 9\}$
$ N = 10, A = \{1, 2, 3, 4, 5, 7, 8, 9\}$
$ N = 11, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11\}$
$ N = 12, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11\}$
$ N = 13, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 14, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 15, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 16, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16\}$
$ N = 17, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17\}$
$ N = 18, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17\}$
$ N = 19, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 20, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 21, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 22, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 23, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23\}$
$ N = 24, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23\}$
$ N = 25, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25\}$
$ N = 26, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25\}$
$ N = 27, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27\}$
$ N = 28, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27\}$
$ N = 29, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29\}$
$ N = 30, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29\}$
$ N = 31, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31\}$
$ N = 32, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 33, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 34, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 35, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 36, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 37, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$
$ N = 38, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$
$ N = 39, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$

I verified this with a program for about 10**5 and it looked satisfiable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.