5
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ In the generalisation, would each number have a common divisor with precisely 3 of the others or with precisely $n$ of the others? $\endgroup$ Apr 16, 2022 at 18:02
  • 1
    $\begingroup$ With 3 of the others. $\endgroup$ Apr 16, 2022 at 18:20
  • $\begingroup$ Do you have a particular solution in mind for the general case? Seems like it might depend on the distribution of prime numbers on the number line, making any solution somewhat tricky to prove as optimal. $\endgroup$
    – Bass
    Apr 16, 2022 at 19:09
  • $\begingroup$ I was assuming wrongly that the underlying graph would normally be a connected cubic graph and wondered what shape such graph with the least largest vertex had. Would still like to know if this be required, i.e., that the underlying graph is cubic and connected. $\endgroup$ Apr 17, 2022 at 0:42
  • 2
    $\begingroup$ Cubic is part of the definition, but the example for $2n=8$ shows that an optimal solution need not be connected. $\endgroup$
    – RobPratt
    Apr 17, 2022 at 0:46

4 Answers 4

10
$\begingroup$

I think I can get the largest number as small as

33

like so:

10, 14, 15, 21, 22, 33

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.

$\endgroup$
3
  • $\begingroup$ In the general case, so you decide on the base prime for each group first, then complete each group with the next available prime number, and this causes issue in that if we want to force last group to use $p_kp_{k+2}$, the smaller groups might have a number bigger than $p_kp_{k+2}$? So it's not about finding a set of numbers which satisfies the conditions that is hard (since we can always find one with this algorithm), but generalizing that the largest number is $p_kp_{k+2}$ (it could be another number from the smaller groups), right? $\endgroup$
    – justhalf
    Apr 21, 2022 at 5:19
  • $\begingroup$ If that's the case, looking at the optimal number in RobPratt's answer, it seems that for 2n=16 indeed $p_kp_{k+2}$ is already not the largest number. $\endgroup$
    – justhalf
    Apr 21, 2022 at 5:26
  • 1
    $\begingroup$ @justhalf Yes, I think you got my meaning perfectly. The simple solution won't work, except when it does. This means that the only way to reach a solution in the general case is to optimally package the available primes so that the biggest number becomes as small as possible, and this doesn't seem to be a problem with a (simply stated non-brute-force) solution. -> "It is tricky". $\endgroup$
    – Bass
    Apr 21, 2022 at 11:34
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Could you post your code please? $\endgroup$
    – Dr Xorile
    Apr 20, 2022 at 23:33
  • $\begingroup$ In 2n=12 case, {16, 34, 38, 46} can be replaced by {2, 4, 8, 16}, right? (not that it changes the highest number, but just to confirm) $\endgroup$
    – justhalf
    Apr 21, 2022 at 5:25
  • $\begingroup$ @justhalf Yes, and the resulting set $\{2,3,4,5,8,9,16,25,27,35,39,55\}$ turns out to minimize the sum. $\endgroup$
    – RobPratt
    Apr 21, 2022 at 16:04
5
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Each number must be noncoprime to precisely three other of the numbers. $\endgroup$ Apr 16, 2022 at 18:18
  • $\begingroup$ @Bernardo OK, then I've done it (I think) for two of the three possible cases of $n$ modulo 3. Not sure about the third case. $\endgroup$ Apr 16, 2022 at 19:00
  • 1
    $\begingroup$ Applauds; doffs cap $\endgroup$
    – Daniel S
    Apr 16, 2022 at 19:39
  • $\begingroup$ Trying the formula for n=3k for the first relevant case (k=2) gives $p_4\times p_{10}=7\times29=203$. However, 55 is enough for 12 numbers, with 2,4,8,16,3,9,27,39,5,25,35,55. $\endgroup$
    – Bass
    Apr 16, 2022 at 20:41
  • 1
    $\begingroup$ If we want to minimize the largest number, wouldn't it be better to reverse the order of the primes $p_2, p_3, \dots, p_{2k}$? For example, when $n=3k$, start with $\{p_{2k} p_{2k+1}, p_{2k} p_{2k+2}, p_{2k} p_{2k+3}, p_{2k-1} p_{2k+1}, p_{2k-1} p_{2k+2}, p_{2k-1} p_{2k+3}\}$ and end with $\{3p_{5k-2}, 3p_{5k-1}, 3p_{5k}, 2p_{5k-2}, 2p_{5k-1}, 2p_{5k}\}$? $\endgroup$ Apr 17, 2022 at 21:37
3
$\begingroup$

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$

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