Monday, November 05, 2012

[bontatqy] Consecutive primes product under 64-bit

The first 15 odd prime numbers, namely 3 through 53, form a product just less than 2^64.  10 more (starting from 59) form the next product that fits into 64 bits.  The sequence of cardinalities goes 15, 10, 9, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6,...  This sequence can be run length encoded as (15,1), (10,1), (9,1), (8,2), (7,7), (6,26), (5,131), (4,1408), but the Haskell computer program runs out of memory (space leak) while calculating the next term (3,???).

The practical use for this sequence is initial primality testing or factorization of a very large number by trial division.  First, divide the large number by a product of small primes so that remainder fits into a machine register.  Then test that remainder for divisibility by the small primes using fast hardware arithmetic (as opposed to software arbitrary-precision arithmetic).  Repeat for the next batch of small primes.

Upon further consideration, something involving GCD would probably be better.

No comments: