Prime Factor Coding Challenge

[shoneill]

Hey, be careful throwing clues around like that.... 😉

The difference reaches max 206 up to the required 5.7 million primes.  😄

One of my versions used this, but I've ditched it since then......

This is INDEED a way to do things, but whether it's the best?  I also think an array of 5.7 million prime gaps (Even if they're U8) will disqualify the VI from the actual competition.  Bruce has already said that generating the primes is supposed to be a major part of the challenge......

Also, I believe that the primes UP TO 2.4 million (i.e. the prime is equal to or smaller than 2.4 million) are being calculated, making things even worse.  This means that the actual primes generated are all less then 2.4 million.  Have I understood correctly guys?

Shane.

[Ben]

Shane said "Hey, be careful throwing clues around like that.... "

Speaking as a Math Wimp let me say " I need all of the clues I can get!"

I am not sure how I can use that info because it seems I would still have to check the candidates and that is what takes so much time.

The "old-school" example I posted will do up to 100M but it takes 10 minutes to do so. I also came up with a candiate for the most creative use of color catagory that will give me all of the primes less than 1M in about 2.5 seconds. It adheres to the rules of the game but not to the intent. Can anyone explain what the relation between wood grain and prime numbers is?

Ben

Message Edited by Ben on 10-10-2005 08:36 AM

[m3nth]

---

This is INDEED a way to do things, but whether it's the best?  I also think an array of 5.7 million prime gaps (Even if they're U8) will disqualify the VI from the actual competition.  Bruce has already said that generating the primes is supposed to be a major part of the challenge......

---

I don't see why it would disqualify under the given rules.  You're still generating the prime numbers.  Whether you use an array of data or a formula is a technicality since you are meeting the requirement not to actually store the prime numbers themselves.

I also don't see how you're going to find a faster way to generate one data set from scratch.... index the array into a for loop with a single add instruction and index the array out... wa la... you wind up with an array of prime numbers where there was none before, from a much smaller array of pre-calculated differences.

---

Also, I believe that the primes UP TO 2.4 million (i.e. the prime is equal to or smaller than 2.4 million) are being calculated, making things even worse.  This means that the actual primes generated are all less then 2.4 million.  Have I understood correctly guys?

---

I may be thinking backwards about this, but why is that "making things even worse"?

Say you store the difference in a U8 array.  That means one byte per prime # you want to generate.  For all primes < 2.4Million, there are ~180k, so your VI size should be 180k + Other overhead, say it comes out to ~200k.  Not bad.  For all primes < 100Million however, there are ~5.7M, so VI size will be almost 6 megs... big difference.

So I'm still not sure where the 2.4 million # came from, but that's extremely feasible to store a difference array for, whereas generating primes up to 100 million is not so feasible in terms of disk storage space.

[altenbach]

---

@shoneill wrote:
Hey, be careful throwing clues around like that.... 😉

The difference reaches max 206 up to the required 5.7 million primes.  😄

---

Clues...clues...clues... 😮

Yes, the 2.4M sub-problem was introduced by Chaos and has been used to gauge the prime generation portion of the problem. It is a quick way to compare relative speeds without polluting the times with the factoring, etc. I now typically test new algoritms with the Chaos limit, because it is quicker and involves less memory.

So, how small can you make a VI with the difference method? Sure the maximum difference is 206 but if you handle the first point seperately, you can throw away one bit, since they are all even. Still, you would need 5.7 x 7 bits, and you would not be able to go below a ~5MB VI. Bruce will throw it out! (For the Chaos problem, you could get away with 6bits/prime).

Instead of vague limits on the number of pre-recorded primes, we should simply place an upper limit on the VI size, in particular the "data" portion before the VI is run the first time!

[BruceAmmons]

I have learned from judging other competitions that the "spirit of the rules" is as important as the written rules.

I would disqualify the "difference" table.  This is simply converting a table of prime numbers from one form to another, so I would consider it to be a table of prime numbers.  My definition of generating prime numbers is using some sort of algorithm to create the list, not just table conversions.

I don't want to set any specific limits, but I would be likely to disqualify any entries that are larger than 1 MB.  This would either be very inefficient coding or there is a large table hidden somewhere in the code.

Bruce

[altenbach]

---

@Ben wrote:

Can anyone explain what the relation between wood grain and prime numbers is?

---

Well, before you paint your wood panels, you apply the primer directly to the wood grain. 😄

[Ben]

Nice come back Christian!

Well that I know that Bruce will not permit my hack due to the "spirit of the rules" and because it violates your data size restriction, I should show my cards.

I dumped all of the primes less than 100M into a picture constant on the diagram. Technically speaking a picture is not an array.  When shaped as as a rectangle who's sides are the SQRT of the # of primes, the picture ends up looking just like wood grain!

I'd post it but the Exchange does not tolerate 21M attachements.

Well, I ain't done yet but I starting to shake.

Ben

[m3nth]

---

@Ben wrote:

I'd post it but the Exchange does not tolerate 21M attachements.

---

Post a screenshot.  Sounds interesting 🙂

[Ben]

As requested.

5.7M of primes mapped as pixel colors and saved as a diagram constant.

Actual image size is 2772 X 2772.

Ben

Message Edited by Ben on 10-10-2005 04:06 PM

[shoneill]

Nice,

I don't know what type of wood that would be, but it looks like a prime piece to me.... 😄

You know that there IS actually a field of Prime number theory dealing with exactly this kind of thing.  I've never heard of anyone referring to wood grain, but the heart of the matter is really the stuff of algebra theory.

I guess you knew all that though 😉

In fact, I my "new" algorithm is based on some thing similar.  I just need to get around to actually implementing it.

Shane.