mersenneforum.org Prime Sums
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-02-15, 03:30 #1 davar55     May 2004 New York City 108B16 Posts Prime Sums Call an ordered set of odd primes "p-good" if: it contains p elements, all prime, which sum to a prime, and every subset of q consecutive elements in the set sum to a prime, where q is any odd prime less than p. Thus for example: {3,5,11}, {5,7,11}, {3,7,13} and {5,11,13} are 3-good sets, {3,7,13,17,31}, {3,11,17,19,23} and {5,7,11,13,17} are 5-good sets, {13,17,23,31,43,53,61}, {5,13,19,29,31,47,53} are 7-good sets. A p-good set is "p-excellent" if it minimizes the largest element in the set. A p-good set is "p-swell" if it minimizes the set sum. These two measures may conflict, but if a p-good set is both p-excellent and p-swell it's "p-best". Even this theoretically may not be p-unique. The problem is to construct a p-best (or at least p-excellent) set for every prime < 100.
 2008-02-15, 03:52 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22×32×52×7 Posts Repetition allowed? {3,3,5} valid?
 2008-02-15, 13:54 #3 davar55     May 2004 New York City 5×7×112 Posts It's a set, so the elements are distinct. However, allowing repetitions may make the problem easier (smaller primes), so that could be considered a different case. Last fiddled with by davar55 on 2008-02-15 at 13:55
 2008-02-15, 17:19 #4 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22·32·52·7 Posts With only a few available primes <100 this can be a brute force problem. If I feel too lazy to think about a smart solution I may write a small proggy to enumerate all values just to exercise the coding muscles a bit. But if you made it something like all primes <500 then the brute force thing is probably nullified, and then it requires some proper thinking about it.
2008-02-15, 18:43   #5
axn

Jun 2003

143B16 Posts

Quote:
 Originally Posted by retina With only a few available primes <100 this can be a brute force problem. If I feel too lazy to think about a smart solution I may write a small proggy to enumerate all values just to exercise the coding muscles a bit. But if you made it something like all primes <500 then the brute force thing is probably nullified, and then it requires some proper thinking about it.
I think you misunderstand the role of the parameter p. It denotes the size of the set, not the size of the largest prime it contains.

 2008-02-15, 18:57 #6 Brian-E     "Brian" Jul 2007 The Netherlands 2·3·5·109 Posts Indeed, it seems to me an enormously difficult problem. Finding any p-good sets at all seems to me beyond simple brute-force searches for p greater than about 50. I don't know what sort of number theory could be used to refine the search.
 2008-02-15, 19:12 #7 davar55     May 2004 New York City 5×7×112 Posts Yes, I may have set the sights too high at all primes p < 100, but I figured that what was beyond my hardware resources and software and theory skills might be just a challenge here. However, I didn't want to scale the problem down and make it too easy, and wasn't sure where to draw the line. Since 100 is arguably arbitrary, perhaps a lower limit would be more appropriate.
2008-02-15, 19:15   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22×32×52×7 Posts

Quote:
 Originally Posted by axn1 I think you misunderstand the role of the parameter p. It denotes the size of the set, not the size of the largest prime it contains.
Oh dear, you are right. I read the last part wrongly:
Quote:
 The problem is to construct a p-best (or at least p-excellent) set for every prime < 100
I somehow got the impression that the contents of the set was primes under 100. But if it means that p<100 then of course the size of the problem suddenly grew enormously.

 2008-02-17, 08:33 #9 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22×32×52×7 Posts The best I can find for the original problem without repetition: 3-best;{3,5,11} 5-best;{5,7,11,13,17} 7-best;{5,7,11,19,29,31,37} 11-excellent;{5,19,23,37,43,59,61,71,79,89,101};{5,13,29,37,43,59,61,71,79,89,101} 11-swell;{3,7,13,17,29,37,43,47,83,97,103};{5,7,11,13,29,41,43,53,67,103,107};{5,7,11,13,29,41,43,47,73,103,107} 13-best;{3,5,11,13,23,37,43,47,83,103,107,127,149};{3,5,11,13,23,37,43,47,89,97,107,127,149} 17-best;{7,23,37,43,47,83,97,103,131,149,151,167,223,229,239,251,271}
2008-02-17, 11:35   #10
Brian-E

"Brian"
Jul 2007
The Netherlands

2×3×5×109 Posts

Quote:
 Originally Posted by retina The best I can find for the original problem without repetition: 3-best;{3,5,11} 5-best;{5,7,11,13,17} 7-best;{5,7,11,19,29,31,37} 11-excellent;{5,19,23,37,43,59,61,71,79,89,101};{5,13,29,37,43,59,61,71,79,89,101} 11-swell;{3,7,13,17,29,37,43,47,83,97,103};{5,7,11,13,29,41,43,53,67,103,107};{5,7,11,13,29,41,43,47,73,103,107} 13-best;{3,5,11,13,23,37,43,47,83,103,107,127,149};{3,5,11,13,23,37,43,47,89,97,107,127,149} 17-best;{7,23,37,43,47,83,97,103,131,149,151,167,223,229,239,251,271}
These are nice results.
I'm interested about your reason for finishing with the 17-best. Was it
(1) that 19-good sets are too difficult to find at all?
or (2) that they are findable but too difficult to search exhaustively for the 19-best?

The problem of finding a p-good set for largest possible p is interesting too. Did you find larger p-good sets than 17-good? Has anyone else tried? (Otherwise I might try myself, but I'm lazy.)

 2008-02-17, 19:25 #11 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 189C16 Posts retina was wrong Okay, everybody just forget what you saw above, it is wrong, some of the internal sub-totals are not prime. Here is new set 3-best;{3,5,11} 5-best;{5,7,11,13,17} 7-best{5,7,11,19,29,31,37} 11-swell;{5,7,17,19,23,31,47,53,79,97,191} 11-swell;{5,7,17,19,23,31,47,53,79,107,181} 11-swell;{5,7,17,19,23,37,41,53,79,97,191} 11-swell;{5,7,17,19,23,37,41,53,79,107,181} 11-excellent;{7,13,17,29,37,43,47,83,97,113,127} 11-excellent;{7,13,17,29,37,43,47,83,103,107,127} 11-excellent;{11,13,17,29,37,43,47,83,103,107,127} 13-swell;{7,13,17,29,37,43,47,83,97,113,127,181,239} 13-excellent;{7,11,13,29,41,43,53,67,103,107,157,197,223} I have checked all sets of primes up to 800 and found no p-good sets for p>13

 Similar Threads Thread Thread Starter Forum Replies Last Post gophne Miscellaneous Math 54 2017-02-22 22:28 davar55 Puzzles 3 2009-12-24 19:45 davar55 Puzzles 2 2008-08-13 12:37 davar55 Puzzles 1 2008-03-19 14:12 grandpascorpion Math 49 2007-04-22 17:06

All times are UTC. The time now is 09:40.

Sun Nov 28 09:40:04 UTC 2021 up 128 days, 4:09, 0 users, load averages: 1.10, 1.16, 1.07