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 left-subset 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 set-solution 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 k-1.  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 (Sum-Pi) mod (k-1) = 0.  Try each such Pi in the kth location.  Now replace Sum by Sum-Pi and see if there is an unused prime Pj, such that (Sum-Pj) mod (k-2) = 0.  If so, try Pj in the k-1 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 LEFT-subset has an integer average.

And what about the set where every LEFT-subset and every RIGHT-subset 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 LEFT-subset and RIGHT-subset 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? 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.