Problems & Puzzles:
Puzzles
Puzzle 175. Integer average & sets of
consecutive primes(*)
Here we will ask for the earliest set of K consecutive primes such that
one permutation of the set has the property that every leftsubset
has an integer average.
Example:
I have found that the earliest set for K=11
is the set that goes from the prime 67
to the prime 109. This set has the
following permutation:
{97, 103, 73, 71, 101, 83, 109, 67, 79, 107, 89}
with the property that all the following numbers are
integers:
97/1
(97+103)/2
(97+103+73)/3
...
(97+103+73+...+89)/11
Questions:
a) Find the earliest set for
K=2, 3, ...10, 12, ...
b) Do you think that there is always a setsolution for any K?
_______
This puzzle is an extension of the POTW 818
of the very interesting puzzles site Macalester
College Problem of the Week.
Solution:
Solutions came from Jud McCranie (229), J. C. Colin
(41), Joe K. Crump (81), J. C. Rosa (15) & Gennady Gusev (22).
BTW, all of them noticed that my solution for n=11
was not the minimal one.
Here are the Jud solutions for K=1 to 20. In
particular he got the largest solution (K=229)
K least prime: sequence of primes
3 3: 3 5 7
4 17: 29 23 17 19
5 71: 71 83 89 73 79
6 5: 5 11 17 19 13 7
7 7: 7 13 19 17 29 11 23
8 17: 17 23 41 31 43 19 29 37
9 239: 239 251 257 241 277 271 263 281 269
10 17: 17 23 29 19 37 31 47 53 41 43
11 31: 31 37 61 47 59 41 67 73 43 71 53
12 29: 31 37 61 47 59 41 67 73 43 71 53 29
13 43: 47 83 89 97 79 73 71 53 101 67 43 61 59
14 149: 151 157 163 197 167 179 211 199 223 173 149 191 193 181
15 229: 229 241 271 251 263 281 277 283 307 257 233 311 293 269 239
16 47: 47 53 59 73 103 61 101 71 89 83 107 113 67 79 109 97
17 7: 19 31 43 23 59 17 67 13 61 47 71 29 53 41 11 7 37
18 7: 19 31 43 23 59 17 67 13 61 47 71 29 53 41 11 7 37 73
19 79: 79 103 139 151 163 157 167 89 149 173 137 113 83 131 101 97 127
109 107
20 29: 29 47 59 37 43 61 109 79 103 73 97 67 41 107 83 101 71 53 89 31
This is his method:
For size k, start with a sequence of k odd primes. Get the sum
of these primes. If it isn't a multiple of k, a solution isn't
possible  reject that set and go on to the next one.
Now try each pair of primes as the first two in the permutation.
You can assume that the smaller of the pair is first. Now start
filling in the nth term, for n=3 to k. To fill in the nth term,
find all unused primes that give a sum that is divisible by n when added
to the sum of the primes already used. Try each of these in the
nth location and repeat with n+1.
One thing that will speed it up is that when you have checked that the
sum of the primes in the set is a multiple of k, make sure that there is
at least one term so that the sum minus that term is divisible by k1.
Also, such a prime must go in the last location.
Later he made a substantial improvement:
After I wrote the last message, I realized that it would be much more
efficient to fill in the numbers from back to front. With that
change, my program does through k=100 in 22 seconds. I can send as many
as you want... Take a set of k consecutive odd primes. Find the
sum of the primes in the set, call it Sum. If the sum is not
divisible by k then go to the next set, starting at the next prime.
For each of the primes Pi in the set, see if (SumPi) mod (k1) = 0.
Try each such Pi in the kth location. Now replace Sum by SumPi
and see if there is an unused prime Pj, such that (SumPj) mod (k2) =
0. If so, try Pj in the k1 location. Repeat this process
until you have two primes left. Since they are odd primes, they
can go in the first two locations. If you get to this point, you
have a solution. If you don't get to a solution, try the next Pj,
the next Pi, etc. If none work, try the set of primes (shift the
set over by 1).
***
The 30/4/2002 G. Gussev wrote this very interesting
interesting lines:
In puzzle 175 we've been searching the
earliest set of K consecutive primes such that one permutation of the
set has the property that every LEFTsubset has an integer average.
And what about the set where every
LEFTsubset and every RIGHTsubset simultaneously have the same
properties?
Here're examples for k = 4 and k = 6:
4: {251,257,263,269} (all 4! permutations)
6: {7, 13, 19, 5, 11, 17}
And what about the earliest set of K
consecutive primes (increasing sequence) with LEFTsubset and
RIGHTsubset properties?
For k=4 : {251,257,263,269} (the same as
above, but only this
one)
For k=5 : {43451,43457,43481,43487,43499}
And finally what about the earliest set
of K consecutive primes such that one permutation of the set has the
property that EVERY (consecutive) SUBSET has an integer average?
For k=4 : {251,257,263,269} (the same as
above)
For k=5 : {18719,18713,18731,18749,18743}
For k=6 : {18701, 18719, 18713, 18743,
18749, 18731}
For k=7 : {577739, 577751, 577721, 577757,
577667, 577799, 577781}
i.e.
(pi+pj)/2  integer
(p1+p2+p3)/3  integer
(p2+p3+p4)/3  integer
(p3+p4+p5)/3  integer
(p4+p5+p6)/3  integer
(p5+p6+p7)/3  integer
(p1+p2+p3+p4)/4  integer
(p2+p3+p4+p5)/4  integer
(p3+p4+p5+p6)/4  integer
(p4+p5+p6+p7)/4  integer
(p1+p2+p3+p4+p5)/5  integer
(p2+p3+p4+p5+p6)/5  integer
(p3+p4+p5+p6+p7)/5  integer
(p1+p2+p3+p4+p5+p6)/6  integer
(p2+p3+p4+p5+p6+p7)/6  integer
and at last (p1+p2+p3+p4+p5+p6+p7)/7 
integer!
For k=8 : {1138237, 1138183, 1138213,
1138171, 1138141, 1138147, 1138273, 1138363}
What do you think of these
extensions of your puzzle?
Could you give new variants of the puzzle to
your readers?
I think it would be a little bit more
difficult and also interesting.
***
