Labelling a Snow Flake Graph to Attain Minimum Sum

Question

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.

Answer 1

My best (manually)

With a sum of

79623

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.

Answer 2

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.

Answer 3

To get started, let's see what the final answer must look like:

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.)

That gave me this:

                 61,17

37,47    2,61,37         13,41,17    31,41

   7,47,23   2,3,5,7,11,13     3,59,31

53,23     5,53,29        11,43,19    19,59

                  29,43

Which, when multiplied out, looks like

              1037

1739    4514        9061    1271

    7567     30030      5487

1219    7685        8987    1121

              1247

For a baseline sum of

1037 + 1739 + 4514 + 9061 + 1271 + 7567 + 30030 + 5487 + 1219 + 7685 + 8987 + 1121 + 1247 = 80965.

Answer 4

Using the labeling provided by Bass we have that the sum is equal to:

$$b d + a r + a b c + d e f + f g + p q r + c e h k n q + g h i + o p + m n o + j k l + i j + l m$$

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.

Swapping an outer edge and a non-adjacent inner edge, e.g. $a$ and $e$, gives:

$$ e < a \equiv b c + r < d f + c h k n q $$

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.

This confirms that hexomino's answer is optimal.

Answer 5

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 answer is: 79627

\begin{align} a &= 7\\ g,h &= 23,43\\ b &= 5\\ i,j &= 31,47 \\ c &= 13 \\ k,l &= 29,19 \\ d &= 2 \\ m,n &= 59,61 \\ e &= 11 \\ o,p &= 17,37 \\ f &= 3 \\ q,r &= 41,53\\ \end{align}

Then

$abcdef + agh + bij + ckl + dmn + eop + fqr + hi + jk + lm + no + pq + rg = 79627$

But, you may ask, how did I find this marvel of optimization?

I'm glad you asked. :-)

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.

eg

   5,   23,   61,   19
   7,   17,   59,   25
   7,   19,   53,   53
   7,   23,   43,   73
  11,   17,   37,   77
  13,   17,   31,  145
   3,   43,   53,  159
  13,   19,   29,  167
   5,   29,   47,  181
   2,   59,   61,  202
   5,   23,   59,  211
   3,   37,   61,  225
   ...

where the first three are the primes and the 4th is the absolution value of the product minus 6556.

Then I treated these as nodes in a maze and used dijkstra's algorithm to find the shortest route (using the abs(product-6996) as the distance to each node).

This led to:

[[7, 23, 43], [11, 17, 37], [13, 19, 29], [2, 59, 61], [5, 31, 47], [3, 41, 53]] (Total distance from 6996 is 1285).

Finally, I ran through the possible permutations (there's not too many) which led to the solution shown.