Problems & Puzzles: Puzzles

Puzzle 142.  Optimal Assignation of Primes in several Patterns

1. Here you are asked to find the optimal assignation of the first N primes in certain pattern, in order to the Sum of the Product of all the Adjacent Couples - SPAC(pattern, N) - of these primes is a quantity:

a) minimal
b) maximal

 Example: Suppose you assign the first 5 primes in a row in the following non-optimal pattern: 7, 2, 3, 11, 5 Then, for this non optimal assignation: SPAC(row, 5) = 7*2+2*3+3*11+11*5 =108

Solve the exercise if the first N primes are in the following patterns:

1. in a Row
2 around a Circle
3. in a Square nxn, N=n^2, (*)
4. in a Rectangle nxm, N=nxm (*)

Here you are asked to find the general strategy or algorithm to make the optimal assignation for each pattern, for each optimal condition (minimal and maximal) and for any N value, if such strategy exists.

Whenever you discover the asked solutions (strategies) please send the description of such strategy and also the corresponding SPAC(pattern, N) solutions for N=3 to 7.

2. A second question associated to the discovery of these strategies is to find a functional bound to the SPAC values for each N, pattern and optimal condition.

______
n.b. This puzzle is based in other two similar puzzles posted 'here and there' in the Web for the first N natural numbers. But I don't want to spoil your fun giving right now the references. I will do that later, only after receiving the solutions.

(*) In a square - or in a rectangle - the 'adjacent primes' are only in the vertical and horizontal direction, and the product to be added should be calculated for the entire row or for the entire column.

Solution

Jean-Charles Meyrignac points out that the tri-dimensional version of this puzzle was posted by Christer Linstedt to Martin Gardner as is consigned in an old (1980) Gardner's book .

Jean-Charles also sent the following solutions to 1 & 2, obtained - I suppose by an exhaustive analysis, because he added "...But I have not find any strategy...

Row:

Max 25= 2 5 3
Min 16= 3 2 5
Max 66= 2 5 7 3
Min 35= 5 3 2 7
Max 163= 2 5 11 7 3
Min 68= 7 3 5 2 11
Max 320= 2 5 11 13 7 3
Min 123= 11 3 5 7 2 13
Max 585= 2 5 11 17 13 7 3
Min 206= 13 3 7 5 11 2 17
Max 934= 2 5 11 17 19 13 7 3
Min 325= 17 3 11 7 5 13 2 19
Max 1439= 2 5 11 17 23 19 13 7 3
Min 484= 19 3 13 7 11 5 17 2 23
Max 2220= 2 5 11 17 23 29 19 13 7 3
Min 715= 23 3 17 7 11 13 5 19 2 29
Max 3165= 2 5 11 17 23 31 29 19 13 7 3
Min 1006= 29 3 19 7 13 11 17 5 23 2 31

Circle:

Max 31= 2 3 5
Min 31= 2 3 5
Max 72= 2 3 7 5
Min 60= 2 5 3 7
Max 169= 2 3 7 11 5
Min 119= 2 7 5 3 11
Max 326= 2 3 7 13 11 5
Min 198= 2 11 5 7 3 13
Max 591= 2 3 7 13 17 11 5
Min 321= 2 13 5 7 11 3 17
Max 940= 2 3 7 13 19 17 11 5
Min 476= 2 17 5 11 7 13 3 19
Max 1445= 2 3 7 13 19 23 17 11 5
Min 703= 2 19 5 13 11 7 17 3 23
Max 2226= 2 3 7 13 19 29 23 17 11 5
Min 1002= 2 23 5 17 11 13 7 19 3 29
Max 3171= 2 3 7 13 19 29 31 23 17 11 5
Min 1375= 2 29 5 19 11 13 17 7 23 3 31

***

Tiziano Mosconi has discovered (1/9/01) the strategies for the row assignations:

Max

For the Max sequence it seems to me that the n-th prime number is to be inserted between the couple of primes whose sum is the maximum.

For example from  {2 5 3} to {2 5 7 3} we have inserted 7 between 5 and 3 because 5+3=8 is the maximum sum of two consecutive elements in the starting list. The same from {2 5 7 3} to {2 5 11 7 3} and so on.

So I wrote a small program in Mathematica that print those sequences (the code is shown in his email buy I cut it for space reasons. Any way it can be sent on request). This is the output:

max  66 = {2, 5, 7, 3}
max  163 = {2, 5, 11, 7,3}
max  320 = {2, 5, 11, 13, 7, 3}
max  585 = {2, 5, 11, 17, 13, 7, 3}
max  934 = {2, 5, 11, 17, 19, 13, 7, 3}
max  1439 = {2, 5, 11, 17, 23, 19, 13, 7, 3}
max  2220 = {2, 5, 11, 17, 23, 29, 19, 13, 7, 3}
max  3165 = {2, 5, 11, 17, 23, 31, 29, 19, 13, 7, 3}
max  4486 = {2, 5, 11, 17, 23, 31, 37, 29, 19, 13, 7, 3}
max  6127 = {2, 5, 11, 17, 23, 31, 41, 37, 29, 19, 13, 7, 3}
max  7964 = {2, 5, 11, 17, 23, 31, 41, 43, 37, 29, 19, 13, 7, 3}
max  10149 = {2, 5, 11, 17, 23, 31, 41, 47, 43, 37, 29, 19, 13, 7, 3}
max  12898 = {2, 5, 11, 17, 23, 31, 41, 47, 53, 43, 37, 29, 19, 13, 7, 3}

{0.0166667 Second}

Min

Finding a strategy to find the minimum is a little more difficult because we must distinguish if the list we are going to generate has an even or an odd number of elements.

The strategy is difficult to explain by words but it's very simple if explained with a diagram.

The point is that from one list to the next there is a rearrangement of the list.
From  {11 3 5 7 2 13} to {13 3 7 5 11 2 17}, for example, the last prime ( 17 ) enters at the last position, 13, that was the last becomes the first. The idea is to have two directions of constructing the list, one that goes 17->13->11->7 and the other that goes 2->3->5.

As you can see each path goes forward and backward in the list in a precise way.
As in the Max case, I've written a program in Mathematica...

min 16 = {3, 2, 5}
min 35 = {5, 3, 2, 7}
min 68 = {7, 3, 5, 2, 11}
min 123 = {11, 3, 5, 7,2, 13}
min 206 = {13, 3, 7, 5,11, 2, 17}
min 325 = {17, 3, 11, 7, 5, 13, 2, 19}
min 484 = {19, 3, 13, 7, 11, 5, 17, 2, 23}
min 715 = {23, 3, 17, 7, 11, 13, 5, 19, 2, 29}
min 1006 = {29, 3, 19, 7, 13, 11, 17, 5, 23, 2, 31}
min 1387 = {31, 3, 23, 7, 17, 13, 11, 19, 5, 29, 2, 37}
min 1856 = {37, 3, 29, 7, 19, 13, 17, 11, 23, 5, 31, 2, 41}
min 2455 = {41, 3, 31, 7, 23, 13, 17, 19, 11, 29, 5, 37, 2, 43}
min 3170 = {43, 3, 37, 7, 29, 13, 19, 17, 23, 11, 31, 5, 41, 2, 47}

{0.0833333 Second}

Of course my strategy is basically an extrapolation, I can't prove it will give right results forever. Anyway I hope to have done something interesting.

***

Jon Perry got (June 2003) a proof for the Tiziano's approach:

Here is a proof of Tiziano's conjecture;

Let V(2)={2,3} and in general V(n) is the vector consisting of the first n primes arranged to be SPAC-maxic.

Tiziano builds V(n) from V(n-1) by claiming that the new prime is inserted between the pair of primes with the largest sum. We can also claim that the new prime is inserted between the pair of primes with the largest product - in this question there is no difference, however there might be in other questions.

To prove that this step does produce SPAC-maxic V's, it suffices to demonstrate that inserting a prime between the two primes with the largest sum creates a SPAC-maxic V(n+1), as if this is true, then V(n) is always 'smooth', in that the terms of V(n) are always increasing until the midpoint, after which they are always decreasing. For interest, V(2k) has a {k+1,k-1} split, and V(2k+1) has a {k+1,k} split, where a {x,y} split of

V(n) has x terms in a strictly increasing sequence, and (y+1) terms in a stricly decreasing sequence.

If we let the two adjacent elements from V(n) with the maximal sum be a and b, and consider two other adjacent elements (a-i) and (b-j), where i and j are both non-negative integers. Obviously both i and j cannot be zero.

In creating V(n+1), we subtract the product of the two elements we are inserting between, and add the two new products. If the new prime is p,

then:

MAXSPAC(n+1) = MAXSPAC(n) - xy + p(x+y)

So we need to maximize p(x+y)-xy

Using the a and b from before:

p(a-i+b-j) - (a-i)(b-j)
= pa - pi + pb - pj - ab + ib + ja - ij
= p(a+b) - ab + i(b-p) + j(a-p) - ij

From here, as (a-p) and (b-p) are negative, we wish i and j to be as small as possible, and the ij component confirms this. So for any i>0 and/or j>0, the insertion sum is less than for i=j=0.

QED.

The min case I haven't tackled yet. There is a similarity in the construction of the min and max cases, both use a kind of 'spiralling' technique, the max method goes:

1) Take the first prime (2), and place it first
2) Take the next prime (3), and place it last
3) Take the 3rd prime (5), and place it after the 2
4) Take the 4th prime (7), and place it before the 3
5) Continue.

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.