Prev: Engineering Vibration 3rd Edition Inman Solutions Manual
Next: JSH: Understanding your worth
From: RussellE on 10 Feb 2010 19:25

On Feb 4, 3:31�am, "Isaac" <gro...(a)sonic.net> wrote:
> Greetings,
>
> I have just come across very interesting work along the lines of my area of
> interest. �Gerard Langlet discovered a very interesting connection between
> his "parity integral", Gray Code, and prime factorization.
>
> Here is a link to his publication in French:http://sboisse.free.fr/science/maths/factorisation-langlet-code-gray.php
>
> Here is a pretty good Google translation (be sure to assemble the whole
> chopped up URL and paste in your browser):http://translate.google.com/translate?prev=hp&hl=en&u=http%3A%2F%2Fsb...
>
> In the article he sets forth a purportedly efficient factorization method
> using a certain gray code based partitioning scheme and a cyclical parity
> function.
>
> Can anyone comment and/or expand on this approach?
>
> Also, is anyone aware of any other work, conjecture, or pertinent
> knowledge/information related to such binary based approaches (e.g., using
> binary codes like gray code) to understanding or analyzing prime numbers?
>
> Thanks!
> Ariel Bentolila-

The method I described in the other post can be used
to derive an IsPrime() function for Gray code:

cba
---
000 = 0
001 = 1
011 = 2
010 = 3
110 = 4
111 = 5
101 = 6
110 = 7

Take the inverse of the non-prime numbers
to create the clauses for the CNF IsPrime():

IsPrimeGray() =
(c+b+a){0} & (c+b+~a){1} & (~c+~b+a){4} & (~c+b+~a){6} =
(c+b) & (~c+~b+a) & (b+~a)

I worked out about a dozen terms of IsPrimeGray().
I didn't see any obvious patterns, but IsPrimeGray()
does look "less random" than than IsPrimeBinary().

There are a LOT of different Gray codes. I'm not sure
we even know how many different Gray codes exist.
http://www.research.att.com/~njas/sequences/A091299

Let IsPrimek() be the IsPrime() function for numbers
with up to k bits. Assume we are using the standard
binary numbering system.

IsPrime3() = (c+b)(~c+a)

Using resolution I get:

IsPrime3() = (c+b)(~c+a)(b+a)

You asked earlier about fixed length clauses.
(b+a) is a fixed length clause of the binary
IsPrime() function.

I can show the clause (b+a) can be derived from
any IsPrimek() function (using binary and k>2).

(b+a) tells us no number of the form "0 mod 4"
can be prime. Using binary, any fixed width
clause reduces to "x mod 2^y" where x is defined
by the clause and y is determined by the highest
order variable in the clause.

This is the best you can do using fixed length
clauses and binary. You can prove things like
no prime is of the form 6 mod 8, 14 mod 16, etc.

I have no idea if one can prove no prime is of
the form "x mod 2^y" where x is odd.

The binary numbering system is good for deriving
statements about powers of 2. You might be
able to prove something about primes of the
form 2^k +- 1 using the binary IsPrime() function.

Gray codes are good for deriving statements
about parity. You asked earlier about the number
of true bits in the binary representations of
primes being evenly distirbuted. You might be
able to derive a relationship like this using
the IsPrimeGray() function.

Don't be surprised if you derive something
simple like no multiple of 4 is prime.



Russell
- 2 many 2 count
 | 
Pages: 1
Prev: Engineering Vibration 3rd Edition Inman Solutions Manual
Next: JSH: Understanding your worth