Find six different numbers (positive integers) such that each of them has a common divisor with precisely three of the other numbers. How small can the largest of the six numbers be?
What if $2n$, $n>3$, numbers need to be found, each having a common divisor with precisely three of the other numbers?
I think I can get the largest number as small as
33
like so:
Method:
I tried different graph configurations for the six numbers, and the one with two triangles seemed to be very efficient in terms of the number of distinct prime factors required. So half the numbers got a factor of 2, the other half a 3. Then, I used the three next smallest primes to connect the triangle points pairwise to add the third number with a shared factor everywhere.
To generalise the method for any 2n numbers with n connections each, two fully connected groups of n plus a pairwise connection between the groups seems quite efficient, so that the maximum number is no bigger than
three times the (n+2)th prime
but I wouldn't be surprised if some particular n would offer more efficient graph possibilities.
OP edited the question to clarify that in the general case, there should always be 3 non-coprime "neighbours", not n.
This seems like it could be a harder problem, judging from how for 8 numbers, the maximum number can actually be smaller than for 6 numbers:
2,4,8,16 (all even and powers of 2)
3,9,15,21 (all odd and divisible by 3)
Here's my best attempt at showing that it really is tricky:
For even n (n=2k), the number of numbers (2n) is divisible by 4, so the best strategy seems to be to group the numbers in bunches of 4, and to assign the smallest available primes as the common factors for each group. The group that got the largest one (the kth prime, $p_k$) is then the limiting one: it cannot use any smaller factors to distinguish between its members, so the optimal composition of that group is $p_k, {p_{k}}^2, p_kp_{k+1}$ and $p_kp_{k+2}$.
The problem with this approach is that it's unclear if there are always enough prime factors to fit all the other groups into the numbers below $p_kp_{k+2}$, without using any of the factors used by the final group. It definitely works for smaller k, but as primes get larger, the smallest possible ratio between two consecutive primes gets arbitrarily small (Yitang Zhang, 2013), so it's not sensible to assume this result will hold for every k.
Via integer linear programming (with a binary decision variable for each positive integer up to a specified bound), I found optimal solutions for $2n\in\{6,8,\dots,24\}$: \begin{matrix} 2n & \text{solution} \\ \hline 6 & \{14,15,20,21,22,33\} \\ 8 & \{2,3,4,8,9,15,16,21\} \\ 10 & \{5,25,26,34,35,38,39,51,55,57\} \\ 12 & \{3,5,9,16,25,27,34,35,38,39,46,55\} \\ 14 & \{5,7,25,49,58,62,69,77,85,87,91,92,93,95\} \\ 16 & \{2,3,5,7,8,9,25,32,49,58,69,77,81,85,91,95\} \\ 18 & \{2,7,8,11,32,49,87,93,111,121,133,142,143,145,155,161,185,187\} \\ 20 & \{2,4,5,7,9,11,16,25,27,49,58,111,121,123,125,133,143,155,161,187\} \\ 22 & \{3,5,9,49,82,106,125,164,177,187,203,209,212,215,217,219,221,235,247,253,259,299\} \\ 24 & \{5,7,9,11,13,49,94,118,121,123,125,169,183,201,215,217,221,236,247,253,259,265,278,319 \} \end{matrix}
By request, here's the SAS code I used:
proc optmodel;
num n = 3;
num m = 50;
set NODES = 1..m;
set EDGES = {i in NODES, j in NODES: i < j and gcd(i,j) > 1};
var UseNode {NODES} binary;
var UseEdge {EDGES} >= 0 <= 1;
min Objective = max {i in NODES} i * UseNode[i];
/* var MinMax;*/
/* min Objective = MinMax;*/
/* con MinMaxCon {i in NODES}:*/
/* MinMax >= i * UseNode[i];*/
con Cardinality:
sum {i in NODES} UseNode[i] = 2*n;
con DegreeThree {k in NODES}:
sum {<i,j> in EDGES: k in {i,j}} UseEdge[i,j] = 3 * UseNode[k];
con NodesImplyEdge {<i,j> in EDGES}:
UseNode[i] + UseNode[j] - 1 <= UseEdge[i,j];
solve linearize;
print UseNode;
quit;
If your solver doesn't support automatic linearization, you can instead use the commented code to manually linearize the min-max objective.
I can do better than Daniel S's answer.
We can split the six numbers into
two triples, each triple pairwise noncoprime, each number noncoprime with exactly one number in the other triple.
The most efficient way of doing this would seem to be
$2\cdot5,2\cdot7,2\cdot11$
$3\cdot5,3\cdot7,3\cdot11$
with the largest of the six numbers being
33.
To find $2n$ distinct numbers such that each one is noncoprime with exactly $n$ of the other numbers,
do the same thing but with $n$-tuples instead of triples.
They would be, optimally,
$2p_3,2p_4,2p_5,\cdots,2p_{n-2}$
$3p_3,3p_4,3p_5,\cdots,3p_{n-2}$
where $p_n$ denotes the $n$th prime number, so the largest among them would be
$3p_{n-2}$. (In the case $n=3$, that gave $33$.)
To find $2n$ distinct numbers such that each one is noncoprime with exactly three of the other numbers, we probably need to split into cases according to $n$ modulo $3$. I've found some possibilities but I'm not sure if they're optimal ...
If $n=3k$, then we can
do the same thing as above but with pairs of triples:
$2p_{2k+1},2p_{2k+2},2p_{2k+3}$ and $3p_{2k+1},3p_{2k+2},3p_{2k+3}$
$5p_{2k+4},5p_{2k+5},5p_{2k+6}$ and $7p_{2k+4},7p_{2k+5},7p_{2k+6}$
$\cdots$
$p_{2k-1}p_{2k+(3k-2)},p_{2k-1}p_{2k+(3k-1)},p_{2k-1}p_{2k+(3k)}$ and $p_{2k}p_{2k+(3k-2)},p_{2k}p_{2k+(3k-1)},p_{2k}p_{2k+(3k)}$
giving the answer as
$p_{2k}p_{5k}$. (In the case $n=3$, that gave $p_2p_5=33$.)
If $n=3k+2$, then we can
do the same thing as above but with pairs of triples and one extra isolated quadruple:
$2,4,8,16$
$3p_{2k+1},3p_{2k+2},3p_{2k+3}$ and $5p_{2k+1},5p_{2k+2},5p_{2k+3}$
$7p_{2k+4},7p_{2k+5},7p_{2k+6}$ and $11p_{2k+4},11p_{2k+5},11p_{2k+6}$
$\cdots$
$p_{2k}p_{2k+(3k-2)},p_{2k}p_{2k+(3k-1)},p_{2k}p_{2k+(3k)}$ and $p_{2k+1}p_{2k+(3k-2)},p_{2k+1}p_{2k+(3k-1)},p_{2k+1}p_{2k+(3k)}$
giving the answer as
$p_{2k+1}p_{5k}$.
My first instinct for a construction is
To use products of primes $p_1p_2p_3$, $p_1p_4p_5$, $p_4p_6p_7$, $p_2p_6p_8$, $p_5p_8p_9$, $p_3p_7p_9$
The smallest such construction of this form would have
$\{p_1,\ldots,p_9\}=\{2,3,5,7,11,13,17,19,23\}$ of which I think the smallest-largest number would be 7935 (haven't checked this part).
A generalisation of this to $2n$ numbers would have
Triples of primes $p_i,p_{i+1\mod{2n}},p_{i\mod n+2n}$ for $i=0,\ldots,2n$
