Prev: Draft paper submission deadline is extended: TMFCS-10, Orlando, USA
Next: all pathes with bounded length
From: RussellE on 14 Feb 2010 20:20
I describe a set of Boolean functions, IsPrimek(),
which take a k-bit binary number and return True
if the number is a prime. I show parts of these
functions can always be reduced to a simple form
and other clauses are somewhat reducible.

To create a CNF IsPrimek() function, make a list
of all k-bit numbers that are composite. Invert
the bits in these numbers to create a k-clause.
These clauses form IsPrimek().

Consider 2-bit binary numbers.

IsPrime2() = (b1+a1){0) & (b1+a0){1} = (b1)

To create IsPrimek+1 from IsPrimek, add the
k'th variable to every clause in IsPrimek(),
then add clauses for every composite number
with the k'th bit equal to 1.

IsPrime3() = (c1+b1) & (c0+b1+a1){4} & (c0+b0+a1){6}
= (c1+b1) & (c0+a1) & (b1+a1)

We can always use resolution and subsumption to
reduce a Boolean expression.

Any CNF clause can be considered a modulo
function of the form (x mod 2^j), where j is the
first power of two greater than the highest order
variable in the clause, and x is determined by
the clause and may be more than one number.

The clause (b1+a1) says no binary number with
the lowest two bits set to 0 can be prime.
We can rewrite this as:

(b1+a1) -> any number (0 mod 4) is not prime

Certain clauses are "closed". A clause is closed if
it is fixed width and can be derived from every
IsPrimek() function greater than some k.
The clause (b1+a1) is a closed clause.

Consider IsPrime4().
Add the variable D to every clause in IsPrime3().

IsPrime4() = (d1+c1+b1) & (d1+c0+a1) & (d1+b1+a1) + ...

We know no multiple of 4 is prime. Combine (d1+b1+a1)
with the clauses for 4, 8, and 12:

(d1+b1+a1) & (d1+c0+b1+a1){4} & (d0+c1+b1+a1){8} & (d0+c0+b1+a1){12}
= (b1+a1)

The clause (b1+a1) can be derived from every IsPrimek()
for k>2. The IsPrime3() clause (c0+a1) is also a closed clause.
(b1+a1) and (c0+a1) are part of a series of closed 2-clauses
that can be derived from every IsPrimek() function:

(b1+a1)(c0+a1)(d0+a1)(e0+a1)...(k0+a1)

These clauses remove all multiples of 2, except 2.

(b1+a1) -> any number (0 mod 4) is not prime
(c0+a1) -> (4,6 mod 8) is not prime
(d0+a1) -> (8,10,12,14 mod 16)
etc.

Clauses that are not closed are open. As far as I can tell,
all clauses for odd, composite numbers are open.
Open clauses will add variables as we increase k.
We do not always have to add every variable to an open clause.
Consider the IsPrime3() clause (c+b).

(c+b) -> (0,1 mod 8) is not prime

We know every number (0 mod 8) is composite.
But, there are lots of numbers (1 mod 8) that
are prime so we will have to add variables to
the open clause (c+b) as we add variables to IsPrime().
There are also a lot of composite numbers (1 mod 8).

IsPrime4() = (d1+c1+b1) & (~d1+c1+b1+~a1) & (b1+a1) & ...
= (c1+b1) & ...

We don't have to add d1 to (c1+b1) because 9 is composite:
Now that we have four variables:

(c1+b1) -> (1,9 mod 16) is not prime

16+1 is prime so we have to add e1 for IsPrime5():

(e1+c1+b1) -> (1,9 mod 32) is not prime

The next power of two such that 2^j+1 and 2^j+9 are both
composite is 2048 in IsPrime12().

(1,9,2049,2057 mod 4096) is not prime.

All of the following numbers are composite:
4096+1, 4096+9, 4096+2049, 4096+2057

(1,9,2049,2057,4097,4105,6145,6153 mod 8192) is not prime.

8192+4097 = 12289 which is prime.
We have to add a variable for 16384.

(1,9,2049,2057,4097,4105,6145,6153 mod 16384) is not prime.

The next smallest odd composite number after 9 is 15.

(15 mod 16) is not prime.
(15,143 mod 256)
(15,143,527,655 mod 1024)


Russell
- 2 many 2 count
 | 
Pages: 1
Prev: Draft paper submission deadline is extended: TMFCS-10, Orlando, USA
Next: all pathes with bounded length