Thread: Prime numbers
View Single Post
Old 2008-11-07, 15:25   #5
retina's Avatar
"The unspeakable one"
Jun 2006
My evil lair

188516 Posts

Originally Posted by xilman View Post
In principle it could be stored in a single hydrogen atom.

Think about it before I reveal the answer.
Naively we might try to encode all the possible values as a bitmap. Then consider the bitmap as a single large number with 2512 bits. Then attempt to encode the number in some fashion into the hydrogen atom. But I feel that this approach severely stretches the bounds of credibility and practicality.

Perhaps a better idea is to take into account the fact that no other restrictions have been given with regard to the encoding algorithm. So a better algorithm would seem to be to encode the log512 of the required bit count of largest prime to generate. The the generation algorithm would simply return all the primes less then or equal to this value. This means that the required largest prime that we need to generate has a bit count of 512, meaning we need to generate all primes up to 2512. So we store the log512(512), or simply 1. Where 1 means to generate all the primes up to 2512[sup]1[/sup]. If we were to store 2 in the hydrogen atom then instead we would generate primes up to 2512[sup]2[/sup].
retina is online now   Reply With Quote