Saturday, January 26, 2013

[zvtfiqya] Recursive prime predecessor factorization notation

Every prime number can be unambiguously written with the following grammar: P = 2 | ( 1 + P P P ... ) where the second arm requires the factorization of P-1.  Then every integer greater than 1 can be written P P P ...  Requiring prime factorizations to be in numerical order from least to greatest makes the notation for every number unique.

This suggests a ternary representation using the three terminals 2 ( and ), dropping the "1 +" because it is redundant information in the presence of parentheses.

Many previous posts. Recursively factoring P-1 is classically used to prove primality using generators.

2 = 2
3 = (2)
4 = 22
5 = (22)
6 = 2(2)
7 = (2(2))
8 = 222
9 = (2)(2)
10 = 2(22)
11 = (2(22))
12 = 22(2)
13 = (22(2))
14 = 2(2(2))
15 = (2)(22)
16 = 2222
17 = (2222)
18 = 2(2)(2)
19 = (2(2)(2))
20 = 22(22)
21 = (2)(2(2))
22 = 2(2(22))
23 = (2(2(22)))
24 = 222(2)
25 = (22)(22)
26 = 2(22(2))
27 = (2)(2)(2)
28 = 22(2(2))

There are never two consecutive open parentheses, so perhaps omit the first 2 after an open parenthesis.  Perhaps omit the final string of consecutive trailing close parentheses.  Compressed notation:

2 = 2
3 = (
4 = 22
5 = (2
6 = 2(
7 = ((
8 = 222
9 = ()(
10 = 2(2
11 = (2(2
12 = 22(
13 = (2(
14 = 2((
15 = ()(2
16 = 2222
17 = (222
18 = 2()(
19 = (()(
20 = 22(2
21 = ()((
22 = 2((2
23 = (((2
24 = 222(
25 = (2)(2
26 = 2(2(
27 = ()()(
28 = 22((

49 = (())(( is the first number where a close parenthesis is not immediately followed by an open.