Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
 MacRumors Forums For all you math geeks: we've got a new Mersenne prime!

Feb 12, 2013, 08:09 AM   #26
Oracle1729
macrumors 6502

Join Date: Feb 2009
Quote:
 Originally Posted by Doctor Q the 48th known Mersenne prime, 2^57,885,161 - 1, a 17,425,170 digit number.... A text file with all of the digits of this new prime number would be over 22MB in size! But it makes wonderful bedtime reading.
I find it amusing that you say that. A text file to hold a 17,425,170 digit number would be oh, say about 17,425,171 bytes long give or take a few bytes. From where did you pull your silly little number? Even more interesting is that you could compress this file below 100 bytes including the program to reexpand it without too much trouble.

Quote:
 I find it amusing that they say that the 47th Mersenne prime was discovered over 4 years ago. According to their own logs it was April 12, 2009, which makes it 3.79 years ago. I guess arithmetic was never their strong suit.
Pot, meet the kettle. I guess arithmetic is not your strong suit either.
0
Feb 12, 2013, 08:47 AM   #27
LPZ
macrumors 65816

Join Date: Jul 2006
Quote:
 Originally Posted by Oracle1729 I find it amusing that you say that. A text file to hold a 17,425,170 digit number would be oh, say about 17,425,171 bytes long give or take a few bytes. From where did you pull your silly little number?
And how large would the text file be if commas were used as separators every three digits?
0
Feb 12, 2013, 08:52 AM   #28
SilentPanda
Demi-God (Moderator emeritus)

Join Date: Oct 2002
Location: The Bamboo Forest
Quote:
 Originally Posted by Oracle1729 I find it amusing that you say that. A text file to hold a 17,425,170 digit number would be oh, say about 17,425,171 bytes long give or take a few bytes. From where did you pull your silly little number? Even more interesting is that you could compress this file below 100 bytes including the program to reexpand it without too much trouble.
The number is a little over 22MB because of commas. You end up with 23 million some characters then divide by 1024. The number was likely pulled from the web sites reporting it as being over 22MB because the main file that is out there holding this prime number contains the commas. While your comment is accurate, so is Doctor Q's.

Also, do you have a source that shows you could compress this under 100 bytes along with the program to reexpand it? I'm not asking as a challenge. I'm a programmer and genuinely curious.
__________________
My 24 hour web cam!

Last edited by SilentPanda; Feb 12, 2013 at 09:07 AM.
0
Feb 12, 2013, 09:13 AM   #29
ChristianJapan
macrumors 68030

Join Date: May 2010
Location: 東京
Quote:
 Originally Posted by Oracle1729 Even more interesting is that you could compress this file below 100 bytes including the program to reexpand it without too much trouble.
Now I'm interessted; how you can compress 17m digits in less the 100 bytes; and get it back ? typo ?
Something like Huffman with binary tree would not help; the distribution of members is equal; the tree would be balanced hence no advantage due to different entropies ...
__________________
I support the MacRumors Blood Drive!
1
Feb 12, 2013, 09:24 AM   #30
SilentPanda
Demi-God (Moderator emeritus)

Join Date: Oct 2002
Location: The Bamboo Forest
Quote:
 Originally Posted by ChristianJapan Now I'm interessted; how you can compress 17m digits in less the 100 bytes; and get it back ? typo ? Something like Huffman with binary tree would not help; the distribution of members is equal; the tree would be balanced hence no advantage due to different entropies ...
Yeah that's what I was looking at. Even if you went into double or triple digit numbers I doubt there would be enough repetition to bother storing them in the table. Coding just the single digits doesn't reduce your bits enough on average. I have the file downloaded and have removed all non-digit characters. I compressed it with 7-zip's ultra compression (not that it is optimized for a random distribution of digits at all) and got it to 7,667,712 bytes. 7.6 is a little under half of the 17 million bytes which makes sense. Not sure how to get rid of the other 7,667,612+ bytes to get it under 100 bytes (need room for the decompressor).
__________________
My 24 hour web cam!
0
Feb 12, 2013, 12:06 PM   #31
Oracle1729
macrumors 6502

Join Date: Feb 2009
Quote:
 Originally Posted by ChristianJapan Now I'm interessted; how you can compress 17m digits in less the 100 bytes; and get it back ? typo ? Something like Huffman with binary tree would not help; the distribution of members is equal; the tree would be balanced hence no advantage due to different entropies ...
I honestly didn't mean that comment to be sarcastic, I thought it was obvious in the same spirit as the person who asked how many 0's are in the binary representation (the answer as given above was 0).

I was basically saying that the Kolmogorov complexity was under 100 bytes. I'm a bit surprised you know of Huffman coding but not complexity theory.

My compressed form is 57885161 which is 4 bytes (it fits in a 32-bit integer), and that leaves me 96 bytes to write my decompressor (an assembly program which basically says "convert that many 1's as a binary number to decimal").

I could claim that simply printing that many 1's is a valid decompressor since binary is a valid representation, but since you can do the decimal conversion in under 96 bytes easily enough, it's a moot point.

Edit: By the way, your Huffman tree is not remotely balanced. You're talking about bytes, so you have 256 possible values of which the most common 10 (11 if you insist on using commas) make up all your bytes. Huffman would get a very high compression ratio on that 17 meg text file. I'm actually surprised that 7-zip did as poorly as it did on purely numerical data stored in ascii.

Last edited by Oracle1729; Feb 12, 2013 at 12:12 PM.
0

MacRumors Forums

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules