

A061775


Number of nodes in rooted tree with MatulaGoebel number n.


76



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



OFFSET

1,2


COMMENTS

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).
Each n occurs A000081(n) times.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
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.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

a(1) = 1; if n = p_t (= the tth prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)1.
a(n) = A091238(A091204(n)).  Antti Karttunen, January 2004
a(n) = A196050(n)+1.  Antti Karttunen, Aug 16 2014


EXAMPLE

a(4) = 3 because the rooted tree corresponding to the MatulaGoebel number 4 is "V", which has one rootnode and two leafnodes, three in total.
See also the illustrations in A061773.


MAPLE

with(numtheory): a := proc (n) local u, v: u := n> op(1, factorset(n)): v := n> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011


MATHEMATICA

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]1]]]; Table[a[n], {n, 108}] (* JeanFrançois Alcover, Jan 16 2014, after Emeric Deutsch *)


PROG

(Haskell)
import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n  1)
a061775_list = 1 : g 2 where
g x = y : g (x + 1) where
y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v  1
where t = a049084 x; u = a020639 x; v = x `div` u
 Reinhard Zumkeller, Sep 03 2013
(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]); (1bigomega(n)) + sum(i=1, omega(n), pfs[i, 1]*pfs[i, 2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014


CROSSREFS

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.
Sequence in context: A303660 A290021 A070941 * A225634 A247134 A080604
Adjacent sequences: A061772 A061773 A061774 * A061776 A061777 A061778


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Jun 22 2001


EXTENSIONS

More terms from David W. Wilson, Jun 25 2001
Extended by Emeric Deutsch, Sep 19 2011


STATUS

approved



