|
%I #63 Mar 19 2022 12:45:52
%S 1,2,3,3,4,4,4,4,5,5,5,5,5,5,6,5,5,6,5,6,6,6,6,6,7,6,7,6,6,7,6,6,7,6,
%T 7,7,6,6,7,7,6,7,6,7,8,7,7,7,7,8,7,7,6,8,8,7,7,7,6,8,7,7,8,7,8,8,6,7,
%U 8,8,7,8,7,7,9,7,8,8,7,8,9,7,7,8,8,7,8,8,7,9,8,8,8,8,8,8,8,8,9,9,7,8,8,8,9,7,7,9
%N Number of nodes in rooted tree with Matula-Goebel number n.
%C Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).
%C Each n occurs A000081(n) times.
%H Alois P. Heinz, <a href="/A061775/b061775.txt">Table of n, a(n) for n = 1..10000</a>
%H Keith Briggs, <a href="http://keithbriggs.info/matula.html">Matula numbers and rooted trees</a>
%H Emeric Deutsch, <a href="http://arxiv.org/abs/1111.4288">Tree statistics from Matula numbers</a>, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
%H F. Goebel, <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. Matula, <a href="http://www.jstor.org/stable/2027327?seq=30">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-Goebel numbers</a>
%F a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
%F a(n) = A091238(A091204(n)). - _Antti Karttunen_, January 2004
%F a(n) = A196050(n)+1. - _Antti Karttunen_, Aug 16 2014
%e a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
%e See also the illustrations in A061773.
%p with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # _Emeric Deutsch_, Sep 19 2011
%t a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* _Jean-François Alcover_, Jan 16 2014, after _Emeric Deutsch_ *)
%o (Haskell)
%o import Data.List (genericIndex)
%o a061775 n = genericIndex a061775_list (n - 1)
%o a061775_list = 1 : g 2 where
%o g x = y : g (x + 1) where
%o y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
%o where t = a049084 x; u = a020639 x; v = x `div` u
%o -- _Reinhard Zumkeller_, Sep 03 2013
%o (PARI)
%o A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
%o for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
%o \\ _Antti Karttunen_, Aug 16 2014
%o (Python)
%o from functools import lru_cache
%o from sympy import isprime, factorint, primepi
%o @lru_cache(maxsize=None)
%o def A061775(n):
%o if n == 1: return 1
%o if isprime(n): return 1+A061775(primepi(n))
%o return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # _Chai Wah Wu_, Mar 19 2022
%Y One more than A196050.
%Y Sum of entries in row n of irregular table A214573.
%Y Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
%Y One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
%Y Cf. A005517 (the position of the first occurrence of n).
%Y Cf. A005518 (the position of the last occurrence of n).
%Y Cf. A091233 (their difference plus one).
%Y Cf. A214572 (Numbers k such that a(k) = 8).
%Y Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
%Y Cf. also A075166, A075167, A216648, A216649.
%K nonn
%O 1,2
%A _N. J. A. Sloane_, Jun 22 2001
%E More terms from _David W. Wilson_, Jun 25 2001
%E Extended by _Emeric Deutsch_, Sep 19 2011
|
