Project Euler Forum

Does it have to be exactly a triple (no more, no less).
For example in row 6 is the number 17. It is part of a prime quad: 11. 13. 17. 23.
Or in row three the number 5 is part of a quad as well. 2, 3, 5, 7.

Therefore are these NOT to be considered a triple for purposes of this problem?

Being in a group greater than a triple counts as being in at least one triple.

In your example, both 5 and 17 would count as being in prime triples.

I have been trying to solve problem 196 (prime triplets) now for a couple of days.
The general algorithm I have, and it is correct for S(10000).
Generaring the numbers for S(5678027) gives me a result, as also S(7208785), but generating those numbers costs hours. The only performance improvement I made was caching intermediate results in a buffer. Perhaps pre-calculating all primes (for row -2 to row +2) in advance could improve the speed some more.

However when I check the result (adding the results for those two numbers) it turns out to be wrong.

I can't see something wrong with my algorithm though. Perhaps it overflows the integer type (long long unsigned int)?

Your results were correct, the sum doesn't overflow even signed 64 bit integers. Try again, but be very sure that you don't have any whitespace in the textfield. If it doesn't work, contact me.

daniel.is.fischer wrote:Your results were correct, the sum doesn't overflow even signed 64 bit integers. Try again, but be very sure that you don't have any whitespace in the textfield. If it doesn't work, contact me.

Thanks!
I found the error (it was in the last addition of those two results), and is now correct!

I'm curious. How did you manage to get that wrong?

My program finds the solution for S(10000) quickly, and a solution for the other two lines not so quickly. Unfortunately their sum is not correct.

My program finds 27438 triplets in line 7208785. A hint as to whether this is high or low would help the debugging process.

Your number is far too large.

Tommy137 wrote:Your number is far too large.

No, his number is too small.

Georg wrote:

Tommy137 wrote:Your number is far too large.

No, his number is too small.

Mhm, I simply changed my code, so that it counts the primes that are a member of a triplet instead of computing the sum. The output was < 10000

Maybe, he meant something else.

Tommy137 wrote:1782¹² + 1841¹² = 1922¹²

what about Fermat's last theorem?

Tommy137 wrote:

Georg wrote:

Tommy137 wrote:Your number is far too large.

No, his number is too small.

Mhm, I simply changed my code, so that it counts the primes that are a member of a triplet instead of computing the sum. The output was < 10000

Maybe, he meant something else.

Ooops. I did not change my program. I read that he computed S(10000) and compared it with the given value. So I did assume that his value was S(7208785) but it is not. I'm sorry, I did not count the triplets. My answer "No, his number is too small." is worthless.

S(200,000) = 8980000676761
S(200,001) = 4040040647250
S(200,002) = 3660072967149
S(500,005) = 134752693946582

Can someone confirm the correctness
or incorrectness of these results to me?

I am trying to find a bug in my code but I cannot see it yet.

I am able to get the answer for S(10,000) but
apparently I am still missing something.

Thanks in advance.

Those are correct.

Thanks for the reply.
I finally found my mistake.

sedefcho wrote:Thanks for the reply.
I finally found my mistake.

Oh my god, I think I have the same mistake you had... Correct results for S(8), S(9), S(10000) <-14 ms., S(200,000-200,002) <- 64sec. and S(500,005) .
I thought fine, lets try it with the real numbers: Incorrect result !!

You know, it hurts a bit after 19.5 hours runtime

Guess my problem are triples at the very end of the row, anyone got a row to compare the results with ?

Gawd!

used accidentally the wrong offset parameter to calculate with which didn't affect the sample results
Well, we'll see... I'll report back in 19.5 plus 4 hours (need my box for other things tonight )

just got the same (wrong) result with my corrected code...

Can anyone confirm the sum of [ S(1), S(2) ... S(10000) ] to be 5572672553494 ?

My code can't handle that and it solves the original problem (now that I've optimized it a bit) in less than one minute. these are specific values for S:

S(100,000) = 549999566882
S(200,010) = 13741374650371
S(150,073) = 4549424035634

If your solution does not work for the values in the problem, but does for values high enough so as not to be causing problems with finding triplets, than probably your prime testing function cannot handle larger numbers or you get overflow at some point.

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

My code can't handle that

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