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