A358729 Difference between the number of nodes and the node-height of the rooted tree with Matula-Goebel number n.

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

Offset: 1

Author

Gus Wiseman, Nov 29 2022

Keywords

• nonn

Comments

Node-height is the number of nodes in the longest path from root to leaf.

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.

Because the number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n, i.e., A317713(n) (= 1+A324923(n)), is always at least one larger than the depth of the same tree (= A109082(n)), it follows that a(n) >= A366386(n) for all n. - Antti Karttunen, Oct 23 2023

Examples

			The tree (oo(oo(o))) with Matula-Goebel number 148 has 8 nodes and node-height 4, so a(148) = 4.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..100000
• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Positions of 0's are A007097.

Positions of first appearances are A358730.

Positions of 1's are A358731.

Other differences: A358580, A358724, A358726.

A000081 counts rooted trees, ordered A000108.

A034781 counts rooted trees by nodes and height, ordered A080936.

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

MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.

MG core: A000040, A000720, A001222, A056239, A112798.

Cf. A206487, A209638, A316321, A358576, A358577, A358592, A358725, A366386.

Programs

Mathematica

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

PARI

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
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 program given in A109082 by Kevin Ryde, Sep 21 2020)
A358729(n) = (A061775(n)-A358552(n)); \\ Antti Karttunen, Oct 23 2023

Formula

a(n) = A061775(n) - A358552(n).

a(n) = A196050(n) - A109082(n). - Antti Karttunen, Oct 23 2023

Extensions

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