Home Original page

Prime number module

Lulu of the Lotus-Eaters mertz at gnosis.cx
Fri Oct 3 01:46:20 EDT 2003 
bokr at oz.net (Bengt Richter) wrote previously:
|I thought primes ran about 10% of all numbers, so 8.3 % seems a little
|suspicious.

The primes become sparser over larger sizes.  Thinking about the Seive
of Erotosthenes makes that apparent, I think:  the larger you get, the
more values get filtered out.

However, your ratios, I believe, *must* be wrong:

|Prime for mask = 3, mask length = 6
|Precompression possible: (6-2 zeroes)/6 => 66.7 % of orig
|Prime for mask = 5, mask length = 30
|Precompression possible: (30-19 zeroes)/30 => 36.7 % of orig
|Prime for mask = 7, mask length = 210
|Precompression possible: (210-163 zeroes)/210 => 22.4 % of orig
[...]

Bracket the Python implementation, just think of the numbers.  If you
have a sequence of N bits, the 2 mask takes out half of them.  What's
left is odd numbers:  exactly 1/3 of which are divisible by 3.  Of the
filtered list, exactly 1/5 of what's left is divisible by 5.  And so
on.[*]

[*] Actually, exact divisibilty can be off-by-one, since the original
sequence might not divide evenly by all those primes.

So, in other words, the 2 mask gets you to 50%; the 2+3 mask gets
1/2*2/3==33%; the 2+3+5 mask gets 1/2*2/3*4/5==27%; the 2+3+5+7 mask
gets 1/2*2/3*4/5*6/7==22.8%; and so on.

Verifying this "experimentally":

  >>> len(filter(lambda n: n%2, range(100)))
  50
  >>> len(filter(lambda n: n%2 and n%3, range(100)))
  33
  >>> len(filter(lambda n: n%2 and n%3 and n%5, range(100)))
  26
  >>> len(filter(lambda n: n%2 and n%3 and n%5 and n%7, range(100)))
  22
  >>> len(filter(lambda n: n%2 and n%3 and n%5 and n%7 and n%11, range(100)))
  21
  >>> len(filter(lambda n: n%2 and n%3 and n%5 and n%7 and n%11 and n%13, range(100)))
  20
  >>> len(filter(lambda n: n%2 and n%3 and n%5 and n%7 and n%11 and n%13 and n%17, range(100)))
  19

Anything that is left over after this filtering is--by definition--of
unknown primality.  You need to encode that by putting a 1 or 0 in the
bit position corresponding to the number remaining.  IOW:

    toEncode = filter(lambda n: n%2 and n%3 and n%5 and n%7, range(10**8)))
    for n in toEncode:
        if isPrime(n):
            bitfield.append(1)
        else:
            bitfield.append(0)

You might want to run that first line on a fast machine with plenty of
memory. :-)

Yours, Lulu...

--
 mertz@  _/_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY: \_\_\_\_    n o
gnosis  _/_/             Postmodern Enterprises            \_\_
.cx    _/_/                                                 \_\_  d o
      _/_/_/ IN A WORLD W/O WALLS, THERE WOULD BE NO GATES \_\_\_ z e
More information about the Python-list mailing list