A358552 Node-height of the rooted tree with Matula-Goebel number n. Number of nodes in the longest path from root to leaf.

1, 2, 3, 2, 4, 3, 3, 2, 3, 4, 5, 3, 4, 3, 4, 2, 4, 3, 3, 4, 3, 5, 4, 3, 4, 4, 3, 3, 5, 4, 6, 2, 5, 4, 4, 3, 4, 3, 4, 4, 5, 3, 4, 5, 4, 4, 5, 3, 3, 4, 4, 4, 3, 3, 5, 3, 3, 5, 5, 4, 4, 6, 3, 2, 4, 5, 4, 4, 4, 4, 5, 3, 4, 4, 4, 3, 5, 4, 6, 4, 3, 5, 5, 3, 4, 4, 5, 5, 4, 4, 4, 4, 6, 5, 4, 3, 5, 3, 5, 4, 5, 4, 4, 4, 4, 3, 4, 3

Offset: 1

Author

Gus Wiseman, Nov 26 2022

Keywords

• nonn

Comments

Edge-height is given by A109082 (see formula).

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

Examples

			The Matula-Goebel number of ((ooo(o))) is 89, and it has node-height 4, so a(89) = 4.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..100000

Crossrefs

Positions of first appearances are A007097.

This statistic is counted by A034781, ordered A080936.

The ordered version is A358379(n) + 1.

A000081 counts rooted trees, ordered A000108.

A055277 counts rooted trees by nodes and leaves, ordered A001263.

Other statistics: A061775 (nodes), A109082 (edge-height), A109129 (leaves), A196050 (edges), A342507 (internals).

Cf. A000040, A000720, A001222, A056239, A112798.

Cf. A206487, A358576, A358589, A358592, A358729.

Programs

Mathematica

MGTree[n_]:=If[n==1,{},MGTree/@If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Table[Depth[MGTree[n]]-1,{n,100}]

PARI

A358552(n) = { my(v=factor(n)[, 1], d=0); while(#v, d++; v=fold(setunion, apply(p->factor(primepi(p))[, 1]~, v))); (1+d); }; \\ (after Kevin Ryde in A109082) - Antti Karttunen, Oct 23 2023

Python

from functools import lru_cache
from sympy import isprime, primepi, primefactors
@lru_cache(maxsize=None)
def A358552(n):
    if n == 1 : return 1
    if isprime(n): return 1+A358552(primepi(n))
    return max(A358552(p) for p in primefactors(n)) # Chai Wah Wu, Apr 15 2024

Formula

a(n) = A109082(n) + 1.

a(n) = A061775(n) - A358729(n). - Antti Karttunen, Oct 23 2023

Extensions

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023