(Codewars) Goldbach's Conjecture (by @rsalgado) in Ruby

Question

^{Link to kata: link
Rank: 6 kyu
Kata author: @rsalgado}

I have been recently learning Ruby-lang and have been attempting to solve the following kata from Codewars involving Goldbach's Conjecture:

Goldbach's Conjecture is amongst the oldest and [most] well-known unsolved mathematical problems out there. In correspondence with Leonhard Euler in 1742, German mathematician Christian Goldbach made a conjecture stating that:

"Every even integer greater than 2 can be written as the sum of two primes"

which is known today as the (strong) Goldbach conjecture.

...

Your task is to implement the function in the starter code, taking into account the following:

1. If the argument isn't even [or isn't] greater than 2, return an empty array/tuple.
2. For arguments even and greater than 2, return a two-element array/tuple with two prime numbers whose sum is the given input.
3. The two prime numbers must be the farthest ones (the ones with the greatest difference).
4. The first prime number must be the smallest one.

The following test cases are given in the description and in the example test cases:

check_goldbach(2)  == []
check_goldbach(4)  == [2, 2]
check_goldbach(5)  == []
check_goldbach(6)  == [3, 3]
check_goldbach(8)  == [3, 5]
check_goldbach(10) == [3, 7]
check_goldbach(14) == [3, 11]
check_goldbach(15) == []
check_goldbach(24) == [5, 19]

From my testing, it seems that the random tests include numbers in the range$$10^5\le\text{input}\lt10^9$$although I'm not entirely sure.

Here is my current solution that gets Time Limit Exceeded:

def check_goldbach num
    """
    The strong Goldbach's Conjecture is stated
    as follows:
    - Every even integer greater than 2 can
      be written as the sum of two primes.
    
    This was conjectured by German mathematician
    Christian Goldbach in 1742 in correspondence
    with Leonhard Euler.
    ==========================================
    `check_goldbach` is a function that takes
    in an integer `num` and returns either of
    - An empty array, if `num` is odd, is less than
      or equal to 2, or if the strong version of
      Goldbach's Conjecture is False.
    - An array of two integers [i, j], where `i` and `j`
      are both prime, `i + j == num` and `i <= j`.
    ==========================================
    We do this by first using a prime number sieve to
    generate an array of prime numbers. Then, for each
    prime number `i` in the range [2, sieve.length / 2],
    we check if `num - i` is prime.
    
    If it is, then we return `[i, num - i]`. However,
    if Goldbach's conjecture is false (we have checked
    all of the numbers in the list and `num - i` is never
    prime), we finally return an empty array.
    ==========================================
    Examples:
    
    puts check_goldbach(2)  # []
    puts check_goldbach(4)  # [2, 2]
    puts check_goldbach(5)  # []
    puts check_goldbach(6)  # [3, 3]
    puts check_goldbach(8)  # [3, 5]
    puts check_goldbach(10) # [3, 7]
    puts check_goldbach(14) # [3, 11]
    puts check_goldbach(15) # []
    puts check_goldbach(24) # [5, 19]
    """
    # If the input is odd or not greater than 2.
    if num % 2 == 1 or num < 3
        return []
    end
    
    sieve = Array.new(num, true)
    # By definition, 0 and 1 are not prime.
    sieve[0] = sieve[1] = false
    
    # If some `i` = `p*k` for prime `p` and
    # `k > 1`, then `i` is not prime.
    (4...num).step(2) {|i| sieve[i] = false}
    (3...Math.sqrt(num).to_i).step(2) do |i|
        if sieve[i]
            (i*i...num).step(2*i) {|j| sieve[j] = false}
        end
    end
    
    # For each prime `i` in the interval `[2, sieve.length / 2]`,
    # we check if `num - i` is also prime.
    
    # We select the primes from 2 up to including `sieve.length` / 2
    # as then we don't have to take more prime numbers than we need,
    # since we are not modifying the sieve itself.
    primes = (2..sieve.length / 2).select {|i| sieve[i]}
    primes.each do |i|
        if sieve[num - i]
            return [i, num - i]
        end
    end
    
    # The conjecture is false, likely will never happen.
    puts "The conjecture is false for input #{num}."
    return []
end

My question is: How can I improve the execution speed of the function?

While I am currently passing all 8 static test-cases (that is, the smaller test-cases in the full test suite) in around 2-3.5 milliseconds, I still usually only pass 2 to 4 random test-cases in the other 11.996 to 11.998 seconds before timing out, depending on how large the random numbers are.

Answer 1

Using a prime sieve isn't always useful

It ends up taking a LOT of memory, and consequently a lot of time to generate large arrays and then iterate through them to create the sieves.

Instead I could have just written a simple prime checker like so:

def is_prime num
    if num < 2
        return false
    end
    
    if num == 2 or num == 3
        return true
    end
    
    (2..Math.sqrt(num).to_i + 1).each do |i|
        if n % i == 0
            return false
        end
    end
    
    return true
end

since I don't necessarily need to know what numbers in the range (0..n) are prime.

And then I could just check (if num != 2 and num % 2 == 0) for each possible_prime in the interval [2, num / 2] to check if both possible_prime and num - possible_prime are both prime numbers.

In total, making these changes causes the code to be successful on all tests in a total time of 56.3841 milliseconds (server side).

Final iteration of the code:

def is_prime num
    if num < 2
        return false
    end

    if num == 2 or num == 3
        return true
    end

    (2..Math.sqrt(num).to_i + 1).each do |i|
        if n % i == 0
            return false
        end
    end

    return true
end

def check_goldbach num
    """
    The strong Goldbach's Conjecture is stated
    as follows:
    - Every even integer greater than 2 can
      be written as the sum of two primes.
    
    This was conjectured by German mathematician
    Christian Goldbach in 1742 in correspondence
    with Leonhard Euler.
    ==========================================
    `check_goldbach` is a function that takes
    in an integer `num` and returns either of
    - An empty array, if `num` is odd, is less than
      or equal to 2, or if the strong version of
      Goldbach's Conjecture is False.
    - An array of two integers [i, j], where `i` and `j`
      are both prime, `i + j == num` and `i <= j`.
    ==========================================
    We do this by first using a prime number sieve to
    generate an array of prime numbers. Then, for each
    prime number `i` in the range [2, sieve.length / 2],
    we check if `num - i` is prime.
    
    If it is, then we return `[i, num - i]`. However,
    if Goldbach's conjecture is false (we have checked
    all of the numbers in the list and `num - i` is never
    prime), we finally return an empty array.
    ==========================================
    Examples:
    
    puts check_goldbach(2)  # []
    puts check_goldbach(4)  # [2, 2]
    puts check_goldbach(5)  # []
    puts check_goldbach(6)  # [3, 3]
    puts check_goldbach(8)  # [3, 5]
    puts check_goldbach(10) # [3, 7]
    puts check_goldbach(14) # [3, 11]
    puts check_goldbach(15) # []
    puts check_goldbach(24) # [5, 19]
    """
    # If the input is odd or not greater than 2.
    if num % 2 == 1 or num < 3
        return []
    end
    
    possible_prime = 2
    while possible_prime <= num / 2
        if is_prime(possible_prime)
            if is_prime(num - possible_prime)
                return [possible_prime, num - possible_prime]
            end
        end
        
        possible_prime += 1
    end
    
    puts "The conjecture is false for input #{num}"
    return []
end

Answer 2

N ≥ 6 would have to be the sum of two odd primes. An odd number x is prime with probability about 2/ln x. X and n - x are two primes with probability about 1 / ln² n, so you need to examine about ln² n pairs of numbers to find a pair of primes.

So that shows that creating a sieve of size n is very inefficient. It takes n steps when you usually need just ln² n. So create one sieve for the numbers cxln² n and one for the numbers n - cx ln² n to n. Experiment to find a “c” that usually finds a solution, and if it doesn’t work then repeat with 2c instead of c.

Now if you wanted to check all even 6 ≤ N ≤ 10⁹ then you would create one large sieve.