----------------------------------- lordofall Sun Dec 19, 2004 5:45 pm Waring's Prime Number Conjecture ----------------------------------- 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 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 Sun Dec 19, 2004 6:03 pm ----------------------------------- they give you 2.5 seconds to finish execution, not a minute ----------------------------------- lordofall Sun Dec 19, 2004 9:44 pm ----------------------------------- they give you 2.5 seconds to finish execution, not a minute haha okay then i'm worse off then b4 :P ----------------------------------- thegoose Mon Dec 20, 2004 8:19 am ----------------------------------- 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 Mon Dec 20, 2004 1:35 pm ----------------------------------- haha, that was my solution but it timed out so i didnt post it :lol: 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 Wed Dec 22, 2004 9:41 pm ----------------------------------- 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 Wed Dec 22, 2004 11:04 pm ----------------------------------- yeah well turing sucks... java would run well under 2.5 seconds. ----------------------------------- Drakain Zeil Wed Dec 22, 2004 11:49 pm ----------------------------------- 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: :multi: ----------------------------------- Hikaru79 Thu Dec 23, 2004 1:59 am ----------------------------------- 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.:think: How *do* they judge it to be sure its fair? ----------------------------------- Drakain Zeil Thu Dec 23, 2004 8:26 am ----------------------------------- 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 Thu Dec 23, 2004 10:58 am ----------------------------------- 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 Thu Dec 23, 2004 2:03 pm ----------------------------------- 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 Thu Dec 23, 2004 8:14 pm ----------------------------------- 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 Thu Dec 23, 2004 9:26 pm ----------------------------------- 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