13
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ computer-puzzle? Hmm, maybe this is harder than I was expecting. $\endgroup$ – Hugh Feb 7 at 2:06
  • $\begingroup$ must the numbers be distinct? thanks! $\endgroup$ – Omega Krypton Feb 7 at 2:19
  • 2
    $\begingroup$ @Omega Kyrpton: By necessity! $\endgroup$ – Bernardo Recamán Santos Feb 7 at 2:21
  • $\begingroup$ Can't I just make every number 2? $\endgroup$ – stuart stevenson Feb 7 at 10:35
  • $\begingroup$ @stuartstevenson if every number were two, then every node would be directly connected to every other node. $\endgroup$ – Bass Feb 7 at 10:53
8
$\begingroup$

My best (manually)

Sum=79623

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.

$\endgroup$
  • $\begingroup$ Nice job. How long did it take to run this code? $\endgroup$ – Dr Xorile Feb 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 Barrera Feb 23 at 20:52
  • $\begingroup$ @DrXorile The total run-time was about 25 minutes. $\endgroup$ – Daniel Mathias Feb 23 at 21:11
  • $\begingroup$ @FreddyBarrera DrXorile's solution differs from mine in that the $(7,23,53,3)$ diamond is flipped. $\endgroup$ – Daniel Mathias Feb 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 Barrera Feb 23 at 21:45
8
$\begingroup$

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

enter image description here

For a total of

$79685$

Breaking these numbers into their prime factorisations looks as follows

enter image description here

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

$\endgroup$
  • $\begingroup$ See my solution of 79627 below... $\endgroup$ – Dr Xorile Feb 23 at 4:06
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 Good job, I completely messed up what I was trying to do earlier. $\endgroup$ – hexomino Feb 7 at 10:09
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$

snowflake

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.

$\endgroup$
  • 1
    $\begingroup$ I have already provided a solution with lesser sum of 79623, though I do like your approach. $\endgroup$ – Daniel Mathias Feb 23 at 4:38
  • $\begingroup$ Nice. Sorry, I didn't see your answer before. I'll edit my response to include it. $\endgroup$ – Dr Xorile Feb 23 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.