A005517 -id:A005517 - cp's OEIS frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

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

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

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.

			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.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 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

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.

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

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

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

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

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

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, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Original entry on oeis.org

4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, 111139, 128074, 137987, 196249, 199591, 203878, 263431, 295969, 298154, 302426, 426058, 448259, 452411

Offset: 1

Keith Briggs, Nov 02 2005

nonn

This sequence should probably start with 1. Then a number k is in the sequence iff k = 1 or k = prime(x) * prime(y) with x and y already in the sequence. - Gus Wiseman, May 04 2021

			From _Gus Wiseman_, May 04 2021: (Start)
The sequence of trees (starting with 1) begins:
     1: o
     4: (oo)
    14: (o(oo))
    49: ((oo)(oo))
    86: (o(o(oo)))
   301: ((oo)(o(oo)))
   454: (o((oo)(oo)))
   886: (o(o(o(oo))))
  1589: ((oo)((oo)(oo)))
  1849: ((o(oo))(o(oo)))
  3101: ((oo)(o(o(oo))))
  3986: (o((oo)(o(oo))))
  6418: (o(o((oo)(oo))))
  9761: ((o(oo))((oo)(oo)))
(End)

Kevin Ryde, Table of n, a(n) for n = 1..5000 (terms 1..186 from Charles R Greathouse IV)
Keith Briggs, Matula numbers and rooted trees
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A245824 (by number of leaves).
Cf. A005517, A005518, A061773, A245824.
These trees are counted by 2*A001190 - 1.
The semi-binary version is A292050 (counted by A001190).
The semi-identity case is A339193 (counted by A063895).
A000081 counts unlabeled rooted trees with n nodes.
A007097 ranks rooted chains.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

nn=20000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];
Select[Range[2,nn],binQ] (* Gus Wiseman, Aug 28 2017 *)

i(n)=n==2 || is(primepi(n))
is(n)=if(n<14,return(n==4)); my(f=factor(n),t=#f[,1]); if(t>1, t==2 && f[1,2]==1 && f[2,2]==1 && i(f[1,1]) && i(f[2,1]), f[1,2]==2 && i(f[1,1])) \\ Charles R Greathouse IV, Mar 29 2013

list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, if(i(p)&&i(q), listput(v, t*q)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Mar 29 2013

PARI
```
\\ Also see links.
```

The Matula tree of k is defined as follows:
matula(k):
    create a node labeled k
    for each prime factor m of k:
       add the subtree matula(prime(m)), by an edge labeled m
    return the node

Definition corrected by Charles R Greathouse IV, Mar 29 2013

a(27)-a(39) from Charles R Greathouse IV, Mar 29 2013

A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 15, 18, 20, 21, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 53, 59, 67, 25, 27, 30, 33, 35, 36, 39, 40, 42, 44, 46, 47, 48, 49, 51, 52, 56, 57, 58, 61, 62, 64, 68, 71, 73, 74, 76, 79, 82, 83, 86, 89, 101, 106

Offset: 1

N. J. A. Sloane, Jun 22 2001

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.
n-th row has A000081(n) terms.
First entry in row n is A005517(n).
Last entry in row n is A005518(n).
The Maple program yields row n after defining F = A005517(n) and L = A005518(n).

			The labels for the rooted trees with at most 4 nodes are as follows (x is the root):
                                         o
                                         |
               o         o        o   o  o
               |          \        \ /   |
     o  o   o  o  o o o    o   o    o    o
     |   \ /   |   \|/      \ /     |    |
  x  x    x    x    x        x      x    x
  1  2    4    3    8        6      7    5 (label)
Triangle begins:
1;
2;
3,4;
5,6,7,8;
9,10,11,12,13,14,16,17,19;
15,18,20,21,22,23,24,26,28,29,31,32,34,37,38,41,43,53,59,67;
25,27,30,33,35,36,39,40,42,44,46,47,48,49,51,52,56,57,58,61,62,64,68,\
71,73,74,76,79,82,83,86,89,101,106,107,109,118,127,131,134,139,157,163,\
179,191,241,277,331;
...
Triangle of rooted trees represented as finitary multisets begins:
(),
(()),
((())), (()()),
(((()))), (()(())), ((()())), (()()()),
((())(())), (()((()))), ((((())))), (()()(())), ((()(()))), (()(()())), (()()()()), (((()()))), ((()()())). - _Gus Wiseman_, Dec 21 2016

Alois P. Heinz, Rows n = 1..12, flattened
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.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP code calculating rows
Gus Wiseman, Matula-Goebel trees triangle illustration n=1..6
Index entries for sequences related to Matula-Goebel numbers
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A061775 (number of nodes), A000081 (row lengths), A005517 (row minimum), A005518 (row maximum), A214572 (row n=8).
Cf. A347620 (inverse permutation).
Cf. A276625, A279065, A279614.

n := 8: F := 45: L := 2221: with(numtheory): N := proc (m) local r, s: r := proc (m) options operator, arrow: op(1, factorset(m)) end proc: s := proc (m) options operator, arrow: m/r(m) end proc: if m = 1 then 1 elif bigomega(m) = 1 then 1+N(pi(m)) else N(r(m))+N(s(m))-1 end if end proc: A := {}: for k from F to L do if N(k) = n then A := `union`(A, {k}) else  end if end do: A;

F[n_] := F[n] = Which[n == 1, 1, n == 2, 2, Mod[n, 3] == 0, 3*5^(n/3-1), Mod[n, 3] == 1, 5^(n/3-1/3), True, 9*5^(n/3-5/3)]; L[n_] := L[n] = Switch[n, 1, 1, 2, 2, 3, 4, 4, 8, , Prime[L[n-1]]]; r[m] := FactorInteger[m][[1, 1]]; s[m_] := m/r[m]; NN[m_] := NN[m] = Which[m == 1, 1, PrimeOmega[m] == 1, 1+NN[PrimePi[m]], True, NN[r[m]]+NN[s[m]]-1]; row[n_] := Module[{A, k}, A = {}; For[k = F[n], k <= L[n], k++, If[NN[k] == n, A = Union[A, {k}]]]; A]; Table[row[n], {n, 1, 8}] // Flatten (* Jean-François Alcover, Mar 06 2014, after Maple *)
nn=8;MGweight[n_]:=If[n===1,1,1+Total[Cases[FactorInteger[n],{p_,k_}:>k*MGweight[PrimePi[p]]]]];
Take[GatherBy[Range[Switch[nn,1,1,2,2,3,4,,Nest[Prime,8,nn-4]]],MGweight],nn] (* _Gus Wiseman, Dec 21 2016 *)

PARI
```
\\ See links.
```

More terms from Emeric Deutsch, May 01 2004

A127301 Matula-Goebel signatures for plane general trees encoded by A014486.

Original entry on oeis.org

1, 2, 4, 3, 8, 6, 6, 7, 5, 16, 12, 12, 14, 10, 12, 9, 14, 19, 13, 10, 13, 17, 11, 32, 24, 24, 28, 20, 24, 18, 28, 38, 26, 20, 26, 34, 22, 24, 18, 18, 21, 15, 28, 21, 38, 53, 37, 26, 37, 43, 29, 20, 15, 26, 37, 23, 34, 43, 67, 41, 22, 29, 41, 59, 31, 64, 48, 48, 56, 40, 48, 36

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

This sequence maps A000108(n) oriented (plane) rooted general trees encoded in range [A014137(n-1)..A014138(n)] of A014486 to A000081(n+1) distinct non-oriented rooted general trees, encoded by their Matula-Goebel numbers. The latter encoding is explained in A061773.
A005517 and A005518 give the minimum and maximum value occurring in each such range.
Primes occur at positions given by A057548 (not in order, and with duplicates), and similarly, semiprimes, A001358, occur at positions given by A057518, and in general, A001222(a(n)) = A057515(n).
If the signature-permutation of a Catalan automorphism SP satisfies the condition A127301(SP(n)) = A127301(n) for all n, then it preserves the non-oriented form of a general tree, which implies also that it is Łukasiewicz-word permuting, satisfying A129593(SP(n)) = A129593(n) for all n >= 0. Examples of such automorphisms include A072796, A057508, A057509/A057510, A057511/A057512, A057164, A127285/A127286 and A127287/A127288.
A206487(n) tells how many times n occurs in this sequence. - Antti Karttunen, Jan 03 2013

			A000081(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, A014486(5) = 44 (= 101100 in binary = A063171(5)), encodes the following plane tree:
.....o
.....|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(1) * A000040(A000040(1)) = 2*3 = 6, thus a(5)=6.
Likewise, A014486(6) = 50 (= 110010 in binary = A063171(6)) encodes the plane tree:
.o
.|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(A000040(1)) * A000040(1) = 3*2 = 6, thus a(6) is also 6, which shows these two trees are identical if one ignores their orientation.

Antti Karttunen, Table of n, a(n) for n = 0..6917
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz
Index entries for sequences related to Matula-Goebel numbers

a(A014138(n)) = A007097(n+1), a(A014137(n)) = A000079(n+1) for all n.
a(|A106191(n)|) = A033844(n-1) for all n >= 1.
Cf. A001222, A005517, A005518, A057515, A057518, A057548, A127302, A129593, A153826, A209638, A243491, A243492, A243494, A243496.
For standard instead of binary encoding we have A358506.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists binary encodings of ordered rooted trees.
Cf. A001263, A061775, A196050, A206487, A358505.

mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
binbalQ[n_]:=n==0||With[{dig=IntegerDigits[n,2]},And@@Table[If[k==Length[dig],SameQ,LessEqual][Count[Take[dig,k],0],Count[Take[dig,k],1]],{k,Length[dig]}]];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[mgnum[bint[n]],{n,Select[Range[0,1000],binbalQ]}] (* Gus Wiseman, Nov 22 2022 *)

(define (A127301 n) (*A127301 (A014486->parenthesization (A014486 n)))) ;; A014486->parenthesization given in A014486.
(define (*A127301 s) (if (null? s) 1 (fold-left (lambda (m t) (* m (A000040 (*A127301 t)))) 1 s)))

A001222(a(n)) = A057515(n) for all n.

A005518 Largest label f(T) given to a rooted tree T with n nodes in Matula-Goebel labeling.

Original entry on oeis.org

1, 2, 4, 8, 19, 67, 331, 2221, 19577, 219613, 3042161, 50728129, 997525853, 22742734291, 592821132889, 17461204521323, 575411103069067, 21034688742654437, 846729487306354343

Offset: 1

N. J. A. Sloane

nonn

Let prime(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 prime(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B, Vol. 29, No. 1 (1980), pp. 141-143.
I. Gutman and A. Ivić, Graphs with maximal and minimal Matula numbers, Bulletin CVII Acad. Serbe, Sciences Math., Vol. 107, No. 19 (1994), pp. 65-74.
I. Gutman and A. Ivić, On Matula numbers, Discrete Math., Vol. 150, No. 1-3 (1996), pp. 131-142.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev., Vol. 10 (1968), p. 273.
Index entries for sequences related to Matula-Goebel numbers.
Index entries for sequences related to rooted trees.
Index entries for sequences related to trees.

Apart from initial terms, same as A057452.

Cf. A061773. See A005517 for the smallest value of f(T).

with(numtheory): a := proc (n) if n = 1 then 1 elif n = 2 then 2 elif n = 3 then 4 elif n = 4 then 8 else ithprime(a(n-1)) end if end proc: seq(a(n), n = 1 .. 12); # Emeric Deutsch, Apr 15 2012

a[n_] := a[n] = Switch[n, 1, 1, 2, 2, 3, 4, 4, 8, , Prime[a[n-1]]]; Table[a[n], {n, 1, 16}] (* _Jean-François Alcover, Mar 06 2014, after Emeric Deutsch *)

a(1)=1; a(2)=2; a(3)=4; a(4)=8; a(n) = the a(n-1)-th prime (see the Gutman and Ivic 1994 paper). - Emeric Deutsch, Apr 15 2012
Under plausible assumptions about the growth of the primes, for n >= 4, a(n+1) = a(n)-th prime and A005518(n) = A057452(n-3). - David W. Wilson, Jul 09 2001
A091233(n) = (a(n)-A005517(n))+1. - Antti Karttunen, May 24 2004

More terms from David W. Wilson, Jul 09 2001

a(17)-a(19) from Robert G. Wilson v, Mar 07 2017 using Kim Walisch's primecount

A235111 Irregular triangle read by rows: row n (n>=1) contains in increasing order the M-indices of the trees with n vertices.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 12, 16, 15, 18, 20, 24, 28, 32, 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64, 45, 50, 54, 55, 60, 63, 65, 70, 72, 77, 78, 80, 84, 88, 91, 96, 98, 104, 112, 119, 128, 133, 152, 75, 81, 90, 99, 100, 105, 108, 110, 117, 120, 121, 126, 130, 132

Offset: 1

Emeric Deutsch, Jan 03 2014

We define the M-index of a tree T to be the smallest of the Matula numbers of the rooted trees isomorphic (as a tree) to T. Example. The path tree P[5] = ABCDE has M-index 9. Indeed, there are 3 rooted trees isomorphic to P[5]: rooted at A, B, and C, respectively. Their Matula numbers are 11, 10, and 9, respectively. Consequently, the M-index of P[5] is 9.
Number of entries in row n is A000055(n) (= number of trees with n vertices).
First entry in row n is A005517(n) (= smallest among the Matula numbers of the rooted trees with n vertices).
Last entry (= largest entry) in row n is A235112(n).

			Example. Row 4 is [5, 7]. Indeed, there are 2 trees with 4 vertices: the path P[4] and the star S[3] with 3 edges. There are two rooted trees isomorphic to P[4], having Matula numbers 5 and 6; smallest is 5. There are two rooted trees isomorphic to S[3], having Matula numbers 7 and 8; smallest is 7.
Triangle begins:
1;
2;
3;
5,7;
9,12,16;
15,18,20,24,28,32;

Emeric Deutsch, Rows n = 1..12, flattened
E. Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
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, W. Linert, I. Lukovits, and Z. Tomovic, The multiplicative version of the Wiener index, J. Chem. Inf. Comput. Sci., 40, 2000, 113-116.
I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, On the multiplicative Wiener index and its possible chemical applications, Monatshefte f. Chemie, 131, 2000, 421-427.
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.

Cf. A000055, A005517, A005518, A235112.

# The following program (due mainly to W. Edwin Clark), yields row n for the specified n (<=15).
n := 9;
with(numtheory): MIN := [1, 2, 3, 5, 9, 15, 25, 45, 75, 125, 225, 375, 625, 1125, 1875]: MAX := [1, 2, 4, 8, 19, 67, 331, 2221, 19577, 219613, 3042161, 50728129, 997525853, 22742734291, 592821132889]: f := proc (m) local x, p, S: S := NULL: x := factorset(m): for p in x do S := S, ithprime(m/p)*pi(p) end do: S end proc: M := proc (m) local A, B: A := {m}: do B := A: A := `union`(map(f, A), A): if B = A then return A end if end do end proc: V := proc (n) local u, v: u := proc (n) options operator, arrow: op(1, factorset(n)) end proc: v := proc (n) options operator, arrow: n/u(n) end proc: if n = 1 then 1 elif isprime(n) then 1+V(pi(n)) else V(u(n))+V(v(n))-1 end if end proc: Q := {}: for j from MIN[n] to MAX[n] do if V(j) = n then Q := `union`(Q, {min(M(j))}) else  end if end do: Q;
# MIN is sequence A005517, MAX is sequence A005518.

nmax = 9 (* nmax > 3 *);
MIN = Join[{1, 2}, LinearRecurrence[{0, 0, 5}, {3, 5, 9}, nmax - 2]];
MAX = Join[{1, 2, 4}, NestList[Prime, 8, nmax - 4]];
row[n_] := (
f[m_] := Table[Prime[m/p]*PrimePi[p], {p, FactorInteger[m][[All, 1]]}];
M[m_] := Module[{A, B}, A = {m}; While[True, B = A; A = Union[Map[f, A] // Flatten, A]; If[B == A, Return[A]]]];
u [m_] := FactorInteger[m][[All, 1]][[1]];
v [m_] := m/u[m];
V [m_] := If [m==1, 1, If[PrimeQ[m], 1+V[PrimePi[m]], V[u[m]]+V[v[m]]-1]];
Q = {}; For[j = MIN[[n]], j <= MAX[[n]], j++, If[V[j] == n,  Q = Union[Q, {Min[M[j]]}]]];
Q);
row[1] = {1};
Table[row[n], {n, 1, nmax}] // Flatten (* Jean-François Alcover, Jan 19 2018, adapted from Maple *)

A091233 (Largest Matula-Goebel number encoding a tree with n nodes) - (smallest Matula-Goebel number encoding a tree with n nodes).

Original entry on oeis.org

1, 1, 2, 4, 11, 53, 307, 2177, 19503, 219489, 3041937, 50727755, 997525229, 22742733167, 592821131015, 17461204518199

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968).

A. Karttunen, Scheme-program for computing this sequence.

Compare to A091241 and A000081. Cf. A061773.

a(n) = (A005518(n)-A005517(n))+1.

A290323 Minimal number of supporters among total of n voters that may make (but not guarantee) their candidate win in a multi-level selection based on the majority vote at each level.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 4, 5, 4, 6, 6, 6, 7, 8, 6, 9, 9, 8, 10, 9, 8, 12, 12, 10, 9, 14, 8, 12, 15, 12, 16, 15, 12, 18, 12, 12, 19, 20, 14, 15, 21, 16, 22, 18, 12, 24, 24, 18, 16, 18, 18, 21, 27, 16, 18, 20, 20, 30, 30, 18, 31, 32, 16, 25, 21, 24, 34, 27

Offset: 1

Max Alekseyev, Jul 27 2017

Each group in a given level must have the same number of voters. A tie in the voting results in a win for the opposition. (A003960 appears to describe the case in which a tie results in a loss for the opposition.) - Peter Kagey, Aug 16 2017

This is related to the gerrymandering question. - N. J. A. Sloane, Feb 27 2021

			For n=9, four supporters are enough in the following 2-level selection with (s)upporters and (o)pponents: ((sso),(sso),(ooo)). On the other hand, no smaller number of supporters can lead to a win in any multi-level selection. Hence, a(9)=4.

Peter Kagey, Table of n, a(n) for n = 1..10000
Author?, Solution to problem M1 (in Russian), Kvant 7 (1970), 49-51.
Author?, Problem M1 with solution (in Russian)
Wikipedia, Gerrymandering.

Cf. A003960, A005517.

f[p_, e_] := ((p + 1)/2)^e; f[2, e_] := Switch[Mod[e, 3], 1, 9/5, 2, 3, 0, 1] * 5^Floor[e/3]; f[2, 1] = 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 18 2023 *)

A290323(n) = my(m=valuation(n,2),f=factor(n>>m)); if(m==1, 2, [1,9/5,3][m%3+1]*5^(m\3)) * prod(i=1,#f~, ((f[i,1]+1)/2)^f[i,2]);

from sympy import factorint
from functools import reduce
from operator import mul
def A290323(n):
    f = factorint(n)
    m = f[2] if 2 in f else 0
    a, b = divmod(m,3)
    c = 2 if m == 1 else 3**(b*(b+1)%5)*5**(a-(b%2))
    return c*reduce(mul,(((d+1)//2)**f[d] for d in f if d != 2),1) # Chai Wah Wu, Mar 05 2021

def divisors_of(n); (2..n).select { |d| n % d == 0 } end
def f(n, group_size); (group_size/2 + 1) * a(n / group_size) end
def a(n); n == 1 ? 1 : divisors_of(n).map { |d| f(n, d) }.min end
# Peter Kagey, Aug 16 2017

Let n = 2^m*p1*...*pk, where pi are odd primes. Then a(n) = c*(p1+1)/2*...*(pk+1)/2 = c*A003960(n), where c=2 if m=1; c=5^b if m=3b; c=3*5^b if m=3b+2; c=9*5^b, if m=3b+4 (b>=0). [So c(m) = A005517(m+1). - Andrey Zabolotskiy, Jan 27 2022]

Keyword:mult added by Andrew Howroyd, Aug 06 2018

A091239 Smallest GF2X-Matula number i which encodes a tree of n nodes, i.e., for which A091238(i) = n.

Original entry on oeis.org

1, 2, 3, 6, 5, 9, 15, 23, 17, 34, 51, 75, 85, 153, 255, 359, 257, 514, 771, 1275, 1285, 2313, 3855, 5911, 4369, 8738, 13107, 19275, 21845, 39321, 65535

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

A. Karttunen, Scheme-program for computing this sequence.

Analogous to A005517. A091240 gives the largest i with number of nodes = n. Cf. A091238, A091241.

A214572 The Matula-Goebel numbers of the rooted trees having 8 vertices.

Original entry on oeis.org

45, 50, 54, 55, 60, 63, 65, 66, 69, 70, 72, 77, 78, 80, 84, 85, 87, 88, 91, 92, 93, 94, 95, 96, 97, 98, 102, 103, 104, 111, 112, 113, 114, 116, 119, 122, 123, 124, 128, 129, 133, 136, 137, 142, 146, 148, 149, 151, 152, 158, 159, 164, 166, 167, 172, 173, 177, 178, 181, 193, 199, 201, 202, 211, 212, 214, 218, 223, 227, 233, 236, 239, 254, 262, 263, 268, 269, 271, 278, 283, 293, 311, 314, 326, 337, 353, 358, 367, 373, 382, 383, 401, 421, 431, 443, 461, 482, 547, 554, 577, 587, 599, 647, 662, 709, 739, 757, 797, 919, 967, 1063, 1153, 1523, 1787, 2221

Offset: 1

Emeric Deutsch, Aug 14 2012

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

It is a finite sequence; number of entries is 115 = A000081(8).

			128=2^7 is in the sequence; it is the Matula-Goebel number of the star K_{1,7}.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

Cf. A005517, A005518, A061775, A000081.

Row n=8 of A061773. - Alois P. Heinz, Sep 06 2012

with(numtheory): N := 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 1+N(pi(n)) else N(r(n))+N(s(n))-1 end if end proc: A := {}: for n to 3000 do if N(n) = 8 then A := `union`(A, {n}) else  end if end do: A;

MGweight[n_] := If[n == 1, 1, 1 + Total[Cases[FactorInteger[n], {p_, k_} :> k*MGweight[PrimePi[p]]]]];
Select[Range[Nest[Prime, 8, 4]], MGweight[#] == 8&] (* Jean-François Alcover, Nov 11 2017, after Gus Wiseman's program for A061773 *)

A061775(n) yields the number of vertices of the rooted tree with Matula-Goebel number n. We use it to find the Matula-Goebel numbers of the rooted trees having 8 vertices.

cp's OEIS Frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A127301 Matula-Goebel signatures for plane general trees encoded by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A005518 Largest label f(T) given to a rooted tree T with n nodes in Matula-Goebel labeling.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A235111 Irregular triangle read by rows: row n (n>=1) contains in increasing order the M-indices of the trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple