The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A061775 Number of nodes in rooted tree with Matula-Goebel number n. 143
 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 Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011. F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143. I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142. I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22. D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273. FORMULA a(1) = 1; if n = p_t (= the t-th 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 Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, 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}] (* Jean-Franç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]); (1-bigomega(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 (Python) from functools import lru_cache from sympy import isprime, factorint, primepi @lru_cache(maxsize=None) def A061775(n): if n == 1: return 1 if isprime(n): return 1+A061775(primepi(n)) return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022 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: A290021 A348020 A070941 * A356384 A225634 A247134 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 30 07:06 EST 2023. Contains 359939 sequences. (Running on oeis4.)