Express any number as the sum of four prime numbers

Question

I was give a problem to express any number as sum of four prime numbers.

Conditions:

• Not allowed to use any kind of database.
• Maximum execution time : 3 seconds
• Numbers only till 100,000
• If the splitting is NOT possible, then return -1

What I did :

1. using the sieve of Eratosthenes, I calculated all prime numbers till the specified number.

2. looked up a concept called Goldbach conjecture which expresses an even number as the summation of two primes.

However, I am stuck beyond that. Can anyone help me on this one as to what approach you might take?

The sieve of Eratosthenes is taking two seconds to count primes up to 100,000.

Answer 1

There is some serious problem with your implementation of the sieve. I just implemented it in Delphi, and on my Intel Core i7 CPU clocked at 2.93 GHz, the time required is less than one millisecond (0.37 ms)!

I used the following code:

program Sieve;

{$APPTYPE CONSOLE}

uses
  SysUtils, Windows;

const
  N = 100000;

var
  i, j: integer;
  tc1, tc2, freq: Int64;
  Arr: packed array[2..N] of boolean;

begin

  FillChar(Arr, length(Arr) * sizeof(boolean), 1);

  QueryPerformanceFrequency(freq);

  QueryPerformanceCounter(tc1);
  for i := 2 to N div 2 do
    if Arr[i] then
    begin
      j := 2*i;
      while j <= N do
      begin
        Arr[j] := false;
        inc(j, i);
      end;
    end;

  QueryPerformanceCounter(tc2);
  Writeln(FloatToStr((tc2 - tc1)/freq));

  Writeln;

  for i := 2 to 100 do
    Writeln(IntToStr(i) + ': ' + BoolToStr(arr[i], true));

  Writeln('...');

  Readln;

end.

Answer 2

Here is a PHP implementation that runs in under 2 seconds for n = 99999:

function Eratosthenes($number)
{
    static $primes = array();

    if (empty($primes[$number]) === true)
    {
        $sqrt = sqrt($number);
        $primes[$number] = array_merge(array(2), range(3, $number, 2));

        for ($i = 2; $i <= $sqrt; ++$i)
        {
            foreach ($primes[$number] as $key => $value)
            {
                if (($value != $i) && ($value % $i == 0))
                {
                    unset($primes[$number][$key]);
                }
            }
        }
    }

    return $primes[$number];
}

$time = microtime(true);
$number = 99995;
$primes = array();

if ($number % 2 == 0)
{
    $primes = array(2, 2);
}

else
{
    $primes = array(2, 3);
}

$number -= array_sum($primes);

foreach (Eratosthenes($number) as $prime)
{
    if (in_array($number - $prime, Eratosthenes($number)))
    {
        $primes[] = $prime;
        $primes[] = $number - $prime;

        die(implode(' + ', $primes) . ' (' . (microtime(true) - $time) . ')');
    }
}

Of course it won't work with numbers bellow 8 unless you (wrongly) consider 1 as being a prime number.

Answer 3

Just on the subject of the Sieve, here's what I consider an unoptimised, "dumb" implementation:

std::vector<int> primes(int n) {
    std::vector<int> s(n+1);
    for (int i = 2; i * i <= n; ++i) {
        if (s[i] == 0) {
            for (int j = 2*i; j <= n; j += i) {
                s[j] = 1;
            }
        }
    }

    std::vector<int> p;
    for (int i = 2; i <= n; ++i) {
        if (s[i] == 0) {
            p.push_back(i);
        }
    }
    // std::copy(p.begin(), p.end(), std::ostream_iterator<int>(std::cout, ", "));
    return p;
}

For me it runs (with n=100000) in a small fraction of a second.

Answer 4

You can cut down on the range of search needed by noting a simple fact: when you sum up two numbers, the last digit of the sum will be the last digit of the sum of the last digits of the two numbers. For example 2345 + 24323 = 26668 and 5+3=8; If the last digits sum to a 2 digit number, use its last digit eg. 2345+5436=7781 5+6=11 whose last digit is 1.

So, following the algorithm suggested earlier:

1. Compute all primes less than N using the Sieve of Eratosthenes.
2. Tabulate a list of sums of two primes.
3. group into 10 std::set boxes based on last digit
4. Look at the last digit of your number, find the combinations that could make this up (including carry). Use these to limit the range of the search

For example,

1. For a number like 34565, the last digit is 5, the components come from (0,5),(1,4),(2,3),(3,2),(4,1),(5,0),(6,9),(7,8),(8,7),(9,6). Excluding duplicates, we are left with (0,5), (1,4), (2,3), (6,9), (7,8). (Precompute these for all last digits and hardcode into your program).

2. If N is the original number, pick each number M from the "0" box, check if (N-M) is a member of the "5" box etc., for all possible combinations. If so, you have found your answer!

   • Sreenadh

Answer 5

You could still be ok with time. Due to the Goldbach conjecture, Every even Number greater or equal 8 can be expressed as the sum of 2,2, and two further primes. Every odd number greater or equal 9 can be expressed as the sum of 2,3 and two further primes. It shouldn't take too long to figure out the primes.

Edit: Actually, you could speed this up significantly: For any even Number N, find the largest prime that is less or equal N-7 and choose that prime and 3, then look for two further primes to suit your sum. For any odd Number N, find the largest prime greater or equal N-6 and choose it and two, then again choose two primes.

Answer 6

Once you have a list of primes nad a concrete number isn't this a knapsack problem?

N is your capacity and primes are your items. You have a restriction of 4 on items count. I would go about solving this with dynamic programing, which should be quite fast.

Answer 7

If there weren't the limit on the number size (100,000 or less) then your problem isn't guaranteed to have a solution: see the weak Goldbach conjecture.

However most likely it's true, at least for numbers within the range of computational results... are you sure your problem isn't to express any number the sum of at most four primes?

Since 2,3,5,7,11,13,17,19,23 offer lots of possibilities, I would compute the numbers which are expressed as a sum of 3 of those numbers. (e.g. 2+3+5=10, 2+3+7=2+5+7=12, 3+5+7=15, 2+3+11=16, 2+5+11=18, 3+5+11=19, 2+7+11=20, ... 17+19+23 = 59.)

Then take your arbitrary number N, find the nearest prime below that which differs from N by one of the precomputed sums of 3 small primes. If you don't find a solution, try the next nearest prime up to N-59. If that still doesn't work, start adding in other small primes.

Use the knowledge about prime gaps to bound your solution... the largest prime gap for primes below 155921 (greater than 100,000) is 86.

---

p.s. your Sieve of Eratosthenes shouldn't be taking 2 seconds for N=100,000. You only need to check divisors up to the square root of 100,000 = 316.

Answer 8

Here is the recomendation given by the question referenced in my comments:

• Compute all primes less than N using the Sieve of Eratosthenes.
• Tabulate a list of sums of two primes.
• Sort the list.
• Check if there are two numbers in the list that sum to N.
• If so, print out the corresponding four primes.

Answer 9

Any number also includes fractionals, so you couldn't express those as primes either. There's other numbers like 9 that you couldn't do. Without 1 as a prime, you can't control it finely.

I expect that the problem does not have a solution.