|
%I #81 Nov 18 2022 03:38:52
%S 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,
%T 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,
%U 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
%N Fully multiplicative with a(p) = k if p is the k-th prime.
%C 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
%C 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
%C 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
%C 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
%H T. D. Noe, <a href="/A003963/b003963.txt">Table of n, a(n) for n = 1..10000</a>
%H E. Deutsch, <a href="http://dx.doi.org/10.1016/j.dam.2012.05.012">Rooted tree statistics from Matula numbers</a>, Discrete Appl. Math., 160, 2012, 2314-2322.
%H F. Göbel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.
%H I. Gutman and A. Ivic, <a href="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.
%H I. Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publ. Inst. Math., 53 (67), 1993, 17-22.
%H D. W. Matula, <a href="http://www.jstor.org/stable/2027327">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.
%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Göbel numbers</a>
%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%F If n = product prime(k)^e(k) then a(n) = product k^e(k).
%F Multiplicative with a(p^e) = A000720(p)^e. - _David W. Wilson_, Aug 01 2001
%F a(n) = Product_{k=1..A001221(n)} A049084(A027748(n,k))^A124010(n,k). - _Reinhard Zumkeller_, Jun 30 2012
%F 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
%F a(n) = A243504(A241909(n)) = A243499(A156552(n)) = A227184(A243354(n)) - _Antti Karttunen_, Mar 07 2017
%p 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);
%p # Alternative:
%p seq(mul(numtheory:-pi(t[1])^t[2], t=ifactors(n)[2]), n=1..100); # _Robert Israel_, May 01 2015
%t a[n_] := Times @@ (PrimePi[ #[[1]] ]^#[[2]]& /@ FactorInteger[n]); a[1] = 1; Table[a[n], {n, 1, 88}]
%o (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
%o (PARI) a(n) = {f = factor(n); for (i=1, #f~, f[i, 1] = primepi(f[i, 1]); ); factorback(f); } \\ _Michel Marcus_, Feb 08 2015
%o (PARI) A003963(n)={n=factor(n); n[,1]=apply(primepi,n[,1]); factorback(n)} \\ _M. F. Hasler_, May 03 2018
%o (Haskell)
%o a003963 n = product $
%o zipWith (^) (map a049084 $ a027748_row n) (a124010_row n)
%o -- _Reinhard Zumkeller_, Jun 30 2012
%o (Python)
%o from math import prod
%o from sympy import primepi, factorint
%o def A003963(n): return prod(primepi(p)**e for p, e in factorint(n).items()) # _Chai Wah Wu_, Nov 17 2022
%Y Cf. A000720, A001221, A001222, A027748, A049084, A056239, A064553, A124010, A156552, A215366, A227184, A241909, A243354, A243499, A243504.
%Y Product of entries on row n of A112798.
%K nonn,nice,easy,mult
%O 1,3
%A _Marc LeBrun_
|
