A355661 Largest number of children of any vertex in the rooted tree with Matula-Goebel number n.

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

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

Kevin Ryde, Table of n, a(n) for n = 1..10000

Index entries for sequences related to Matula-Goebel numbers

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:
seq(a(n), n=1..100);  # Alois P. Heinz, Jul 14 2022

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

Cf. A001222 (bigomega), A354322 (distinct subtrees).

Cf. A007097 (indices of <=1).

Cf. A355662 (minimum children).

Sequence in context: A052304 A049874 A060501 * A109129 A304486 A188550

Adjacent sequences: A355658 A355659 A355660 * A355662 A355663 A355664

Keyword

nonn

Author

Kevin Ryde, Jul 14 2022

Status

approved