Gödel, Göbel, Matula, Mullin, ...

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

AK = Antti Karttunen
JA = Jon Awbrey

catching up on old correspondence,
so this may be a bit out of order.
will try to pare the redundancies.

JA: In 1980, we find the above paper published,
    giving a correspondence between rooted trees
    and natural numbers that is dual, in a sense,
    to the one that I gave between natural numbers
    and planted plane trees.  In summary, we have:

    1.  Recur on Index : N <-> Rooted Trees
    2.  Recur on Power : N <-  Planted Plane Trees
    3.  Recur on Both  : N  -> Riffs <-> Rotes

JA: As given, the 2nd mapping is many-to-one and onto
    from planted plane trees to natural numbers, but
    there is a way to make the 2nd mapping injective,
    at least, I have an old note that claims this,
    but I will need to read it over again first,
    as I'm not as sure as I used to be about it.

AK: Look at A075166, giving a bijection between
    rooted plane trees and natural numbers > 0.

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=075166

| The rooted plane trees encoded here are:
| .....................o...............o.........o...o..o.......
| .....................|...............|..........\./...|.......
| .......o....o...o....o....o.o.o..o...o.o.o.o.o...o....o...o...
| .......|.....\./.....|.....\|/....\./...\|.|/....|.....\./....
| @...... at ......@...... at ......@...... at ......@...... at ......@.....
| 1......2......3......4......5......6......7......8......9.....

AK: was it that what you had in mind then?

oh, strictly speaking, we should be calling these "planted plane trees",
as otherwise you can rotate the branches around the root and transform,
for example, 6 into 9.

i found the two letters that i wrote to martin gardner in 76 & 78,
and will try to extract the gist of them later, but here is a bit:

| The forest primeval:  a correspondence between natural numbers and planted plane trees.
|
| Consider the primes factorization of a number and represent it as the sequence of its
| exponents separated by parentheses, thus, N = (n_1) (n_2) (n_3) ... (n_m), ignoring
| for now the all-zero exponents after some point m.
|
| e.g.:  1 = 2^0 = (),  2 = 2^2^0 = (()),  3 = 2^0 3^2^0 = ()(())
|
| Repeat this process with each exponent in the factorization and with each further
| exponent in 'its' factorization and so on, until zero exponents are reached along
| every path of development.  A zero exponent, having no representation in primes,
| may simply be omitted on the next pass.  For example:
|
| 360  =  (3)(2)(1)  =  ((0)(1)) ((1)) ((0))  =  (()((0))) (((0))) (())
|
|      =  (()(())) ((())) (())
|
|      =  2^(2^0 3^2^0) 3^2^2^0 5^2^0
|
| Thus, parentheses suffice to represent this "involved factorization" of a number.
| But they also represent planted plane trees, if we interpret the exterior space
| as the planter, parenthetical containments as further edges, and contained
| spaces as nodes, e.g.:
|
|        o  o
|        |  |
|      o o  o  o
|       \|  |  |
|        o  o  o
|         \ | /
|          \|/
|           o
|           |
| 360   =   @
|
| In this way, every number may be assigned a unique minimal tree, but
| many trees will share the same number when the "insignificant digits" of
| a factorization are taken into account.  E.g., trees of the following form,
| where an ellipsis represents an arbitrary number of terminal edges, all have
| the number 360:
|
|       o 
 o 

|       |/  |/
|     o o 
 o 
 o 

|      \|/  |/  |/
|       o   o   o
|        \  |  /
|         \ | /
|          \|/
|           o---

|           |
|           @
|
| = 2^(2^0 3^(2^0 3^0 
) 5^0 
) 3^(2^(2^0 3^0 
) 3^0 
) 5^(2^0 
) 7^0 


continued later,

jon awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o