OFFSET
1,2
COMMENTS
The Matula (or Matula-Goebel) number of a rooted tree can be 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 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 numbers of the m branches of T.
Fully multiplicative with a(prime(n)) = prime(prime(a(n))). - Antti Karttunen, Mar 09 2017
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..708
Emeric Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
FORMULA
Let p(n) denote the n-th prime (= A000040(n)). We have the recursive equations: a(p(n)) = p(p(a(n))), a(rs) = a(r)a(s), a(1) = 1. The Maple program is based on this.
From Antti Karttunen, Mar 09 2017: (Start)
(End)
EXAMPLE
a(3)=11; indeed, 3 is the Matula number of the path of length 2 and 11 is the Matula number of the path of length 4.
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 1 elif bigomega(n) = 1 then ithprime(ithprime(a(pi(n)))) else a(r(n))*a(s(n)) end if end proc: seq(a(n), n = 1 .. 60);
MATHEMATICA
r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
a[n_] := a[n] = Which[n == 1, 1, PrimeOmega[n] == 1, Prime[ Prime[ a[PrimePi[n]]]], True, a[r[n]]*a[s[n]]];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Sep 09 2024, after Maple program *)
PROG
A257538(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = prime(prime(A257538(primepi(f[i, 1]))))); factorback(f); }; \\ Nonmemoized implementation by Antti Karttunen, Mar 09 2017
(Scheme, with memoization-macro definec)
(definec (A257538 n) (cond ((= 1 n) 1) (else (* (A000040 (A000040 (A257538 (A055396 n)))) (A257538 (A032742 n))))))
;; Antti Karttunen, Mar 09 2017
CROSSREFS
KEYWORD
nonn,mult
AUTHOR
Emeric Deutsch, May 01 2015
EXTENSIONS
Formula corrected by Antti Karttunen, Mar 09 2017
STATUS
approved