- --- On Sun, 6/2/13, Jens Kruse Andersen <jens.k.a@...> wrote:
> Phil Carmody wrote:

I specifically wanted to offer the choice. I wanted the chains to be longer, and also less simple to find. (By which I mean that you can't just do a simple O(length)-time depth-first search from each root prime, as you now have a tree to probe, not a straight line, and might want to consider how much effort is wasted doing duplicated work as neigbouring roots share common sub-trees.)

> > Find sets of 3 consecutive primes whose sum is itself prime,

> > and associate that set and its members with that sum.

> >

> > What's the longest chain of associated primes you can find?

> > Heuristically - would you expect there to be longer ones

> > than the longest you can find?

>

> http://www.primepuzzles.net/puzzles/puzz_421.htm requires that the

> sum is always the first of the 3 consecutive primes in the next sum.

> http://primes.utm.edu/curios/page.php/507995698619.html

Good work. I presume you just ran a prime sieve and then probed for each one with no deduplication? Given how likely failure is, probing a tree shouldn't be much more than a small factor smaller than probing a straight line.

> says for that:

>

> "Start with the prime 507995698619. Add it with the two next primes

> to get a sum which is prime. Repeat. The first 10 sums are prime.

> This is the first case with more than 8.

> Arbitrarily long chains are certainly expected.

I hadn't considered Dickson. It's the big gun, certainly. I wondered initially if it would fail on guaranteeing that the positioned primes are consecutive, but if you ask for a triplet {p,p+3+/-1,p+6}, then that comes for free.

> It would for example follow from Dickson's conjecture:

> http://primes.utm.edu/glossary/xpage/DicksonsConjecture.html

Phil

--

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani] - --- On Sun, 6/2/13, Jens Kruse Andersen <jens.k.a@...> wrote:
> Phil Carmody wrote:

I specifically wanted to offer the choice. I wanted the chains to be longer, and also less simple to find. (By which I mean that you can't just do a simple O(length)-time depth-first search from each root prime, as you now have a tree to probe, not a straight line, and might want to consider how much effort is wasted doing duplicated work as neigbouring roots share common sub-trees.)

> > Find sets of 3 consecutive primes whose sum is itself prime,

> > and associate that set and its members with that sum.

> >

> > What's the longest chain of associated primes you can find?

> > Heuristically - would you expect there to be longer ones

> > than the longest you can find?

>

> http://www.primepuzzles.net/puzzles/puzz_421.htm requires that the

> sum is always the first of the 3 consecutive primes in the next sum.

> http://primes.utm.edu/curios/page.php/507995698619.html

Good work (as per usual!). I presume you just ran a prime sieve and then probed for each one with no deduplication? Given how likely failure is, probing a tree shouldn't be much more than a small factor smaller than probing a straight line.

> says for that:

>

> "Start with the prime 507995698619. Add it with the two next primes

> to get a sum which is prime. Repeat. The first 10 sums are prime.

> This is the first case with more than 8.

> Arbitrarily long chains are certainly expected.

I hadn't considered Dickson. It's the big gun, certainly. I wondered initially if it would fail on guaranteeing that the positioned primes are consecutive, but if you ask for a triplet {p,p+3+/-1,p+6}, then that comes for free.

> It would for example follow from Dickson's conjecture:

> http://primes.utm.edu/glossary/xpage/DicksonsConjecture.html

Phil

--

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani] - Phil Carmody wrote:
> I specifically wanted to offer the choice. I wanted the chains

With the choice we quickly get a chain with 12 sums:

> to be longer, and also less simple to find.

281 + 283 + 293 = 857

857 + 859 + 863 = 2579

2551 + 2557 + 2579 = 7687

7681 + 7687 + 7691 = 23059

23059 + 23063 + 23071 = 69193

69193 + 69197 + 69203 = 207593

207569 + 207589 + 207593 = 622751

622751 + 622777 + 622781 = 1868309

1868287 + 1868291 + 1868309 = 5604887

5604881 + 5604887 + 5604901 = 16814669

16814669 + 16814671 + 16814701 = 50444041

50444027 + 50444041 + 50444059 = 151332127

The longest chain with initial primes below 10^11 is probably 14 sums:

2878090951 + 2878090961 + 2878090967 = 8634272879

8634272839 + 8634272879 + 8634272891 = 25902818609

25902818609 + 25902818629 + 25902818663 = 77708455901

77708455819 + 77708455823 + 77708455901 = 233125367543

233125367543 + 233125367599 + 233125367609 = 699376102751

699376102751 + 699376102757 + 699376102783 = 2098128308291

2098128308239 + 2098128308273 + 2098128308291 = 6294384924803

6294384924787 + 6294384924803 + 6294384924823 = 18883154774413

18883154774413 + 18883154774441 + 18883154774447 = 56649464323301

56649464323301 + 56649464323303 + 56649464323307 = 169948392969911

169948392969877 + 169948392969881 + 169948392969911 = 509845178909669

509845178909611 + 509845178909669 + 509845178909687 = 1529535536728967

1529535536728967 + 1529535536728987 + 1529535536728999 = 4588606610186953

4588606610186927 + 4588606610186947 + 4588606610186953 = 13765819830560827

There are also 14 starting with

44453980303 + 44453980309 + 44453980379 = 133361940991

> I presume you just ran a prime sieve and then probed for each one

I didn't bother with deduplication but I ran two prime sieves in

> with no deduplication?

parallel, around p and 3p. This meant the first sum never had to be prp

tested, and its surrounding primes were also generated without prp tests.

It could be extended to a third sieve around 9p and so on, but each

extra sieve has to sieve a larger interval and avoids fewer prp tests.

> I hadn't considered Dickson. It's the big gun, certainly.

Dickson's conjecture can be manipulated to ensure consecutive primes

> I wondered initially if it would fail on guaranteeing that the

> positioned primes are consecutive, but if you ask for a triplet

> {p,p+3+/-1,p+6}, then that comes for free.

in this problem for any admissible pattern. We can just demand extra

primes chosen so specific prime factors are forced to divide certain

numbers in a gap.

For example, we can ensure consecutive {p, p+6} by demanding four primes

{p, p+6, p+8, p+14}. This forces 3 to divide p+4, and 5 to divide p+2.

--

Jens Kruse Andersen - --- In primenumbers@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...> wrote:

> Arbitrarily long chains are certainly expected.

which is a special case of Bateman-Horn:

> It would for example follow from Dickson's conjecture:

> http://primes.utm.edu/glossary/xpage/DicksonsConjecture.html

http://tech.groups.yahoo.com/group/primenumbers/message/25133

David