mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-02-15, 03:30   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

108B16 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2008-02-15, 03:52   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×32×52×7 Posts
Default

Repetition allowed? {3,3,5} valid?
retina is offline   Reply With Quote
Old 2008-02-15, 13:54   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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
davar55 is offline   Reply With Quote
Old 2008-02-15, 17:19   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·32·52·7 Posts
Default

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.
retina is offline   Reply With Quote
Old 2008-02-15, 18:43   #5
axn
 
axn's Avatar
 
Jun 2003

143B16 Posts
Default

Quote:
Originally Posted by retina View Post
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.
axn is offline   Reply With Quote
Old 2008-02-15, 18:57   #6
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2·3·5·109 Posts
Default

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.
Brian-E is offline   Reply With Quote
Old 2008-02-15, 19:12   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2008-02-15, 19:15   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×32×52×7 Posts
Default

Quote:
Originally Posted by axn1 View Post
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.
retina is offline   Reply With Quote
Old 2008-02-17, 08:33   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×32×52×7 Posts
Default

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}
retina is offline   Reply With Quote
Old 2008-02-17, 11:35   #10
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2×3×5×109 Posts
Default

Quote:
Originally Posted by retina View Post
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.)
Brian-E is offline   Reply With Quote
Old 2008-02-17, 19:25   #11
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

189C16 Posts
Default 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
retina is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Consecutive cumulative prime sums gophne Miscellaneous Math 54 2017-02-22 22:28
Prime Reciprocal Sums davar55 Puzzles 3 2009-12-24 19:45
Prime Sums #3 davar55 Puzzles 2 2008-08-13 12:37
Prime Sums #2 davar55 Puzzles 1 2008-03-19 14:12
Sums of prime powers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.