Timeline for Project Euler 46: Finding a counterexample to a Goldbach conjecture
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2017 at 12:54 | comment | added | ljeabmreosn |
@jschnei I agree with that asymptomatic time complexity, but for the simple trial division algorithm, each call is at worse O(sqrt(n)) where the sieve is Theta(nloglogn) which is worse. Check out the thread of problem 7 (after you solve it) where the moderator of the site says that sieving with no known upper bound in less efficient.
|
|
| Jul 3, 2017 at 5:16 | comment | added | jschnei | (Basically, this is since 1 log log 1 + 2 log log 2 + 4 log log 4 + ... + M log log M = O(M log log M)). (This isn't even a particularly smart way of doing it; there are smarter ways to just extend the boolean array using the segmented techniques linked above). | |
| Jul 3, 2017 at 5:15 | comment | added | jschnei |
Here is a simple description of the dynamic sieve. Begin by sieving the numbers up to L, for some arbitrarily chosen L. Now, whenever you ask is_prime(n): 1. if n <= L, just output what's stored in the sieve. 2. otherwise, update L to 2*L, sieve the first 2*L numbers, and repeat. If the maximum n for which you call is_prime(n) is M, then you repeat this process at most log M times (since the size of your sieve doubles each iteration). Moreover, the time complexity is dominated by the last iteration, so this still takes time O(M log log M).
|
|
| Jul 3, 2017 at 1:24 | comment | added | ljeabmreosn |
@jschnei I am still a little skeptical of your description of this "dynamic" sieve you have mentioned. As a concrete example, suppose the user calls is_prime(29). Behind the scenes, there is now a boolean array of size 30 where array[29] == True. Now, in the same instance, the user calls is_prime(31). Surely, you could extend the array in amortized O(1) if you are using the right data structure, but how could the algorithm determine if 31 is prime and extend to boolean array if it has the primality of all n <= 29? I can only think of the sieve just starting from scratch.
|
|
| Jul 3, 2017 at 1:17 | comment | added | jschnei | More explicitly, if you end up doing P primality checks and the maximum number we end up checking is M, your algorithm will take time O(Psqrt(M)) doing these checks, whereas any dynamic sieving method will take time O(P + MloglogM). So there is a definite tradeoff between these two methods, but for this problem I suspect sieving pays off. | |
| Jul 3, 2017 at 1:13 | comment | added | jschnei | I can't find an implementation that does exactly what I described, but there is a similar algorithm that goes by names like "segmented sieve" which works via similar principles (e.g. primesieve.org/segmented_sieve.html). The important thing to realize is that you definitely don't have to rebuild the table every time you want to do a new check. You only ever have to extend the table. Of course, if you extend it by a factor of 2 each time, it doesn't matter asymptotically if you just rebuild the whole table instead (and you'll do at most log(max) rebuilds). | |
| Jul 3, 2017 at 1:04 | comment | added | ljeabmreosn |
@jschnei The sieve of Eratosthenes is useful when the numbers in are in some range. But suppose we need to determine if n is prime. Okay, run the sieve. Then, determine if n^2 + 2 is prime. You would then need to rebuild the table which is very inefficient. The trial division algorithm is O(sqrt(n)), Omega(1) whereas the sieve is Theta(nloglogn). It would be nice if you could point me to the dynamic sieve implementation you mentioned!
|
|
| Jul 3, 2017 at 0:40 | comment | added | jschnei | Also I think you should be very careful when calling solutions "optimal" unless you can actually prove they are optimal. (There are faster solutions for this problem, especially if you're willing to trade some time for memory). | |
| Jul 3, 2017 at 0:37 | comment | added | jschnei | It's not at all true that "the sieve of Eratosthenes is only useful if there is a given upper bound". Sieving is useful whenever you want to test primality of a large number of numbers in a (relatively) small range. If you don't know the exact range of the numbers, that isn't an obstacle in and of itself; you can always use a strategy where you double the size of the range and recompute each time you need a larger range (similar to how dynamic arrays are allocated). This will be asymptotically faster. | |
| Jul 1, 2017 at 18:45 | history | edited | ljeabmreosn | CC BY-SA 3.0 |
wrong link
|
| Jul 1, 2017 at 6:56 | vote | accept | Po Chen Liu | ||
| Jul 1, 2017 at 3:23 | comment | added | ljeabmreosn |
So, you need to solve n = p + 2x^2. One possible way (there are others) is to write the equation as p = n - 2x^2. Now, try plugging in x = 0, 1, 2, ... until p is prime. We can stop searching for x when p becomes negative, hence the highest x possible causes n - 2x^2 = 0. Then, solving for x gives x = sqrt(n/2). So if there is no x in the range 0 to sqrt(n/2) satisfying the previously mentioned equation, then there is no solution, meaning n is the answer.
|
|
| Jul 1, 2017 at 2:56 | comment | added | Po Chen Liu | This is a pretty cool approach, but I don't understand what 'for all possible x' means. Especially in 'my implementation'. Everything else makes sense. | |
| Jun 30, 2017 at 22:24 | history | answered | ljeabmreosn | CC BY-SA 3.0 |