Waring's Prime Number Conjecture

[lordofall]

Recently I was in the dwite contest and they had a problem that stated this

Waring's Prime Number Conjecture states that every odd number is a either prime or the sum of three primes
Ex.
21 = 7 + 7 + 7
21 = 13 + 5 + 3
21 = 11 + 7 + 3
21 = 11 + 5 + 5
21 = 17 + 2 + 2
33 = 11 + 11 + 11
33 = 13 + 13 + 7
33 = 17 + 11 + 5
33 = 17 + 13 + 3
33 = 19 + 7 + 7
33 = 19 + 11 + 3
33 = 23 + 5 + 5
33 = 23 + 7 + 3
33 = 29 + 2 + 2
23 is prime

we had to create a program that opens a file, reads the first 5 lines of data and prints out how many different combinations can make up that number, or PRIME if the number is prime
the data consist of odd, positive integers between 3 and 99999

To find out if a number is prime i used

code:

function prime (n : int) : boolean     if n < 2 then         result false     elsif n = 2 or n = 3 then         result true     elsif n mod 2 = 0 then         result false     else         for f : 3 .. round (sqrt (n)) by 2             if n mod f = 0 then                 result false             end if         end for         result true     end if end prime

(although i created a case statement that checks for all the 9000+ prime numbers between 1-100000, turing could not operate the program)
this code is pretty fast, and i attached the code for the rest of the program
(sry its undocumented as the contest is run by an online judge and the only goal is to create a program fast that runs.

But when the program runs it has less then a minute to find the answers to the 5 sets of data, including everything from 3-99999.
which means the code has to be very fast since my program ran out of time as 50000+ takes more then a minute easily.
This is how the code operates
1- get the integer from the file. Ex n = 33
2- Is it prime? Yes Exit, otherwise
3- Divide it by 3 and store that in 3 integers
integerOne - 11, integerTwo - 11, integerThree - 11
4) now subtract 2 from the last digit (integerThree) and add it to integerTwo if its smaller then integerOne otherwise add it to integerOne.
integerThree = 9 integerOne = 13 integerTwo = 11
5)now is integer three prime? if yes go through a loop and subtract 2 from integerTwo and add it it to integerOne until both integerTwo and integerThree are equal then go back to step 4. If not go back to step 4

IntegerThree is not prime, goes to step 4, step 4 returns
IntegerOne = 13 integerTwo = 13 integerThree = 7

when integer two and three are prime add one to the counter, so as it repeats the loop

IntegerOne = 13 integerTwo = 13 integerThree = 7 (counter + 1)
IntegerOne = 15 (not prime) integerTwo = 11 integer three = 7
integerOne = 17 integer Two = 9 (not prime) integerThree =7
integerOne = 19 integerTwo = 7 integerThree = 7 counter + 1

now it exits since two and three are equal and goes back to step 4.
After integerThree reaches two it exits the program and prints out the counter.
Unfortunately the code is to slow for large numbers as they may have hundreds or thousands of combinations i believe. As the contset is over I was just wondering if there is any easier way to solve this. Thank You.

[zylum]

they give you 2.5 seconds to finish execution, not a minute

[lordofall]

zylum wrote:

they give you 2.5 seconds to finish execution, not a minute

haha okay then i'm worse off then b4

[thegoose]

I did DWITE and my solution was something like this. My program basically find all primes and kept a list where prime[i]=1 if i is prime. Then I cycled through all combinations of 1st and 2nd primes and checked if the 3rd is prime using the list. This ran in O(N^2) time and with some pruning, ran for 0.125 (or something like that) on the judge's cases. Turing users had a disadvantage with this problem because Turing programs have a big constant and the judge's Turing is old (it's DOS version).

[zylum]

haha, that was my solution but it timed out so i didnt post it

code:

var P : flexible array 1 .. 0 of int var file, out : int open : file, "DATA41.txt", get open : out, "OUT41.txt", put proc seive (var N : array 1 .. * of boolean)     for i : 1 .. upper (N)         N (i) := true     end for     for i : 2 .. ceil (sqrt (upper (N)))         if N (i) = true then             for j : i .. floor (upper (N) / i)                 N (i * j) := false             end for         end if     end for end seive for : 1 .. 5     var n : int     get : file, n     var N : array 1 .. n of boolean     new P, 0     seive (N)     if N (upper (N)) then         put : out, "PRIME"     else         for i : 1 .. upper (N)             if N (i) then                 new P, upper (P) + 1                 P (upper (P)) := i             end if         end for         var counter := 0         for i : 2 .. upper (P)             for j : i .. upper (P)                 exit when upper (N) - (P (i) + P (j)) < P (j)                 if N (upper (N) - (P (i) + P (j))) then                     counter += 1                 end if             end for         end for         put : out, counter     end if end for put Time.Elapsed

i dunno if i can make it run any faster... runs the first data set in 45 seconds on my crappy computer

[lordofall]

thanks for the help =^D (woulda thanked you earlier but fixing all my comps currently) =^D I've never used some of these operators before but i'll spend some time learning them later, unfortunately i ran it against their test input and it took 13 seconds.

[zylum]

yeah well turing sucks... java would run well under 2.5 seconds.

[Drakain Zeil]

I'm not a fan of this "2.5 second" deal. Different computers process it at different speeds, and it is not dedicated fully to it, also, other processes could slow it down by taking over for a moment... ie. some background OS stuff.

I'd think of somthing useful to post, but I'm tired and going to bed..... emoticon:

[Hikaru79]

Drakain Zeil wrote:

I'm not a fan of this "2.5 second" deal. Different computers process it at different speeds, and it is not dedicated fully to it, also, other processes could slow it down by taking over for a moment... ie. some background OS stuff.

Heh. Nobody's a "fan" of it, but if it's a requirement when your program's being marked in a contest, you really have no choice. Although the question of certain hidden processes in the OS affecting programs unfairly when the judges clock it is an interesting one. It's probably not a huge difference, but when the time limit's 2.5 seconds, every quarter-second counts. How *do* they judge it to be sure its fair?

[Drakain Zeil]

You don't. Take that program above, make two statements such as clock(start)as close to the top as you can, ie. before /other/ vars , clock(end) at the end of the program
put end-start after end's measure. Running this several times will show you that there is a difference with the exact same code.

[bugzpodder]

Mr S asked me to write a solution to that problem before the contest and although i didnt time it officially, my C++ solution took a really long time. I seived the primes like what Richard did and then did a N^2 search.

[thegoose]

I just recoded my Pascal stuff in Turing. It ran for 14.618 seconds on a P4 2.8 GHZ computer. The funny thing is that it takes 1.9 seconds to just generate all the prime numbers.


Here is the code:

var prime, ifprime : array 1 .. 100000 of int
var f_in, f_out, primet, tot, n : int;
open : f_in, "DATA41.txt", get;
open : f_out, "OUT41.txt", put;

primet := 1;
prime (1) := 2;
ifprime (1) := 0;
ifprime (2) := 1;
for i : 3 .. 99999
ifprime (i) := 0;
var j, found, stop : int
found := 1;
stop := floor (sqrt (i));
j := 0;
loop
j += 1;
if (prime (j) > stop) then
primet += 1;
ifprime (i) := 1
prime (primet) := i;
exit
end if
if (i mod prime (j) = 0) then
exit
end if
end loop
end for

for a : 1 .. 5
get : f_in, n
var i, j, barrier1, barrier2, n1, k : int;
if (ifprime (n) = 1) then
put "PRIME"
else
i := 0;
tot := 0;
barrier1 := n div 3;
loop
i += 1;
exit when prime (i) > barrier1;
j := i - 1;
n1 := n - prime (i);
barrier2 := n1 div 2;
loop
j += 1;
exit when prime (j) > barrier2;
k := n1 - prime (j);
if (ifprime (k) = 1) then
tot += 1
end if
end loop;
end loop
put tot
put : f_out, tot
end if
end for

close : f_in;
close : f_out;
put "total time:", Time.Elapsed

Conclusion: We should all switch to Pascal.

[Drakain Zeil]

Here's somthing I just noticed I had in my bookmarks for one reason or another, helpful.

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

[thegoose]

Prime search is not really the bottle neck of the problem since it runs in O(Nsqrt(N)) time. The thing is that the search is still O(N^2) which takes most of the time as N approaches large sizes. It seems that Turing does only about 100,000 instructions per second.
The funny thing aobut this problem is that even if there are more than 3 prime numbers, it still can be done in O(KN^2) where K is the number of primes that N is taken apart into(it's 3 in this case). This can be done using DP, see the following link:
http://acm.uva.es/p/v104/10419.html