13
$\begingroup$

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?

enter image description here

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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...$ $\endgroup$
    – Asvin
    Commented Jun 5, 2021 at 18:44
  • 8
    $\begingroup$ 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. $\endgroup$
    – Asvin
    Commented Jun 5, 2021 at 18:45
  • 6
    $\begingroup$ 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. $\endgroup$
    – Arya McCarthy
    Commented Jun 6, 2021 at 3:09

1 Answer 1

Reset to default
15
$\begingroup$

(I see this in the comments, too, but to ensure this has an actual answer...)

Here are the first fifteen natural numbers after drawing an individual line segment (edge and node) beneath the root: enter image description here As you can see, I also numbered what this change does:

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Of course, one does not need to rely on pattern analysis to discover this. It follows directly from the paper's definition of the number for a given graph. The graphs in which the root has order 1 are exactly those whose associated numbers have exactly one prime factor (of order 1), and that factor is the nth prime, where n is the number assigned to the subgraph obtained by deleting the root of the original and choosing its adjacent vertex as the root of the new graph. $\endgroup$
    – John Bollinger
    Commented Jun 6, 2021 at 16:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .