# Göbel's correspondance between rooted trees and natural numbers

In the paper On a 1-1-correspondence between rooted trees and natural numbers by F. Goebel, a correspondence between natural numbers and rooted tree was established via prime factorization.

He defines:

Let $$T$$ be a rooted tree, $$r$$ its root. The connected components of $$T-r$$ are denoted by $$T_1,\dots,T_v$$, where $$v$$ is the degree of $$r$$. The graphs $$T_j$$ ($$j=1,\dots,v$$) obviously are trees, which we transform into rooted trees by defining as the root of $$T_j$$ the vertex of $$T_v$$ which is adjacent to $$r$$ in $$T$$.

Figure 2 (below) shows all rooted trees up to n=45. I do understand all composite numbers, however I fail to understand the structure of how the rooted trees for prime numbers are structured.

Question: What are the rules to get the rooted tree for prime numbers?

• Certainly one obvious pattern is that for the prime numbers $p$, there is exactly one vertex adjacent to the root. If we remove the root, we get another tree associated to some $n < p$. In the examples above, we get the pairs $(p,n)$ equal to $3 - 2, 5 - 3, 7 - 4, 11 - 5, 13 - 6, 17 - 7, 19 - 8, 23 - 9, 29- 10...$ Jun 5, 2021 at 18:44
• So the pattern seems to be that if $p$ is the n-th prime, then you attach the graph associated to $n$. It seems very plausible to me that this will indeed give a bijection. Jun 5, 2021 at 18:45
• Chiming in just to indicate that Göbel discovered this in 1980, independently of David Matula who discovered this in 1968. The natural number for a given rooted tree is often called the Matula number. Jun 6, 2021 at 3:09

The $$n$$th natural becomes the diagram for the $$n$$th prime, e.g., you recover the rooted trees beginning with $$2, 3, 5, 7, 11, 13$$ by looking at this image. Next will be $$17, 19, 23$$, etcetera.