

A355661


Largest number of children of any vertex in the rooted tree with MatulaGoebel number n.


2



0, 1, 1, 2, 1, 2, 2, 3, 2, 2, 1, 3, 2, 2, 2, 4, 2, 3, 3, 3, 2, 2, 2, 4, 2, 2, 3, 3, 2, 3, 1, 5, 2, 2, 2, 4, 3, 3, 2, 4, 2, 3, 2, 3, 3, 2, 2, 5, 2, 3, 2, 3, 4, 4, 2, 4, 3, 2, 2, 4, 3, 2, 3, 6, 2, 3, 3, 3, 2, 3, 3, 5, 2, 3, 3, 3, 2, 3, 2, 5, 4, 2, 2, 4, 2, 2, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Record highs are at a(2^k) = k which is a root with k singleton children.
A new root above a tree has a single child (the old root) so no change to the largest number of children, except when above a singleton, so that a(prime(n)) = a(n) for n >= 2.
Terms a(n) <= 1 are paths down (all vertices 0 or 1 children), which are the primeth recurrence n = A007097.


LINKS



FORMULA

a(n) = max(bigomega(n), {a(primepi(p))  p prime factor of n}).
a(n) = Max_{s in row n of A354322} bigomega(s).


EXAMPLE

For n=629, tree 629 is as follows and vertex 12 has 3 children which is the most of any vertex so that a(629) = 3.
629 root
/ \
7 12 tree n=629 and its
 /\ subtree numbers
4 1 1 2
/ \ 
1 1 1


MAPLE

a:= proc(n) option remember; uses numtheory;
max(bigomega(n), map(p> a(pi(p)), factorset(n))[])
end:


MATHEMATICA

nn = 105; a[1] = 0; a[2] = 1; Do[a[n] = Max@ Append[Map[a[PrimePi[#]] &, FactorInteger[n][[All, 1]]], PrimeOmega[n]], {n, 3, nn}]; Array[a, nn] (* Michael De Vlieger, Jul 14 2022 *)


PROG

(PARI) a(n) = my(f=factor(n)); vecmax(concat(vecsum(f[, 2]), [self()(primepi(p)) p<f[, 1]]));


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



