Comment Feed for Puzzle series: Addition of Four Primes (Posts on Channel 8)

Re: Puzzle series: Addition of Four Primes

Ambica — Mon, 14 Jan 2008 01:56:04 GMT

I did not go through all the posts here. But having read the first few, in continuation to what Trix posted, I think we can check this:

If it is an even number: What Trix says works good(Goldbachs Conjecture)

If it is odd number: subtract 5 from the number. We will be left with 5, even number. 5=2+3, for even number again we can go by the Goldbachs Conjecture.

The smallest number I could think of to express as a combination of 4 primes is 8(2, 2, 2, 2). Lets take the next: 9.

9=5+4

which means 2,3,2,2

so I think this works for all the numbers.

But... I haven't yet checked the efficiency (time and space complexity) of this... will do it next week when I am free again..

Re: Puzzle series: Addition of Four Primes

jaircazarin — Wed, 09 Jan 2008 03:39:18 GMT

Actually I think that my solution is O(n) in the worst case where n is the input number. (without including prime number generation).
OTOH, AlanSpillane solution is O(n^4) as you said again without prime number generation.

Re: Puzzle series: Addition of Four Primes

platinumacetric — Wed, 09 Jan 2008 02:23:46 GMT

Jaircazarin your solution even though it's not brute force it basically working on the same level. the difference is that you initially fill your vector with all possible prime numbers from 0 to 10000000.

even though your program funs flawlessly you wil suffer a huge tax on the for loop to get all prime numbers. now you can solve that by appsing it to a file where you can read the data if it's not found and this will effective reduce your runtime effiency by more than half.in terms of speed both of you guys jaircazarin and AlanSpillane | all have almost the same run time speed you guys are rough about big-oh of log n.

Me personally i prefare Jaircazarin version since it has the possibilty to be very effiecient if data is stored remotely or better yet if the algorithm is called more than once in a program.

I wil try and edit your code and see if i can come up with anything better, but you guys have done a great job on the algorithm

*ok change that jaircazarin you are around big-oh logn and AlanSpillane has about bif-oh n^4

Re: Puzzle series: Addition of Four Primes

jaircazarin — Sun, 06 Jan 2008 03:18:27 GMT

Your solution is the so called brute force approach, check out my solution

http://jaircazarincode.googlecode.com/svn/trunk/Channel8/Puzzle_Series/FourPrimes.cpp

Re: Puzzle series: Addition of Four Primes

jaircazarin — Sun, 06 Jan 2008 03:16:34 GMT

I don't have enough time to explain my algorithm (maybe tomorrow), but here is my implementation.

http://jaircazarincode.googlecode.com/svn/trunk/Channel8/Puzzle_Series/FourPrimes.cpp

Drop me an email<jair.cazarin[at]gmail.com> if somebody have a question.

Re: Puzzle series: Addition of Four Primes

evildictaitor — Sun, 06 Jan 2008 02:54:16 GMT

Here's a thought to chew on:

Given some number K to split into four primes A, B, C and D, these are all going to be near to K/4.

Why not then pair up two numbers (say A and B, C and D) and increase one and decrease the other until both are prime. Since both numbers are significantly smaller than K, you don't need to compute as many primes to start off with, and primes are going to be closer together at K/4 than at K.

And for those of you wanting to make a series of primes, consider using an algorithm like:

public static List<int> PrimeSeries(int K)
    {
        List<int> primeseries = new List<int>();
        primeseries.Add(2);
        bool isPrime;
        for (int i = 3; i < K; i++)
        {
            isPrime = true;
            foreach (int prime in primeseries)
            {
                if (i % prime == 0)
                {// i is divisible by the prime, i.e. is a constant multiple of it, ie. is not prime
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
                primeseries.Add(i);
        }
        return primeseries;
    }

It should be a bit faster, and less memory intensive than the sieve methods for reasonably sized numbers (ones that fit into an int for instance)

Re: Puzzle series: Addition of Four Primes

evildictaitor — Sun, 06 Jan 2008 02:41:20 GMT

@ Trix:

For odd that seems tricky, because "Waring's prime number conjecture, it states that every odd integer is either prime or the sum of three primes." Well, if it is only a sum of 3 primes how can you get 4 out of it?

You can turn one of the primes into two primes.

Eg. 13 = 11 + 2

So for the number

23 = 13 + 7 + 3
= (11 + 2) + 7 + 3

Re: Puzzle series: Addition of Four Primes

AlanSpillane — Sun, 06 Jan 2008 01:30:36 GMT

Ok, before I start I must mention that I have little experience developing complex algorithms but I really enjoy trying to solve them. I have read the above posts and can follow it easily but I wanted to code it first the way I pictured it in my head, and then learn from the approach you guys take. This is definitely the most inefficient solution possible but it’s a starting point for me J

Recently I read an excellent book called “the music of the primes” by Marcus du Sautory and within it he explains the sieve of Eratosthenes. (Here on Wikipedia)

He began by writing out all the numbers from 1 to 1000. He then took the first prime, 2, and struck off every second number on the list. Since all these numbers were divisible by 2, they weren’t prime. He then moved to the next number that hadn’t been struck off, namely 3. He then struck off every third number after 3. Since these were all divisible by 3, they weren’t prime either. He kept doing this, just picking up the next number which hadn’t been struck from the list and striking off all the numbers divisible by the new prime. By this semantic process he produced tables of primes!!

I then found this article on codeproject which shows how to implements it in c#.

Essentially what I did was get all the primes between the 2 and the number entered and store them. I then loop through these adding them up until I get a match. It works for small numbers but VERY POOR for large numbers.

int value = int.Parse(NumbetextBox.Text);

int[] primes = new int[value];

BitArray numbers = new BitArray(value, true);

for (int i = 2; i < value; i++)

if (numbers[i]){

for (int j = i * 2; j < value; j += i)

numbers[j] = false;

}

int numPrimes = 0;

for (int i = 2; i < value; i++)

if (numbers[i])

{

primes[numPrimes] = i;

numPrimes++;

}

for (int k = 0; k < numPrimes; k++)

for (int l = 0; l < numPrimes; l++)

for (int m = 0; m < numPrimes; m++)

for (int n = 0; n < numPrimes; n++)

{

int num = primes[k] + primes[l] + primes[m] + primes[n];

if (num == value)

{

// Output values to screen

break;

}

I realise that this solution is of little use to anyone but I am happy with my first attempt.

Looking forward to what you guys can do.

Re: Puzzle series: Addition of Four Primes

Trix — Sat, 05 Jan 2008 20:29:43 GMT

Hm I see, I wonder if it would be reasonable if excel could do this, i'm guessing not.

Re: Puzzle series: Addition of Four Primes

littleguru — Sat, 05 Jan 2008 20:28:54 GMT

This is a nice puzzle. Trix really has already a good stand with his idea. Trix you could also - instead of writing it in code - use pseudo code, which means you only write down a list of operations that do it... like for example going through a list of numbers and check how many values are uneven looks like this:

numbersOfEven = 0
loop until end of list reached
   get number from list
   check if item value is even
   when even
      numbersOfEven + 1
end loop
return numbersOfEven

Re: Puzzle series: Addition of Four Primes

Miguel — Sat, 05 Jan 2008 19:58:42 GMT

I see, I think your solution is quite good. You have provided more or less a certain number of ordered steps to get the solution.

What is an algorithm? It is a "set of ordered instructions to solve a problem". We have several ways to represent algorithms. We can use natural languages, we can use pseudocode, or we can dive into and use more specific languages like C# or Visual Basic.

At the end, we will find that all of them are "partial" translations of natural (high-level) languages into something that is getting increasingly similar to "machine code", the final result needed in order to compute the problem with a PC.

So, you programmers, now we have one more clue, the verbal reasoning of Trix about a solution to the problem... What about code? Or also, what about a different approach to the problem?

Cheers!

Re: Puzzle series: Addition of Four Primes

Trix — Sat, 05 Jan 2008 19:52:06 GMT

I'm studying to be a chemical engineer, coding is something I'd like to learn but it is like another language, but I'm always just so busy during school. I don't really know much about code, at least I don't think so, but I think with logic I can figure things out, and how I would code something.

Re: Puzzle series: Addition of Four Primes

Miguel — Sat, 05 Jan 2008 19:48:47 GMT

It may be tricky, but I would like all of you to try formalizing and CODING the algorithm. And then, search for the most efficient solution. Most of times, we can think about a problem and consider it is more difficult that the actual level of difficulty.

Intuitive reasoning or demonstration of the problem is more or less easy but we should practice how to translate reasonings and colloquial language into code. This way we are "standardizing" our explanations, then other people could understand, and also we can realize about some tricky aspects...

:-)

Re: Puzzle series: Addition of Four Primes

Trix — Sat, 05 Jan 2008 19:24:04 GMT

This is tricky. I can do evens fine.

First I'd have a list of prime numbers from (2-10000000).

Ok, now I have to look at the input and figure out how to get 4 primes out of it.

If the inputer = even integer I'd use this process:

I'd divide by 2 and work in chunks. Using conjectures will help here.

Example: Input 1000

Divide by 2=500

Hm well that is a rather large even number, but using Goldbachs Conjecture, I know there has to be two numbers that are prime that add up to 500. Using the list of Prime numbers, I would work backwards from 500 down. Selecting from a pool of x < 500 starting from the number closets to 500, I would select 499. I would then subtract this from 500, then see if the result was a prime number. 500-499=1, nope didn't work. If it were not I'd keep going down the list, next is 491. 500-491=9, nope. Next is 487. 500-487=13. Bingo! So from there, I know 487-13-487-13 works.

Example: Input 52

Divide by 2 = 26 Two sets of 26, but 26 is even, not a prime.

Here I would use Goldbach's Conjecture, and note that 26 has to be made up of two primes. From the list of prime numbers, I can figure out that 13+13 is infact 26.

From here I now know that 13-13-13-13 works.

Example: Input 14

Divide by 2 = 7 So two sets of seven make up 14.

Using Goldbach, I know that 7 has two prime numbers that make it up. Using my handy method of using a set list, I would choose the number closets to 7 from the left, which is 5, subtract that from 7, I get 2. 2 = prime 5 = prime. So 2-5-2-5

For odd that seems tricky, because "Waring's prime number conjecture, it states that every odd integer is either prime or the sum of three primes." Well, if it is only a sum of 3 primes how can you get 4 out of it?

My guess is since 2 is a special prime, you could subtract that at the beginning and still end up with an odd. 69-2 = 67. From there you can figure out the 3 that make up 67 and then add 2. I just don't know how to do that yet, I'll think and post back.