What would happen if you changed the last three lines from

    answer = list(islice(goldbachCounterExamples(), 2))
print(f'Finished in {round((time() - start_time)/n, 3)} seconds/run.')
print(f'Answer: {answer}')

to 

    answer = islice(goldbachCounterExamples(), 2)
print(f'Finished in {round((time() - start_time)/n, 3)} seconds/run.')
print(f'Answer: {list(answer)}')
 

rabbott wrote:

We didn't have a chance to talk about many alternative Python versions for the Goldbach problem. Here's mine. It should open in Google Colabratory (Jupyter). When I run it, it gets the answer in about 0.17 sec.

Look in particular at how it generates the list of primes. It generates only the ones it needs and then keeps the ones it generates -- so it doesn't have to generate the same prime more than once.

Also, notice that to avoid traversing the list twice, isAPrime uses dropwhile rather than takewhile.

 

I forgot to point out in class but the primality check can be optimized further. Instead of looking for prime number in a linear fashion, we can just check if any prime number <= sqrt(number being checked) exists which is also a factor of the number to be checked (because n*n<=k for any n,k >= 1). This helped a lot in my haskell code, reduced the time down to 0.30 sec, and your code as well performed faster (clocked about 0.12 sec). Even further, we can check for primes only for 6k+1 and 6k-1 numbers (except for 2 and 3), and maybe can perform the primality check by doing binary search over the primes' list. Haven't worked on these though.

Sure. Here is my haskell code. I will post your code too once I will have an access to my system.

Let me try again on explanation part :D

Let N = 36, then these are the possibilities

• p = 3, q = 12; Therefore, p < sqrt(36) < q
• p = 6, q = 6; Therefore, p == q == sqrt(36)

Therefore, it it sufficient to say that there must be one factor of a number N that is less than or equal to sqrt(N). And so, our primality test becomes 

isPrime n = null [p | p <- takeWhile(<= iSqrt n) primes, n `mod` p == 0]

Another way to perform isPrime is to perform binary search over the existing array of prime numbers as long as the largest number in the array is bigger than or equals to the number being checked. This will cut down this check to lg(N). Haven't tried this yet.

AAdryel wrote:

The time to find the Goldbach counter examples should decrease since the conversion to a list is happening after the timer stops. The change should be small, though, since there are only two elements to convert into a list.

Did you try it? I think you will be surprised at the difference in the time.

In your code, there is a prime check in primes_gen():

is_prime = not any(p for p in Primes.primes_list if k % p == 0)

I replaced this and limited the check till sqrt(k) only. 

Edit: Didn't see above comment until I submitted this

I took a different approach for the Python version than most of the people I've talked to. The idea is to iterate through odd numbers (not from a list of odd numbers) and maintain a list of primes (rather than generating one) and a list of "disprove numbers". A while loop with a check for the length of the list of "disprove numbers" is what keeps the code from checking for more than 2 "disprove numbers".

Here's the code. It isn't very elegant or complex (it doesn't use anything from itertools) but it averages out to running in 0.09 seconds.

Thanks Jay! 

Your code actually runs faster (0.07 seconds) when I run it on my computer and not on Colaboratory.

It does look to be conceptually similar, but your use of a generator and islice rather than a while loop seems to be speed it up a bit.