RecursivePrimeDecomposition

As children we 
learn how to count by "1,2,3,4,5,6,7,8,9,10" a little later we learn that there is a "unit
's place" a "ten's place", a "hundred's place" etc...  What we are doing is representing t
he number base ten.  So a number that looks like $abcd = d\cdot 10^0 + c\cdot 10^1 + b\cdo
t 10^2 + a\cdot 10^3$.  

Still later in life we may learn that computers store information in "base-2" or binary.  
Now a number $abcd = d\cdot 2^0 + c\cdot 2^1 + b\cdot 2^2 + a \cdot 2^3$.  
There are other crazy notational systems like RomanNumerals.  We could also consider a pri
me-number decomposition where a number writen $abcd = p_1^a p_2^b p_3^c p_4^d$, where $p_i
$ represents the $i^{th}$ prime.
So there are a lot of possibilities.  Let us consider a few properties of such systems:


The length of the description grows with the size of the number we are trying to descri
be $L(n)$.  
The "memory" needed for each of the base symbols
The "ease of computation" (EOC) in the notational system
The "arbitrariness" of the system
table>





 
Base-1
 
Base-2
 
Base-10
 
RomanNumeral
 
Prime
 
RecursivePrimeDecomposition


 
$\cdot$
 
1
 
1
 
I
 
0
 
$\cdot$


 
$\cdot \cdot$
 
10
 
2
 
II
 
1
 
$(\cdot)$


 
$\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot$
 
1001
 
9
 
IX
 
(0,2)
 
$(\circ,(\cdot))$


 
$\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot$
 
1010
 
10
 
X
 
(1,0,1)
 
$(\cdot,\circ,\cdot)$



It seems that Base-1 is the least arbitrary, least memory intensive, and most iconic way t
o describe a number.  Unfortunately, it's like the "trivial notation" and $L(n) = n$ so it
's pretty ineffecient.  Moreover, computation in base-1 is great for addition: Simply writ
e the two numbers next to eachother!
On the otherhand, Base-2, or binary, is the least arbitrary "non-trivial notation" (at lea
st that is based on an exponential system).  It is not very memory intensive (only 1 and 0
 or $\cdot$ and $\circ$).  Furthermore, computation in binary is pretty easy (for instance
 the simple logic array for addition and the simple left-shift for multiplication).  As fo
r $L(n)$ it looks like all (non-trivial) exponential systems of base-$m$ $L(n) = [\log_m n
] \pm 1$.
Base-10 seems to be the dominant human notational system.  I suppose we have ten "digits" 
(as in numbers) because we have ten "digits" (as in fingers).  It is definitely more memor
y intensive, but not as bad as base-16 or something.  For the most part, computation sucks
.  We have to learn multiplication tables and remember rules like "if you add up the place
s and it's divisible by three then the number is divisible by three" and crap like that.  
The Prime Number Decomposition is cool because the compositeness of the number has been ob
viated and it embraces the number-theoretic properties.  Multiplication is pretty damn eas
y (add the exponents in place), though addition isn't so easy to see.  Unfortunately, it's
 somewhat poorly defined, because to write down the exponents we usually digress to Base-1
0.  An alternative would be to recur the Prime Number Decomposition to the exponents until
 the exponent is simply 1.  This is a neat picture because the number would most easily be
 represented in an $D$-dimensional binary grid where $D$ is the number of recursions it to
ok to decompose the number. This notation's computing properties are quite complicated, bu
t that could be of some utility, it seems, for numbers with particular types of structure.
  Here $L(n)$ is more difficult to express because of the difficulty of describing the pri
mes and the fact that it is not montonically increasing with $n$.  How are these related t
o p-Adic prime numbers ?
More Recursive Prime Decomposition - thanks Sean for the RPDCode
1 1
2 (1,)
3 (0, 1)
4 ((1,),)
5 (0, 0, 1)
6 (1, 1)
7 (0, 0, 0, 1)
8 ((0, 1),)
9 (0, (1,))
10 (1, 0, 1)
11 (0, 0, 0, 0, 1)
12 ((1,), 1)
13 (0, 0, 0, 0, 0, 1)
14 (1, 0, 0, 1)
15 (0, 1, 1)
16 (((1,),),)
17 (0, 0, 0, 0, 0, 0, 1)
18 (1, (1,))
19 (0, 0, 0, 0, 0, 0, 0, 1)
20 ((1,), 0, 1)
21 (0, 1, 0, 1)
22 (1, 0, 0, 0, 1)
23 (0, 0, 0, 0, 0, 0, 0, 0, 1)
24 ((0, 1), 1)
25 (0, 0, (1,))
26 (1, 0, 0, 0, 0, 1)
27 (0, (0, 1))
28 ((1,), 0, 0, 1)
29 (0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
30 (1, 1, 1)
31 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
32 ((0, 0, 1),)
33 (0, 1, 0, 0, 1)
34 (1, 0, 0, 0, 0, 0, 1)
35 (0, 0, 1, 1)
36 ((1,), (1,))
37 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
38 (1, 0, 0, 0, 0, 0, 0, 1)
39 (0, 1, 0, 0, 0, 1)
40 ((0, 1), 0, 1)
41 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
42 (1, 1, 0, 1)
43 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
44 ((1,), 0, 0, 0, 1)
45 (0, (1,), 1)
46 (1, 0, 0, 0, 0, 0, 0, 0, 1)
47 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
48 (((1,),), 1)
49 (0, 0, 0, (1,))
50 (1, 0, (1,))
51 (0, 1, 0, 0, 0, 0, 1)
52 ((1,), 0, 0, 0, 0, 1)
53 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
54 (1, (0, 1))
55 (0, 0, 1, 0, 1)
56 ((0, 1), 0, 0, 1)
57 (0, 1, 0, 0, 0, 0, 0, 1)
58 (1, 0, 0, 0, 0, 0, 0, 0, 0, 1)
59 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
60 ((1,), 1, 1)
61 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
62 (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
63 (0, (1,), 0, 1)
64 ((1, 1),)
65 (0, 0, 1, 0, 0, 1)
66 (1, 1, 0, 0, 1)
67 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
68 ((1,), 0, 0, 0, 0, 0, 1)
69 (0, 1, 0, 0, 0, 0, 0, 0, 1)

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
         47, 53, 59, 61, 67, 71]

def getDecomposition(n):
       from math import sqrt
       factors = {}
       i = 0
       while n > 1:
               if n%primes[i] == 0:
                       exp = factors.get(i, 0)
                       exp = exp + 1
                       factors[i] = exp
                       n = n/primes[i]
               else:
                       i = i + 1
       arr = [0]*(max(factors.keys()) + 1)
       for key, value in factors.items():
               arr[key] = value
       return tuple(arr)

def rdp(n):
       if n < 2:
               return n
       factors = getDecomposition(n)
       if n in primes:
               return factors
       else:
               return tuple(map(rdp, factors))
if __name__ == '__main__':
       for i in range(70):
               print i, rdp(i)




Some or all expressions may not have rendered properly,
because Latex returned the following error:
! Undefined control sequence.
l.49 $|~ abcd = d\cdot 10^0 + c\cdot 10^1 + b\cdo

?