Project Euler Forum

Jochen_P wrote:Got the same results as you have for S(100,000), S(200,010) and S(150,073) so I guess my triplet finding algorithm is ok. Well then, it must be a glitch in my (slow) prime finding solutions which hasn't shown yet for the other problems it has solved. Hard to find :sceptic:

You're using Python, aren't you? Then it's probably not integer overflow.
I have an idea what might be problematic, could verify if you PM me the code.

My code can't handle that

You mean the sum of S(1) to S(10000)? Wonder how that can be..

Easy: our programmes don't consider that many rows.

No, it's not my Eratosthenes method of prime checking (trial division of primes up to sqrt of testee).
I found a MillerRabin algorithm on the web and tried with this instead. Got me the same wrong result in just 32 minutes

Daniel, PM is on the way!

edit: Daniel spotted the looney (me). Silly mistake. Danke, Daniel

I tried to apply the 6k+/-1 rule to my loop from row start to row end, which worked ok for the beforementioned tests but of course not for all cases which I failed to recognize

Do you consider the prime 5 a part of a prime triplet? It is part of a prime quadruplet, and I wonder if sets of more than 3 primes are considered "prime triplets" as well. Thanks.

The problem says nothing about being part of more than one prime triplet . A prime quadruple is just two triplets that aren't disjoint.

Thanks.

Hmm. I get the right answer for all the test cases, but not the final answer. Can someone confirm if either of these is correct?

S(5678027) ends in 78.
S(7208785) ends in 09.

It took me a while to understand why I was getting this wrong, my program looked fine. What I did was to reimplement the pattern detector in a brutal way, and bingo I had missed one pattern.

I am trying to understand this problem.

For my understanding, 31 has neighbors: 23, 24, 25, 30, 32, 38, 39, 40. There is only one prime number, 23, in them. Why is 31 considered as an element of a triplet. Can anyone kindly point out what I missed?

{23,29,31} is a prime triplet because 23 and 31 are adjacent to 29. Therefore 23, 29 and 31 are all part of (at least one) prime triplet.

TripleM wrote:{23,29,31} is a prime triplet because 23 and 31 are adjacent to 29. Therefore 23, 29 and 31 are all part of (at least one) prime triplet.

Thanks a lot, TripleM! Now I get.

S(1 000 000)=<snipped by moderator>?

Yes.

I've been working on this problem for a while now trying to confirm the test data, which says that S(10000) = 950007619. Because each number in row 10000 is around 50 million, that would lead me to believe that there are 19 primes in this row that are part of a prime triplet family. I keep coming up with the following 11 primes: I'm wondering if someone would be willing to give me a prime that is part of a triple but not on my list. That would help me to figure out if the issue is with how I'm generating/determining my primes or with how I'm looking for triples.

tchiari wrote: Sat Jan 12, 2019 6:53 pmI'm wondering if someone would be willing to give me a prime that is part of a triple but not on my list. That would help me to figure out if the issue is with how I'm generating/determining my primes or with how I'm looking for triples.

I've sent a private message.

tchiari wrote: Sat Jan 12, 2019 6:53 pm I've been working on this problem for a while now trying to confirm the test data, which says that S(10000) = 950007619. Because each number in row 10000 is around 50 million, that would lead me to believe that there are 19 primes in this row that are part of a prime triplet family. I keep coming up with the following 11 primes:

Expand

49,995,811
49,997,501
49,998, 209
49,999,441
49,999,819
50,000,921
50,000,971
50,001,197
50,003,077
50,003,201
50,004,407

I'm wondering if someone would be willing to give me a prime that is part of a triple but not on my list. That would help me to figure out if the issue is with how I'm generating/determining my primes or with how I'm looking for triples.

i got the exact same result. i forgot the "value itself"

TripleM wrote: {23,29,31} is a prime triplet because 23 and 31 are adjacent to 29. Therefore 23, 29 and 31 are all part of (at least one) prime triplet.

I would rather say that 29 and 31 are adjacent to 23.
I have the same problem. I try to figure out how to do it efficiently.
I hope that the previous and next lines are sufficients to do the job. I already have those lines.
I know that my result is still wrong, but does it make sense that it has 18 digits?
Actually, my execution time is around 500 ms on an Intel I7 4790K.
If I generate only once the list (flags) of prime numbers up to the square root of the greatest numbers with the Sieve of Eratosthene, I can extend the sieve to the appropriate range.
So, the three lines are flags saying if the corresponding number is a prime.