A003963 Fully multiplicative with a(p) = k if p is the k-th prime.

1, 1, 2, 1, 3, 2, 4, 1, 4, 3, 5, 2, 6, 4, 6, 1, 7, 4, 8, 3, 8, 5, 9, 2, 9, 6, 8, 4, 10, 6, 11, 1, 10, 7, 12, 4, 12, 8, 12, 3, 13, 8, 14, 5, 12, 9, 15, 2, 16, 9, 14, 6, 16, 8, 15, 4, 16, 10, 17, 6, 18, 11, 16, 1, 18, 10, 19, 7, 18, 12, 20, 4, 21, 12, 18, 8, 20, 12, 22, 3, 16, 13, 23, 8, 21, 14, 20, 5

Offset: 1

Author

Marc LeBrun

Keywords

• nonn
• nice
• easy
• mult

Comments

a(n) is the Matula number of the rooted tree obtained from the rooted tree T having Matula number n, by contracting its edges that emanate from the root. Example: a(49) = 16. Indeed, the rooted tree with Matula number 49 is the tree obtained by merging two copies of the tree Y at their roots. Contracting the two edges that emanate from the root, we obtain the star tree with 4 edges having Matula number 16. - Emeric Deutsch, May 01 2015

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-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. - Emeric Deutsch, May 01 2015

a(n) is the product of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(75) = 18; indeed, the partition having Heinz number 75 = 3*5*5 is [2,3,3] and 2*3*3 = 18. - Emeric Deutsch, Jun 03 2015

Let T be the free-commutative-monoid monad on the category Set. Then for each set N we have a canonical function m from TTN to TN. If we let N = {1, 2, 3, ...} and enumerate the primes in the usual way (A000040) then unique prime factorization gives a canonical bijection f from N to TN. Then the sequence is given by a(n) = f^-1(m(T(f)(f(n)))). - Oscar Cunningham, Jul 18 2019

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
• F. Göbel, 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 entries for sequences related to Matula-Göbel numbers
• Index entries for sequences computed from indices in prime factorization

Crossrefs

Cf. A000720, A001221, A001222, A027748, A049084, A056239, A064553, A124010, A156552, A215366, A227184, A241909, A243354, A243499, A243504.

Product of entries on row n of A112798.

Programs

Haskell

a003963 n = product $
   zipWith (^) (map a049084 $ a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Jun 30 2012

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 pi(n) else a(r(n))*a(s(n)) end if end proc: seq(a(n), n = 1 .. 88);
# Alternative:
seq(mul(numtheory:-pi(t[1])^t[2], t=ifactors(n)[2]), n=1..100); # Robert Israel, May 01 2015

Mathematica

a[n_] := Times @@ (PrimePi[ #[[1]] ]^#[[2]]& /@ FactorInteger[n]); a[1] = 1; Table[a[n], {n, 1, 88}]

PARI

a(n)=f=factor(n);prod(i=1,#f[,1],primepi(f[i,1])^f[i,2]) \\ Charles R Greathouse IV, Apr 26 2012; corrected by Rémy Sigrist, Jul 18 2019

PARI

a(n) = {f = factor(n); for (i=1, #f~, f[i, 1] = primepi(f[i, 1]); ); factorback(f); } \\ Michel Marcus, Feb 08 2015

PARI

A003963(n)={n=factor(n); n[,1]=apply(primepi,n[,1]); factorback(n)} \\ M. F. Hasler, May 03 2018

Python

from math import prod
from sympy import primepi, factorint
def A003963(n): return prod(primepi(p)**e for p, e in factorint(n).items()) # Chai Wah Wu, Nov 17 2022

Formula

If n = product prime(k)^e(k) then a(n) = product k^e(k).

Multiplicative with a(p^e) = A000720(p)^e. - David W. Wilson, Aug 01 2001

a(n) = Product_{k=1..A001221(n)} A049084(A027748(n,k))^A124010(n,k). - Reinhard Zumkeller, Jun 30 2012

Rec. eq.: a(1)=1, a(k-th prime) = a(k), a(rs)=a(r)a(s). The Maple program is based on this. - Emeric Deutsch, May 01 2015

a(n) = A243504(A241909(n)) = A243499(A156552(n)) = A227184(A243354(n)) - Antti Karttunen, Mar 07 2017