# Splitting the integers 1 to 36

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?

• This talk by Peter Wrinkler at Gathering for Gardner is the origin of this problem: youtube.com/watch?v=RQtCRpWvVuw&t=397s Apr 28, 2022 at 23:09
• Can B be empty? May 4, 2022 at 8:59

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\}$$.

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.