

A003963


Fully multiplicative with a(p) = k if p is the kth prime.


178



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


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 MatulaGoebel) number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel 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 MatulaGoebel 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_jth 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 freecommutativemonoid 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 factorisation 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, 23142322.
F. Göbel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to MatulaGöbel numbers
Index entries for sequences computed from indices in prime factorization


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(kth 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


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}]


PROG

(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
(Haskell)
a003963 n = product $
zipWith (^) (map a049084 $ a027748_row n) (a124010_row n)
 Reinhard Zumkeller, Jun 30 2012


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.
Sequence in context: A319855 A228731 A163507 * A003960 A243499 A124223
Adjacent sequences: A003960 A003961 A003962 * A003964 A003965 A003966


KEYWORD

nonn,nice,easy,mult


AUTHOR

Marc LeBrun


STATUS

approved



