Anyone like playing with prime numbers?
I have a pet hobby at the moment of trying to compress prime numbers. It should be very difficult with very fast decompression times, as they are supossedly unpredictable, without brute force iterative factoring attempts.
So my little task I've set is:
To compress the primes in the first 1000 numbers on the numberline to the smallest number of bytes possible.
It must be decompressed and readable in under 2 seconds (obviously this is dependent on resourses, but its a rule of thumb to prevent simple brute force).
Also the compression algorithm should preferably also work for any given number pattern. Not just primes. But thats just for extra smug points.
Compression time is unrestricted.
WinZip gets it down to about 465 bytes (on disk size is much bigger though).
I'm down to arround 269 [edit: 242] [edit: ~148] [edit: 115]
Anyone know if there are any records for this sort of thing out there?
Anyone want to join me in my challange?
or is this a geekyness too far you guys?
Last edited by Phil Teare on 18 Oct 2007 07:55 pm; edited 2 times in total
Share: 
∞
edit.
...or 42.
http://www.opsi.gov.uk/acts/acts1995/Ukpga_19950050_en_8.htm#mdiv57
Share:
You can procedurally generate them fairly quickly using a sieving algorithm. If you're looking for ~1000 prime numbers, you know that asympotitically pi(x) (the number of prime numbers less than x) is x/log(x). So solve n/log(n)=1000 for n (approximately 9120), allocate an array of that size, then mark all indices that are multiplies of two as composite, then iterate through 3,5,7,9,etc until you hit all the factors of 9120, and then any indices left over must be prime.
I'm sure you could write that program in just a couple lines of code, but that isn't really storing the primes (but I promise you it would run in under 2 seconds).
Share:
Nice. But no smug points. I'm trying to prove that for finite numbers, primes are predictable to a degree beyond iterative factoring (or as you have, by iterative multiplication and then exclusion - but Conan Doyal would like your point 
).
Is there any pattern, that can be stored which is smaller than the data itself, which reduces the work to be done. What you've done is not compress, but iterate quickly. Like I say, nice, but no smug points, and not quite what I'm aiming at...
The difference is your system has a fix number of iterations needed. So I could lower the time limit to exclude your solution. But that shouldn't take from the fact that you've come back with a nice lateral solution.
Share:
every here and there I read discussions about "infinite compression" but nobody ever did it ... except black hole I guess.
Share:
To get all the prime numbers -
Get all numbers in an array for i++ and test by dividing by all previous numbers in array, test for float, if it is a float divide by next number, if you get a whole number result move on, else add to second array. Use the numbers in the second array.
| Quote: |
| Is there any pattern, that can be stored which is smaller than the data itself, which reduces the work to be done. |
Only if it is a reference? You could say get all them prime numbers and simply print out everything in between, hence you would not need to store all of the numbers
Share:
Square root X and round down, ! it and divide X by it.
If X gets smaller then is not prime e.g. 25, square root rounded down is 5, 5! = (1 x 2 x3 x 4 x 5) = 120, 25/120= 5/24 25 has become 5 which is smaller so 25 is not prime.
Share:
Too funny. For any "non math" people this is absolutely funny.
Share:
I was looking around for prime number information online and came across this post. Sorry for bringing such a long dead post back to life.
In any case, I've put together a compression algorithm that works really well for the list of primes up to 1000 (168 distinct primes from 2 to 997). The compressed data size is 56 bytes. That is all.
Share:
| ScottRobisonUS wrote: |
| I've put together a compression algorithm that works really well for the list of primes up to 1000 (168 distinct primes from 2 to 997). The compressed data size is 56 bytes. That is all. |
Sounds good to me, will it unpack in under 2 seconds?
Accessify Forum Administrator ~ Nigel Peck / MIS Web Design
"Everything I say is not meant to be set in stone" - Van Morrison
Share:
| Nigel Peck wrote: | ||
Sounds good to me, will it unpack in under 2 seconds? |
Absolutely. The key is to transform the dataset from the list of primes to the list of differences between the primes. This yields very repetitious data that is easily compressed. My 56 byte claim is based on building a tree for huffman codes and counting the bits. It would be necessary to hard code the tree into the decompressor to get the 56 byte claim. Embedding the information to rebuild the tree would add a certain amount of overhead, but I didn't bother calculating how much it would be. Arithmetic or range encoding could be even more efficient, though I didn't bother trying them.
This approach could be applied in a more general fashion to 'compress' datasets consisting of fixed length words of increasing values, though the level of compression would completely depend on how often each difference appeared.
An example since I don't have code to show:
First you generate your list of primes:
2 3 5 7 11 13 17 19 23 29 31 37
Calculate the difference between each member and it's predecessor (0 is logically the predecessor for 2):
2 1 2 2 4 2 4 2 4 6 2 6
Now encode that stream by whatever algorithm you desire. If nothing else, you can encode the differences in 3 bits each, vs the 6 bits it would require for the primes themselves in this example.
To recover the original primes, decompress the set of differences, then start with zero and add the first difference to get the first prime. Add to that the second difference to get the second prime, and so on.
Share:
Interesting stuff Scott, sounds like a good method to me.Accessify Forum Administrator ~ Nigel Peck / MIS Web Design
"Everything I say is not meant to be set in stone" - Van Morrison
Share:
haha this is one of the weirder hobbies i have ever heard of but i'll give you credit it, you sucked me in and it does looking like fun - i'll give it a go!An excellent online magazine with journalistic opportunities for anyone interested and also great stuff to read! http://www.moonproject.co.uk
Share: