login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Depth of rooted tree having Matula-Goebel number n.
57

%I #64 Nov 28 2022 10:02:10

%S 0,1,2,1,3,2,2,1,2,3,4,2,3,2,3,1,3,2,2,3,2,4,3,2,3,3,2,2,4,3,5,1,4,3,

%T 3,2,3,2,3,3,4,2,3,4,3,3,4,2,2,3,3,3,2,2,4,2,2,4,4,3,3,5,2,1,3,4,3,3,

%U 3,3,4,2,3,3,3,2,4,3,5,3,2,4,4,2,3,3,4,4,3,3,3,3,5,4,3,2,4,2,4,3

%N Depth of rooted tree having Matula-Goebel number n.

%C Another term for depth is height.

%C Starting with n, a(n) is the number of times one must take the product of prime indices (A003963) to reach 1. - _Gus Wiseman_, Mar 27 2019

%H François Marques, <a href="/A109082/b109082.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..5381 from Alois P. Heinz).

%H Emeric Deutsch, <a href="http://arxiv.org/abs/1111.4288">Tree statistics from Matula numbers</a>, arXiv preprint arXiv:1111.4288 [math.CO], 2011.

%H F. Goebel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.

%H I. Gutman and A. Ivic, <a href="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.

%H I. Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publ. Inst. Math., 53 (67), 1993, 17-22.

%H D. W. Matula, <a href="http://www.jstor.org/stable/2027327">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%F a(1)=0; if n is the t-th prime, then a(n) = 1 + a(t); if n is composite, n=t*s, then a(n) = max(a(t),a(s)). The Maple program is based on this.

%F a(A007097(n)) = n.

%F a(n) = A358552(n) - 1. - _Gus Wiseman_, Nov 27 2022

%e a(7) = 2 because the rooted tree with Matula-Goebel number 7 is the 3-edge rooted tree Y of height 2.

%p with(numtheory): a := proc(n) option remember; if n = 1 then 0 elif isprime(n) then 1+a(pi(n)) else max((map (p->a(p), factorset(n)))[]) end if end proc: seq(a(n), n = 1 .. 100); # _Emeric Deutsch_, Sep 16 2011

%t a [n_] := a[n] = If[n == 1, 0, If[PrimeQ[n], 1+a[PrimePi[n]], Max[Map[a, FactorInteger[n][[All, 1]]]]]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, May 06 2014, after _Emeric Deutsch_ *)

%o (PARI) a(n) = my(v=factor(n)[,1],d=0); while(#v,d++; v=fold(setunion, apply(p->factor(primepi(p))[,1]~, v))); d; \\ _Kevin Ryde_, Sep 21 2020

%o (Python)

%o from functools import lru_cache

%o from sympy import isprime, primepi, primefactors

%o @lru_cache(maxsize=None)

%o def A109082(n):

%o if n == 1 : return 0

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

%o return max(A109082(p) for p in primefactors(n)) # _Chai Wah Wu_, Mar 19 2022

%Y A left inverse of A007097.

%Y Cf. A003963, A061775, A091233.

%Y Cf. A000081, A000720, A001222, A109129, A112798, A196050, A290822, A317713, A320325, A324927 (positions of 2), A324928 (positions of 3), A325032.

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

%Y The ordered version is A358379.

%Y For node-height instead of edge-height we have A358552.

%Y Cf. A000108, A055277, A056239, A342507, A358576.

%K nonn

%O 1,3

%A _Keith Briggs_, Aug 17 2005

%E Edited by _Emeric Deutsch_, Sep 16 2011