<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2900.2668" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY
style="WORD-WRAP: break-word; khtml-nbsp-mode: space; khtml-line-break: after-white-space"
bgColor=#ffffff>
<DIV><FONT face=Arial size=2>As numbers increase, the density of primes in those
numbers decreases. Beyond a certain point, you would do better to
represent the differences between successive primes p and q based on the
possible values of p mod 2310=2*3*5*7*11. Once you get past 2, 3, 5, 7,
and 11, there are 480 possible values of that a prime, p, mod
2310 can take on (because 480 is phi(2310)). The distance of q from p
among these values can be represented by a 4-bit code in which 0000 means that q
is the next possible number that could be prime; 0001 means q is the second
possible number that could be prime, etc. 1111 could be reserved to mean
the distance among possible values is larger than 15, and successive 1111's
could be used to indicate gaps larger than 30, 45, etc. I've noted that 15
hops along the possible values of prime numbers, i.e. those relatively
prime to 2310, take you an average of 72 numbers. So until you
get high enough that the density of primes approaches 1/72 (which doesn't happen
before 10^31), the average number of bits per prime is only a tiny bit
larger than 4.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Using the bit-map approach, the average number of
bits per prime starts to exceed 4 when the density of primes falls below 1/15,
which happens pretty early in the game -- before 4
million. </FONT><FONT face=Arial size=2>So the break-even point (the
point where the "distance mod-2310" scheme gets better than the
bit-map) occurs about when the primes exceed 4 million.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>I recognize that theory and programming are two
different animals, and that programming a "distance among relative primes
to 2310" scheme has its own set of challenges, such as the ones that have been
mentioned: speed of lookup, speed of manipulating large arrays of primes, etc.
so this scheme may not be at all practical. I'm just throwing it out as an
idea that people might want to consider.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>--Graeme</FONT></DIV>
<DIV><FONT face=Arial size=2> </DIV></FONT>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV>----- Original Message ----- </DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV
style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B>
<A title=pxp@rogers.com href="mailto:pxp@rogers.com">Hans Havermann</A> </DIV>
<DIV style="FONT: 10pt arial"><B>To:</B> <A title=joshua.zucker@gmail.com
href="mailto:joshua.zucker@gmail.com">joshua.zucker@gmail.com</A> </DIV>
<DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=seqfan@ext.jussieu.fr
href="mailto:seqfan@ext.jussieu.fr">seqfan@ext.jussieu.fr</A> </DIV>
<DIV style="FONT: 10pt arial"><B>Sent:</B> Monday, September 19, 2005 11:16
AM</DIV>
<DIV style="FONT: 10pt arial"><B>Subject:</B> Re: tables of p(n) and/or
pi(n)</DIV>
<DIV><BR></DIV>Joshua Zucker wrote:
<DIV><BR class=Apple-interchange-newline>
<BLOCKQUOTE type="cite">
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>The easy compression fits 30 numbers per byte, by using one bit
for</FONT></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>prime/not prime for each of the number equal to 1, 7, 11, 13, 17,
19,</FONT></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>23, 29 mod 30.</FONT></P>
<P style="MIN-HEIGHT: 21px; MARGIN: 0px; FONT: 16px Monaco"><BR></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco size=5>So
it's not 30 primes per byte, but rather 30 numbers.</FONT></P>
<P style="MIN-HEIGHT: 21px; MARGIN: 0px; FONT: 16px Monaco"><BR></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>With that scheme, since pi(3*10^13) is roughly 10^12, it would
take</FONT></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>only (3*10^13)/30 bytes to store the primality of all of them,
so</FONT></P>
<P style="MARGIN: 0px"><FONT style="FONT: 16px Monaco" face=Monaco
size=5>indeed, 1TB is about right (not 10TB as in your corrected
post).</FONT></P></BLOCKQUOTE></DIV><BR>
<DIV>To be fair, I'm not just storing primality, but also relatively fast
recovery of pi(prime) values.</DIV></BLOCKQUOTE></BODY></HTML>