A257538 The Matula number of the rooted tree obtained from the rooted tree T having Matula number n by replacing each edge of T with a path of length 2.

1, 3, 11, 9, 127, 33, 83, 27, 121, 381, 5381, 99, 773, 249, 1397, 81, 3001, 363, 563, 1143, 913, 16143, 4943, 297, 16129, 2319, 1331, 747, 23563, 4191, 648391, 243, 59191, 9003, 10541, 1089, 3761, 1689, 8503, 3429, 57943, 2739, 13297, 48429

Offset: 1

Author

Emeric Deutsch, May 01 2015

Keywords

• nonn
• mult

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

Examples

			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.
		

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.
• Index to divisibility sequences
• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Cf. A000040, A000720, A006450, A032742, A046523, A049084, A055396.

Programs

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 *)

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)

a(1) = 1; for n>1, a(n) = A000040(A000040(a(A055396(n)))) * a(A032742(n)).

A046523(a(n)) = A046523(n). [Preserves the prime-signature of n].

(End)

Extensions

Formula corrected by Antti Karttunen, Mar 09 2017