A partition of 186 into five parts under divisibility constraints

Question

The sum of 5 positive natural numbers, not necessarily distinct, is 186. If placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and only if they have a common divisor greater than 1 (that is, they are not relatively prime).

What, in non-decreasing order, are those 5 numbers? The answer is unique.

Answer 1

In order for the edges to exist for the square the way that they do, it must be that the numbers in the square are of the form $ab,ac,bd,cd$ for distinct primes $a,b,c,d$ with possible extra powers or terms being multiplied. Further, in order for the total sum to be even and the singleton to not share any edges with the square, none of $a,b,c,d$ may be equal to $2$. This is because if one of $a,b,c,d$ were $2$, then the sum of the square would be even and to have the total sum be even so too must the singleton be even.

The two smallest "bases" for the square then must be either $3\cdot 5, 3\cdot 7, 5\cdot 11, 7\cdot 11$ or $3\cdot 5, 5\cdot 7, 7\cdot 11, 11\cdot 3$ having sums $168$ and $160$ respectively. If any of these had an additional prime factor larger than $2$, for example in the second base if $3\cdot 5$ was replaced by $3\cdot 3\cdot 5$, then the sum would become larger than the desired sum of $186$, so we learn that every term in the base is either a product of two small odd primes or is a $2$ times a product of small primes.

Further, the only prime which may be replaced out of $3,5,7,11$ while keeping the sum of the square less than $186$ would be switching out $11$ for $13$. Any other switch makes the sum too large.

Now, we don't have many cases left to check. If all of the terms in the square are odd, then the singleton must be of the form $2e$ for $e$ coprime to $a,b,c,d$. In order to keep the total sum low enough, it must be a small power of $2$ or it must be $13$ (or $11$ if $13$ was switched out). Anything larger makes the sum too big for either base.

Alternatively, if exactly one of the terms in the square is even, then the singleton must be of the form $e$ for $e$ either $1$ or a prime different than any of $2,a,b,c,d$.

---

As there are very few cases left to check, by finishing with brute force you can arrive at the answer and confirm that it is indeed unique.

Factorized $3\cdot 5, 5\cdot 7, 7\cdot 11, 11\cdot 3, 2\cdot 13$, or expanded they are $15,35,77,33,26$

Answer 2

We cannot have at least three even numbers, for then there would be a triangle. So, we have four odd numbers and one even.

None of the numbers in the square can be a prime number, for else the two numbers it is connected two would have that prime number as a common divisor, and share an edge.

So, each number in the square must share one prime factor with one neighbor, and a different prime factor with another, and since it does not share en edge with the third, those two numbers have different prime factors altogether, meaning that there are at least four odd prime factors involved among the four numbers in the square.

One of them could be multiplied by $2$, but maybe the singleton is the even number ... well, let's see what is possible:

With those four odd prime numbers being $3,5,7,11$, we could form:

$3\cdot 5$, $3 \cdot 7$, $5 \cdot 11$, and $7 \cdot 11$ ... sum is $168$, so leftover number is $18$, which has prime factor $3$ ... does not work.

We can try to multiply one of the numbers by $2$, but not going over $186$ that can only be done for $3 \cdot 5$, meaning a sum of $183$ with a leftover of $5$ ... also does not work.

$3 \cdot 5$, $5 \cdot 7$, $3 \cdot 11$, $7 \cdot 11$ ... sum is $160$, so leftover is $26$ ... works!

Multiplying $3 \cdot 5$ by $2$ gives leftover $11$ .. does not work

$3 \cdot 7$, $3 \cdot 11$, $5 \cdot 7$, $5 \cdot 11$ ... sum is $144$ ... leftover $42$ ... does not work

Multiplying by $2$ gives leftovers $21$, $9$, and $7$ ... none work

Taking our four odd primes as $3,5,7,13$:

$3\cdot 5$, $3 \cdot 7$, $5 \cdot 13$, $7 \cdot 13$ ... sum is $193$ ... too high

$3 \cdot 5$, $3 \cdot 13$, $5\cdot 7$, $7 \cdot 13$ ... sum $180$ ... leftover $6$ ... does not work

$3 \cdot 7$, $3 \cdot 13$, $5 \cdot 7$, $5 \cdot 13$ ... sum $160$ ... leftover $26$ ... does not work

multiplying by $2$: only $3 \cdot 7$ possible, but gives leftover of $5$ does not work.

Any other combination of four odd primes gives sum above $186$.

So: only one combination possible: the square is $15, 33, 77, 35$, and the singleton is $26$

Answer 3

A Mathematica search finds and confirms:

$\{ 33, 77, 35, 15, 26 \}$

---

mylist = Select[
   DeleteDuplicates /@ 
    Select[IntegerPartitions[186, {5}], ContainsNone[#, {1}] &], 
   Length[#] == 5 &];

fulllist = Flatten[Permutations /@ mylist, 1];

Select[fulllist, (GCD[#[[1]], #[[2]]] > 1 &&
    GCD[#[[2]], #[[3]]] > 1 && 
    GCD[#[[3]], #[[4]]] > 1 &&
    GCD[#[[4]], #[[1]]] > 1 &&
    GCD[#[[1]], #[[3]]] ==
     GCD[#[[2]], #[[4]]] ==
     GCD[#[[1]], #[[5]]] ==
     GCD[#[[2]], #[[5]]] ==
     GCD[#[[3]], #[[5]]] ==
     GCD[#[[4]], #[[5]]] == 1) &]

This is, admittedly, inefficient code. It can be sped up by incorporating the fact that the isolated vertex is even and the others are odd; avoiding over-testing rotations of the four odd numbers, etc.

Answer 4

The solution cannot be unique.

First: $3\cdot5 $, $5\cdot7$, $3\cdot11$, $7\cdot11$ with reminder $26$

Second: $3\cdot5 $, $5\cdot7$, $3\cdot13$, $7\cdot13$ with reminder $6$