Integers in Terms of Grouping Operators

Using Recursive Prime Factorization and Prime Indexes to Represent Integers in Terms of Grouping Operators

The idea of this program is to represent any integer purely in terms of grouping operators “(” and “)”. These 2 symbols will give a binary representation of the integers. Since the grouping operators will be balanced, we are guaranteed that the density of (‘s and )’s will be equal. Also, since the ) that matches the first ( indicates the end of a number, arbitrary length integers can be strung together without any special “record separator” indicator.

This is accomplished by expressing the number in terms of it’s prime factors, then taking the prime indices of the prime factors, and iterate this procedure until all of the numbers go to 1, whose prime factors are ().  This gives a unique code for each number. For example, the number
18 = ((2)(3)(3)), taking indices: ((1)(2)(2)) (ie. the first prime * by the 2nd prime * 2nd prime).
Take prime factors again: -> ((())((2))((2))), index -> ((())((1))((1))) factor->((())((()))((()))).

It is possible that as the integers get very large, this representation is more compact than a straight binary representation (Log[2,n]), but I can’t prove it and it certainly isn’t true for numbers less than 10^20 or so.
Trying to answer this question led me to an interesting problem, which is “how many prime factors does the number N have?”. How does this function grow with large N?

In[400]:=

PrimeIndex[1] := 0 ; PrimeIndex[n_Integer]/;PrimeQ[n] := PrimePi[n] ;  … ot; “->””, “{“->”(“, “}”->”)”}]] ;

Here is an example of the “prime representation” of a fairly large integer, it’s length and the length of the binary representation. Also it’s possible to show in TreeForm, which is somewhat easier to decode.

n = 1 * Random[Integer, 1000000000000] ; Print[“n “, n] ; t = toGroups[Abs[n]] ; gs … ;, Floor @ Log[2, Abs[n]], ” bits.”] ; (*Print[TreeForm[t]/.Listf] ; *)

n 405565361059

((((())((()))((((())(())(()))))))(((())(())(())(((())(())))((((()))(((())))((((()))))(((((()))((()))))))))))

Length of Prime Representation 108 bits. Binary Representation 38 bits.

The First 30 Integers:

Thread[{Range[30], toGroupsString/@Range[30]}] //TableForm
1     ()
2     (())
3     ((()))
4     ((())(()))
5     (((())))
6     ((())((())))
7     (((())(())))
8     ((())(())(()))
9     (((()))((())))
10     ((())(((()))))
11     ((((()))))
12     ((())(())((())))
13     (((())((()))))
14     ((())(((())(()))))
15     (((()))(((()))))
16     ((())(())(())(()))
17     ((((())(()))))
18     ((())((()))((())))
19     (((())(())(())))
20     ((())(())(((()))))
21     (((()))(((())(()))))
22     ((())((((())))))
23     ((((()))((()))))
24     ((())(())(())((())))
25     ((((())))(((()))))
26     ((())(((())((())))))
27     (((()))((()))((())))
28     ((())(())(((())(()))))
29     (((())(((())))))
30     ((())((()))(((()))))

A simple demonstration that each number has a unique representation. The length of unique strings in the first 10000 integers is 10000: they are each unique.

g =    {} ; Do[AppendTo[g, toGroupsString[i]], {i, 1, 10000}] ; Length[Union[g]]

10000

How does the (length of the string/Log[2,N]) grow with N? It seems to be getting smaller at large N, but it’s difficult to go much further. I need to come up with a way to estimate this from theory.

All credits to Steve Eichblatt.

Posted in Uncategorized