Factorization into Primes using Gray code and full parity
Isaac
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%2Fsboisse.free.fr%2Fscience%2Fmaths%2Ffactorisation-langlet-code-gray.php&sl=auto&tl=en
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-
RussellE
On Feb 4, 3:31�am, "Isaac" <gro...@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
>
> 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
Isaac
reply embedded below.
"RussellE" <reas...@gmail.com> wrote in message
news:hkvipl$2guo$1...@dizzy.math.ohio-state.edu...
>
> On Feb 4, 3:31�am, "Isaac" <gro...@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:
yes, I recall. You originally said any binary numbering sequence would work
for your function. I'm really surprised why the math group is not
interested in this binary prime factorization method based on gray code and
cyclical parity. Seems amazing to me that there is any connection between
the two. A curiosity at the very least. Why do you think there is no
interest?
>
> 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().
interesting if true. Is there any work out there that digs into patterns or
structures of any binary analysis or transform functions?
>
> 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
>
It would be interesting to know if there is an analytical or theoretical
(tight?) upper bound.
> 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.
I don't recall asking about fixed length clauses. Please explain the
context of my question so I can better understand the relevance of your
response.
Thanks,
Ariel-