Problem 27 - Theoretical Imporvement

[Supyovalk]

Hello there, I think I found a theoretical vital time improvement to question 27 "Quadratic primes" It relies on the following 2 lemmas: 1.If b is composite OR smaller then 0 then x^2+ax+b returns a non-prime number for x=0 Meaning that the prime sequence for those b already ends at x=0 [Note that in the examples 41 and 1601 are both bigger then 0 and prime] This can remove both the negative numbers AND the composite numbers from the b search. 2.If prime p divides a and b then x^2+ax+b returns a composite number for x=p [Trivial proof since p divides p^2+xp*p+yp] for those ab pairs, the sequence end at most in x=p That means we don't have to check the ab pairs which share a prime factor smaller then the minimum required consecutive sequence (which in our range is at least 39)

[nayuki]

Great points, thanks! I'll have to think about what strategies to include in my solution program.

If you hop over to the "Benchmark" section of the web page you can see that even my stupidly literal solution only takes 96 ms in Java. I find it hard to justify introducing more intelligence and potential bugs in the code.

[Supyovalk]

I mean, there's 168 primes between 1 to 1000. That means that for our range, that's reduces the required ab cases sixfold, and even more if we increase the range. And if we apply the "No similar factor below 39 it could reduce even the a range." Then In theory this program:

Run on all prime 2<=p<=1000:
    Run on all 2<=a<=1000 that aren't multiple of p IF p<39:
        Check for sequence prime of (a,p) and compare to maximum

Could be much faster then original one.

[nayuki]

A more thorough review:

• Excluding negative b is easily justifiable and takes no code to implement, as it only entails changing the start of the search range.

• Checking that b is composite is exactly as hard as checking that x^2+ax+b is not prime for the very first case where x=0, so there's no point in special-casing that. However, this does suggest to reverse the nesting of the loops so that b on the outside, and if b is not prime, then the entire inner loop is skipped.

• The observation about the smallest p dividing both a and b is a good one which I didn't think of myself. But it doesn't seem to help because it seems to be just as hard as checking all the x^2+ax+b for primeness from 0 to p. That is to say, there is no easy way to find the smallest common factor of a and b.

Please note that I am not optimizing only for CPU time or memory. I am also optimizing for human comprehension. My code, as it stands, is clearly correct and is a faithful brute-force translation of the problem statement. Once you introduce these mathematical optimizations, I hold myself accountable to justify and explain them, in English prose and math formulas, in the comments. The speed optimizations you propose will take more lines of English comments to justify than the milliseconds of CPU time it saves. Though, maybe I should apply some optimizations to my Mathematica solution because it does take 21 seconds.

One extreme example is problem 218 where the entire solution "code" is an enormous math essay (in comments), and the answer is 0. https://github.com/nayuki/Project-Euler-solutions/blob/master/java/p218.java?ts=4