Label the vertices (or nodes) of this graph with positive integers so that any two nodes are joined by a edge (or line) if and only if the corresponding integers have a common divisor greater than 1 (i.e. they are not relatively prime). Do so in such a way that the total sum of the 13 numbers is minimum.

5 Answers
5

Update:
An exhaustive search of all 28.74 billion distinct arrangements with the lowest primes in the center has confirmed that this is the optimal solution. The C code for this search can be viewed here.

$\begingroup$Nice job. How long did it take to run this code?$\endgroup$
– Dr XorileFeb 23 at 17:02

$\begingroup$With the smallest prime numbers in the edges of the center of the graph and leaving the prime numbers 2, 59 and 61 fixed (as they are in your configuration), I obtained the same result. In addition, with this same configuration but exchanging 59 with 61, we get the same result as @DrXorile (currently, 79627) but with a different partition.$\endgroup$
– Freddy BarreraFeb 23 at 20:52

$\begingroup$@DrXorile The total run-time was about 25 minutes.$\endgroup$
– Daniel MathiasFeb 23 at 21:11

$\begingroup$@FreddyBarrera DrXorile's solution differs from mine in that the $(7,23,53,3)$ diamond is flipped.$\endgroup$
– Daniel MathiasFeb 23 at 21:14

$\begingroup$Yes. I wanted to say is that if we exchange 59 with 61 of your solution, we get 79627, with a different partition than the partition that gave Dr Xorile. That is, 79627 has at least two different solutions.$\endgroup$
– Freddy BarreraFeb 23 at 21:45

Edit: I made an assertion previously about the minimum which turns out to be wrong due to a bug in my code. The strategy of Bass is the right one and using the reasoning of 2012rcampion, we must put the smallest numbers in the centre

Here is the best answer I have found so far using this strategy

For a total of

$79685$

Breaking these numbers into their prime factorisations looks as follows

It seems as though this is still not optimal, as suggested here so please feel free to keep investigating.

Since there are no fully connected triangles in the graph, each edge must be represented by a distinct prime. That gives us this basic shape:

bd
ar abc def fg
pqr cehknq ghi
op mno jkl ij
lm

(Each letter a-r is a distinct prime.)

Then, you take out a computer, and find the best assignment for a-r. I didn't, so I did this instead:

Take the primes from 2 to 61.

1. Put the six smallest primes in the middle.
2. Arrange the same on the concave corners so that the differences between "neighbours" are big.
3. Pair the smallest concave corners with the largest remaining primes.
4. Repeat.
5. For the points, pair small with big, and midsize with midsize

The basic idea is to avoid multiplying big by big, because that's what makes huge numbers fast. To further improve the result, steps 3 and 4 should really be combined, so that the products at the concave spots are as close to each other as possible, but that seemed too tedious to do by hand. (If you do that, the optimal order for step 2 might change, too.)

We want to find an assignment of unique primes to the variables $a$ through $r$ such that the sum is minimized. It is easy to see that we must use the smallest 18 primes ($p_1=2$ through $p_{18}=61$) to minimize the sum, so the problem reduces to finding a permutation of the first 18 primes.

We can reduce the search space by testing what happens if we interchange two numbers. We'll assume we have the optimal solution, so any change will increase the sum (or keep it the same). For example, swapping $a$ and $b$ gives us

$$
b d + a r + a b c \leq a d + b r + a b c
$$

(Note I have kept only the terms containing $a$ and $b$, as the others do not change.) We can reduce this to $b(d-r) \leq a(d-r)$. Since all the variables are positive and distinct, this means that either $b<a$ and $d>r$, or $b>a$ and $d<r$.

Doing this for an outer edge and its adjacent inner edge, $a$ and $c$ for example, gives us:

$$
c < a \equiv r < e h k n q \\
$$

Note the form of the second half, comparing one variable to the product of five variables. If we compare the largest prime, $p_{18}=61$, to the five smallest primes, $p_1 p_2 p_3 p_4 p_4=2\cdot 3\cdot 5\cdot 7\cdot 11=2310$, we can see that this inequality must always be satisfied. Therefore the first half must be true, and all outer edges must be larger than their adjacent inner edges.

To see if we can violate the right-hand inequality we'll ignore the uniqueness constraint between terms and test $p_{18}c + p_{18} < p_1 p_2 + c p_1 p_2 p_3 p_4$, i.e. $61c+61<6+210c$, which yields $c>\frac{55}{149}$. Since $c$ must be at least $p_1=2$, this inequality cannot be violated. Therefore, all outer edges must be larger than all inner edges.

I have got a slightly lower answer than either @hexomino or @FreddyBarrera in this question. @DanielMathias did an exhaustive search and found one slightly better (I confess I didn't even try the exhaustive approach once I ballparked how many permutations there were).

My intuition told me that we need to balance the "middle" nodes (agh,bij,ckl,...). The product of all these numbers is simply the product of the first 18 primes or 117,288,381,359,406,970,983,270. The 6th root of this is about 6996. So I figured that picking triplets such that the product was close to 6996 would be a winning idea.

So I generated all the triplets and ordered them by how far the product was from 6996.