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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A109129 Width (i.e., number of non-root vertices having degree 1) of the rooted tree with Matula-Goebel number n. 75
0, 1, 1, 2, 1, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 4, 2, 3, 3, 3, 3, 2, 2, 4, 2, 3, 3, 4, 2, 3, 1, 5, 2, 3, 3, 4, 3, 4, 3, 4, 2, 4, 3, 3, 3, 3, 2, 5, 4, 3, 3, 4, 4, 4, 2, 5, 4, 3, 2, 4, 3, 2, 4, 6, 3, 3, 3, 4, 3, 4, 3, 5, 3, 4, 3, 5, 3, 4, 2, 5, 4, 3, 2, 5, 3, 4, 3, 4, 4, 4, 4, 4, 2, 3, 4, 6, 2, 5, 3, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
The Matula-Goebel number of a rooted tree is defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel 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 Matula-Goebel numbers of the m branches of T.
A non-root vertex having degree 1 is called a leaf.
Every positive integer has a unique factorization (see A324924) into factors q(i) = prime(i)/i for i > 0. The number of ones in this factorization is a(n). For example, 30 = q(1)^3 q(2)^2 q(3), so a(30) = 3. - Gus Wiseman, Mar 23 2019
LINKS
E. 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.
FORMULA
a(1)=0; a(2)=1; if n = p(t) (= the t-th prime) and t >= 2, then a(n) = a(t); if n = rs (r, s >= 2), then a(n) = a(r) + a(s). The Maple program is based on this recursive formula.
The Gutman et al. references contain a different recursive formula.
EXAMPLE
a(7)=2 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y.
a(2^m) = m because the rooted tree with Matula-Goebel 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 n = 2 then 1 elif bigomega(n) = 1 then a(pi(n)) else a(r(n))+a(s(n)) end if end proc: seq(a(n), n = 1 .. 110);
MATHEMATICA
Nest[Function[{a, n}, Append[a, If[PrimeQ@ n, a[[PrimePi@ n]], Total@ Map[#2 a[[#1]] & @@ # &, FactorInteger[n]] ]]] @@ {#, Length@ # + 1} &, {0, 1}, 105] (* Michael De Vlieger, Mar 24 2019 *)
PROG
(Haskell)
import Data.List (genericIndex)
a109129 n = genericIndex a109129_list (n - 1)
a109129_list = 0 : 1 : g 3 where
g x = y : g (x + 1) where
y = if t > 0 then a109129 t else a109129 r + a109129 s
where t = a049084 x; r = a020639 x; s = x `div` r
-- Reinhard Zumkeller, Sep 03 2013
(PARI) ML(n) = if( n==1, 1, my(f=factor(n)); sum(k=1, matsize(f)[1], ML(primepi(f[k, 1]))*f[k, 2])) ;
A109129(n) = if( n==1, 0, ML(n) ); \\ François Marques, Mar 16 2021
(Python)
from functools import lru_cache
from sympy import primepi, isprime, factorint
@lru_cache(maxsize=None)
def A109129(n):
if n <= 2: return n-1
if isprime(n): return A109129(primepi(n))
return sum(e*A109129(p) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022
CROSSREFS
Sequence in context: A049874 A060501 A355661 * A304486 A188550 A064122
KEYWORD
nonn
AUTHOR
Keith Briggs, Aug 17 2005
EXTENSIONS
Typo in formula fixed by Reinhard Zumkeller, Sep 03 2013
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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)