login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061775 Number of nodes in rooted tree with Matula-Goebel number n. 93
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

Each n occurs A000081(n) times.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Keith Briggs, Matula numbers and rooted trees

E. Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288, 2011

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. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Index entries for sequences related to Matula-Goebel numbers

FORMULA

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.

a(n) = A091238(A091204(n)). - Antti Karttunen, January 2004

a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

EXAMPLE

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.

See also the illustrations in A061773.

MAPLE

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

MATHEMATICA

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

PROG

(Haskell)

import Data.List (genericIndex)

a061775 n = genericIndex a061775_list (n - 1)

a061775_list = 1 : g 2 where

   g x = y : g (x + 1) where

      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1

          where t = a049084 x; u = a020639 x; v = x `div` u

-- Reinhard Zumkeller, Sep 03 2013

(PARI)

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

for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));

\\ Antti Karttunen, Aug 16 2014

CROSSREFS

One more than A196050.

Sum of entries in row n of irregular table A214573.

Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.

One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.

Cf. A005517 (the position of the first occurrence of n).

Cf. A005518 (the position of the last occurrence of n).

Cf. A091233 (their difference plus one).

Cf. A214572 (Numbers k such that a(k) = 8).

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.

Cf. also A075166, A075167, A216648, A216649.

Sequence in context: A303660 A290021 A070941 * A225634 A247134 A080604

Adjacent sequences:  A061772 A061773 A061774 * A061776 A061777 A061778

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jun 22 2001

EXTENSIONS

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 14:52 EDT 2019. Contains 328161 sequences. (Running on oeis4.)