

A196052


Sum of the degrees of the nodes at level 1 in the rooted tree with MatulaGoebel number n.


3



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



OFFSET

1,3


COMMENTS

The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the MatulaGoebel numbers of the m branches of T.


REFERENCES

D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
E. Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288, 2011
F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

a(1)=0; if n = p(t) (the tth prime), then a(n)=1+G(t), where G(t) is the number of prime divisors of t counted with multiplicities; if n=rs (r,s>=2), then a(n)=a(r)+a(s). The Maple program is based on this recursive formula.


EXAMPLE

a(7)=3 because the rooted tree with MatulaGoebel number 7 is the rooted tree Y.
a(2^m) = m because the rooted tree with MatulaGoebel number 2^m is a star with m edges.


MAPLE

with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then 1+bigomega(pi(n)) else a(r(n))+a(s(n)) end if end proc: seq(a(n), n = 1 .. 110);


PROG

(Haskell)
import Data.List (genericIndex)
a196052 n = genericIndex a196052_list (n  1)
a196052_list = 0 : g 2 where
g x = y : g (x + 1) where
y = if t > 0 then a001222 t + 1 else a196052 r + a196052 s
where t = a049084 x; r = a020639 x; s = x `div` r
 Reinhard Zumkeller, Sep 03 2013
a(n) = my(m=factor(n)); [bigomega(primepi(p))+1  p<m[, 1]] * m[, 2]; \\ Kevin Ryde, Oct 16 2020


CROSSREFS

Cf. A049084, A020639, A001222.
Sequence in context: A131410 A202453 A259529 * A080773 A134598 A325120
Adjacent sequences: A196049 A196050 A196051 * A196053 A196054 A196055


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Sep 27 2011


STATUS

approved



