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,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

E. 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

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)

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

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

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

Sequence in context: A316884 A084409 A038229 * A304052 A303122 A080351

Adjacent sequences: A257535 A257536 A257537 * A257539 A257540 A257541

Keyword

nonn,mult

Author

Emeric Deutsch, May 01 2015

Extensions

Formula corrected by Antti Karttunen, Mar 09 2017

Status

approved