On Fri, Oct 15, 1999 at 01:03:57AM -0800, Gordon Bower wrote:
> PS - On an unrelated note --- what is the smallest natural number that is
> not known whether it is prime or composite? Surely *someone* out there is
> trying to work from the bottom up and factor every number. (I don't know
> the answer. I am guessing the it is a smallish number of maybe 15 or
> so decimal digits?)
Suppose you were keeping such a list. With one bit (prime vs not-prime) to
represent each number up to 10^15, you would need approximately 10^14 bytes of
storage, which is on the order of 100 terabytes. That would be your first
problem. The second problem would be if you were to present me with the
smallest number that was not factored, I could almost immediately present you
with a factorization (or show that it's prime).
The point is there are so many numbers, it would take far too much time to
determine the character of even the small ones that could individually be
characterized almost immediately.
Here's another argument - suppose the largest unfactored composite was C. How
long did it take to determine the factorization (or primality) of C-2? (C-1
would be even.) Then to factor C would only take a marginally longer amount of
time than it took for C-2. There is no reason you could not complete the
factorization of C.
Greg Hewgill
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
