### Matula numbers and rooted trees

In *SIAM Review* volume 10, page 273, D. W. Matula described an interesting
bijection between the set of positive integers and the set of rooted trees.
This is defined by the following algorithm.
Here π*(x)* is the number of primes less than or equal to *x*.

`
matula(n):
create a node(labelled `*n*)
for each prime factor *p* of *n*:
add the subtree matula(π(*p*)), by an edge labelled *p*
return the node

#### exercises

- give an algorithm for the inverse operation
- which values of
*n* give line graphs?
- which values of
*n* give binary trees? [hint]

#### size, depth and width

The *size* is the number of nodes.
The *depth* of a rooted tree is the maximum distance from the root to a leaf.
The *width* of a rooted tree is the number of leaves.

The plot shows the depth and width of the tree matula(n).

Exercise: how fast do these functions grow? Here is some more data for
inspiration. For size and depth, the values of *n* corresponding to
the first increase to a new maximum are labelled.

#### diagrams of the trees

Here are the Matula trees for *n* from 1 to 100. The edges are
labelled by the prime factors. Leaves are denoted by circles.

Hint to exercise 3: Matula(n) is a binary tree for n=4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, ... .