A358552 - OEIS

%I #19 Apr 15 2024 02:01:07

%S 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,

%T 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,

%U 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

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

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

%C 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.

%H Antti Karttunen, <a href="/A358552/b358552.txt">Table of n, a(n) for n = 1..100000</a>

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

%F a(n) = A061775(n) - A358729(n). - _Antti Karttunen_, Oct 23 2023

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

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

%t Table[Depth[MGTree[n]]-1,{n,100}]

%o (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

%o (Python)

%o from functools import lru_cache

%o from sympy import isprime, primepi, primefactors

%o @lru_cache(maxsize=None)

%o def A358552(n):

%o     if n == 1 : return 1

%o     if isprime(n): return 1+A358552(primepi(n))

%o     return max(A358552(p) for p in primefactors(n)) # _Chai Wah Wu_, Apr 15 2024

%Y Positions of first appearances are A007097.

%Y This statistic is counted by A034781, ordered A080936.

%Y The ordered version is A358379(n) + 1.

%Y A000081 counts rooted trees, ordered A000108.

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

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

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

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

%K nonn

%O 1,2

%A _Gus Wiseman_, Nov 26 2022

%E Data section extended up to a(108) by _Antti Karttunen_, Oct 23 2023