A061773 -id:A061773 - cp's OEIS frontend

A279614 a(1)=1, a(d(x_1)..d(x_k)) = 1+a(x_1)+..+a(x_k) where d(n) = n-th Fermi-Dirac prime.

1, 2, 3, 4, 5, 4, 6, 5, 5, 6, 7, 6, 6, 7, 7, 6, 7, 6, 8, 8, 8, 8, 7, 7, 7, 7, 7, 9, 8, 8, 8, 7, 9, 8, 10, 8, 7, 9, 8, 9, 8, 9, 7, 10, 9, 8, 9, 8, 9, 8, 9, 9, 9, 8, 11, 10, 10, 9, 9, 10, 8, 9, 10, 9, 10, 10, 8, 10, 9, 11, 8, 9, 8, 8, 9, 11, 12, 9, 8, 10, 10, 9

Offset: 1

Gus Wiseman, Dec 15 2016

nonn

A Fermi-Dirac prime (A050376) is a positive integer of the form p^(2^k) where p is prime and k>=0.

In analogy with the Matula-Goebel correspondence between rooted trees and positive integers (see A061775), the iterated normalized Fermi-Dirac representation gives a correspondence between rooted identity trees and positive integers. Then a(n) is the number of nodes in the rooted identity tree corresponding to n.

			Sequence of rooted identity trees represented as finitary sets begins:
{}, {{}}, {{{}}}, {{{{}}}}, {{{{{}}}}}, {{}{{}}}, {{{{{{}}}}}},
{{}{{{}}}}, {{{}{{}}}}, {{}{{{{}}}}}, {{{{{{{}}}}}}}, {{{}}{{{}}}},
{{{}{{{}}}}}, {{}{{{{{}}}}}}, {{{}}{{{{}}}}}, {{{{}{{}}}}},
{{{}{{{{}}}}}}, {{}{{}{{}}}}, {{{{{{{{}}}}}}}}, {{{{}}}{{{{}}}}},
{{{}}{{{{{}}}}}}, {{}{{{{{{}}}}}}}, {{{{}}{{{}}}}}, {{}{{}}{{{}}}}.

OEIS Wiki, "Fermi-Dirac representation" of n

Cf. A004111, A050376, A061773, A061775, A084400, A276625, A279065.

nn=200;
FDfactor[n_]:=If[n===1,{},Sort[Join@@Cases[FactorInteger[n],{p_,k_}:>Power[p,Cases[Position[IntegerDigits[k,2]//Reverse,1],{m_}->2^(m-1)]]]]];
FDprimeList=Array[FDfactor,nn,1,Union];
FDweight[n_?(#<=nn&)]:=If[n===1,1,1+Total[FDweight[Position[FDprimeList,#][[1,1]]]&/@FDfactor[n]]];
Array[FDweight,nn]

Number of appearances of n is |a^{-1}(n)| = A004111(n).

A304486 Number of inequivalent leaf-colorings of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 2, 2, 1, 4, 2, 4, 2, 5, 2, 4, 3, 4, 4, 2, 2, 7, 2, 5, 3, 9, 2, 5, 1, 7, 2, 4, 4, 9, 4, 7, 5, 7, 2, 11, 4, 4, 4, 4, 2, 12, 7, 4, 4, 11, 5, 7, 2, 16, 7, 5, 2, 11, 4, 2, 9, 11, 5, 5, 3, 9, 4, 11

Offset: 1

Gus Wiseman, Aug 17 2018

			Inequivalent representatives of the a(52) = 11 colorings of the tree (oo(o(o))) are the following.
  (11(1(1)))
  (11(1(2)))
  (11(2(1)))
  (11(2(2)))
  (11(2(3)))
  (12(1(1)))
  (12(1(2)))
  (12(1(3)))
  (12(3(1)))
  (12(3(3)))
  (12(3(4)))

Cf. A000081, A001678, A004111, A007097, A049076, A061773, A061775, A109082, A109129, A300626, A303024, A303431, A317713, A317994.

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.

A091238 Number of nodes in rooted tree with GF2X-Matula number n.

Original entry on oeis.org

1, 2, 3, 3, 5, 4, 4, 4, 6, 6, 4, 5, 6, 5, 7, 5, 9, 7, 5, 7, 7, 5, 8, 6, 5, 7, 8, 6, 6, 8, 5, 6, 7, 10, 9, 8, 7, 6, 8, 8, 7, 8, 7, 6, 10, 9, 5, 7, 7, 6, 11, 8, 7, 9, 6, 7, 10, 7, 7, 9, 6, 6, 9, 7, 11, 8, 8, 11, 7, 10, 8, 9, 6, 8, 12, 7, 9, 9, 8, 9, 11, 8, 9, 9, 13, 8, 10, 7, 8, 11, 8, 10, 8, 6, 9, 8

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Each n occurs A000081(n) times.

			GF2X-Matula numbers for unoriented rooted trees are constructed otherwise just like the standard Matula-Goebel numbers (cf. A061773), but instead of normal factorization in N, one factorizes in polynomial ring GF(2)[X] as follows. Here IR(n) is the n-th irreducible polynomial (A014580(n)) and X stands for GF(2)[X]-multiplication (A048720):
................................................o...................o
................................................|...................|
............o...............o...o........o......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........x..
1..2 = IR(1)..3 = IR(2)..4 = 2 X 2....5 = 3 X 3....6 = 2 X 3....7 = IR(3)..8 = 2 X 2 X 2..9 = 3 X 7
Counting the vertices (marked with x's and o's) of each tree above, we get the eight initial terms of this sequence: 1,2,3,3,5,4,4,4,6.

a(n) = A061775(A091205(n)). a(A091230(n)) = n+1. Cf. A091239-A091241.

A245824 Triangle read by rows: row n>=1 contains in increasing order the Matula numbers of the rooted binary trees with n leaves.

Original entry on oeis.org

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

Offset: 1

Emeric Deutsch, Aug 02 2014

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.

Row n contains A001190(n) entries (the Wedderburn-Etherington numbers).

			Row 2 is: 4 (the Matula number of the rooted tree V)
Triangle starts:
1;
4;
14;
49, 86;
301, 454, 886;
1589, 1849, 3101, 3986, 6418, 13766;

Gus Wiseman, Table of n, a(n) for n = 1..94
Emeric Deutsch, Tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], (18-November-2011)
Emeric 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. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Cf. A000081, A001190, A007097, A061773, A111299 (the ordered sequence of all numbers appearing in this sequence), A280994.

nn=9;
allbin[n_]:=allbin[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[allbin/@c]]]/@Select[IntegerPartitions[n-1],Length[#]===2&]];
MGNumber[{}]:=1;MGNumber[x:{}]:=Times@@Prime/@MGNumber/@x;
Table[Sort[MGNumber/@allbin[n]],{n,1,2nn,2}] (* Gus Wiseman, Aug 28 2017 *)

Let H[n] denote the set of binary rooted trees with n leaves or, with some abuse, the set of their Matula numbers (for example, H[1]={1}, H[2]={4}). Each binary rooted tree with n leaves is obtained by identifying the roots of an "elevated" tree from H[k] and of an "elevated" tree from H[n-k] (k=1,..., floor(n/2)). The Maple program is based on this. It makes use of the fact that the Matula number of the "elevation" of a rooted tree with Matula number q has Matula number equal to the q-th prime. The shown program determines H[m] for m=3...9 but shows only H[9].

Ordering of terms corrected by Gus Wiseman, Aug 29 2017

A366388 The number of edges minus the number of leafs in the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 2, 2, 3, 1, 2, 1, 3, 0, 2, 2, 1, 2, 2, 3, 3, 1, 4, 2, 3, 1, 3, 3, 4, 0, 4, 2, 3, 2, 2, 1, 3, 2, 3, 2, 2, 3, 4, 3, 4, 1, 2, 4, 3, 2, 1, 3, 5, 1, 2, 3, 3, 3, 3, 4, 3, 0, 4, 4, 2, 2, 4, 3, 3, 2, 3, 2, 5, 1, 4, 3, 4, 2, 4, 3, 4, 2, 4, 2, 4, 3, 2, 4, 3, 3, 5, 4, 3, 1, 5, 2, 5, 4, 3, 3, 4, 2, 4

Offset: 1

Antti Karttunen, Oct 23 2023

nonn

Number of iterations of A366385 needed to reach the nearest power of 2.

			See illustrations in A061773.

Cf. A000720, A006530, A052126, A061395, A061773, A366385.
Cf. A109129 (gives the exponent of the nearest power of 2 reached), A196050 (distance to the farthest power of 2, which is 1).
Cf. also A329697, A331410.

Array[-1 + Length@ NestWhileList[PrimePi[#2]*#1/#2 & @@ {#, FactorInteger[#][[-1, 1]]} &, #, ! IntegerQ@ Log2[#] &] &, 105] (* Michael De Vlieger, Oct 23 2023 *)

A366388(n) = if(n<=2, 0, if(isprime(n), 1+A366388(primepi(n)), my(f=factor(n)); (apply(A366388, f[, 1])~ * f[, 2])));

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A366385(n) = { my(gpf=A006530(n)); primepi(gpf)*(n/gpf); };
A366388(n) = if(n && !bitand(n,n-1),0,1+A366388(A366385(n)));

Totally additive with a(2) = 0, and for n > 1, a(prime(n)) = 1 + a(n).
a(n) = A196050(n) - A109129(n).
a(2n) = a(A000265(n)) = a(n).

A216648 Triangle T(n,k) in which n-th row lists in increasing order all positive integers with a representation as totally balanced 2n digit binary string without totally balanced proper prefixes such that all consecutive totally balanced substrings are in nondecreasing order; n>=1, 1<=k<=A000081(n).

Original entry on oeis.org

2, 12, 52, 56, 212, 216, 232, 240, 852, 856, 872, 880, 920, 936, 944, 976, 992, 3412, 3416, 3432, 3440, 3480, 3496, 3504, 3536, 3552, 3688, 3696, 3752, 3760, 3792, 3808, 3888, 3920, 3936, 4000, 4032, 13652, 13656, 13672, 13680, 13720, 13736, 13744, 13776

Offset: 1

Alois P. Heinz, Sep 12 2012

There is a simple bijection between the elements of row n and the rooted trees with n nodes. Each matching pair (1,0) in the binary string representation encodes a node, each totally balanced substring encodes a list of subtrees.

			856 is element of row 5, the binary string representation (with totally balanced substrings enclosed in parentheses) is (1(10)(10)(1(10)0)0).  The encoded rooted tree is:
.    o
.   /|\
.  o o o
.      |
.      o
Triangle T(n,k) begins:
2;
12;
52,     56;
212,   216,  232,  240;
852,   856,  872,  880,  920,  936,  944,  976,  992;
3412, 3416, 3432, 3440, 3480, 3496, 3504, 3536, 3552, 3688, 3696, ...
Triangle T(n,k) in binary:
10;
1100;
110100,       111000;
11010100,     11011000,     11101000,     11110000;
1101010100,   1101011000,   1101101000,   1101110000,   1110011000, ...
110101010100, 110101011000, 110101101000, 110101110000, 110110011000, ...

Alois P. Heinz, Rows n = 1..12, flattened

First column gives: A080675.
Last elements of rows give: A020522.
Row lengths are: A000081.
Subsequence of A057547, A081292.
Cf. A061773, A216349, A216350, A216649.

F:= proc(n) option remember; `if`(n=1, [10], sort(map(h->
      parse(cat(1, sort(h)[], 0)), g(n-1, n-1)))) end:
g:= proc(n, i) option remember; `if`(i=1, [[10$n]], [seq(seq(seq(
      [seq (F(i)[w[t]-t+1], t=1..j),v[]], w=combinat[choose](
      [$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)])
    end:
b:= proc(n) local h, i, r; h, r:= n, 0; for i from 0
      while h>0 do r:= r+2^i*irem(h, 10, 'h') od; r
    end:
T:= proc(n) option remember; map(b, F(n))[] end:
seq(T(n), n=1..7);

T(n,k) = A216649(n-1,k)*2 + 2^(2*n-1) for n>1.

A280994 Triangle read by rows giving Matula-Goebel numbers of planted achiral trees with n nodes.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 23, 31, 32, 53, 59, 67, 25, 27, 49, 64, 83, 127, 131, 241, 277, 331, 97, 103, 128, 227, 311, 431, 709, 739, 1523, 1787, 2221, 81, 121, 256, 289, 361, 509, 563, 719, 1433, 2063, 3001, 5381, 5623, 12763, 15299, 19577

Offset: 1

Gus Wiseman, Jan 12 2017

An achiral tree is either (case 1) a single node or (case 2) a finite constant sequence (t,t,..,t) of achiral trees. Only in case 2 is an achiral tree considered to be a generalized Bethe tree (according to A214577).

			Triangle begins:
1,
2,
3, 4,
5, 7, 8,
9, 11, 16, 17, 19,
23, 31, 32, 53, 59, 67,
25, 27, 49, 64, 83, 127, 131, 241, 277, 331.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.

Cf. A003238 (row lengths), A214577, A061773, A061775, A004111, A007097, A196545, A275870.

nn=7;MGNumber[[]]:=1;MGNumber[x:[__]]:=If[Length[x]===1,Prime[MGNumber[x[[1]]]],Times@@Prime/@MGNumber/@x];
cits[n_]:=If[n===1,{1},Join@@Table[ConstantArray[#,(n-1)/d]&/@cits[d],{d,Divisors[n-1]}]];
Table[Sort[MGNumber/@(cits[n]/.(1->{}))],{n,nn}]

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 5, 4, 5, 3, 4, 3, 7, 2, 4, 5, 3, 4, 5, 5, 6, 3, 10, 4, 9, 3, 5, 7, 6, 2, 9, 4, 7, 5, 4, 3, 7, 4, 5, 5, 4, 5, 13, 6, 8, 3, 5, 10, 7, 4, 3, 9, 13, 3, 5, 5, 5, 7, 6, 6, 9, 2, 10, 9, 4, 4, 11, 7, 5, 5, 6, 4, 19, 3, 9, 7, 6, 4, 17, 5, 7, 5

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

We require that an initial subtree contain either all or none of the branchings under any given node.

			70 is the Matula-Goebel number of the tree (o((o))(oo)), which has 7 distinct initial subtrees: {o, (ooo), (oo(oo)), (o(o)o), (o(o)(oo)), (o((o))o), (o((o))(oo))}. So a(70) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476, A317713.

si[n_]:=If[n==1,1,1+Product[si[PrimePi[b[[1]]]]^b[[2]],{b,FactorInteger[n]}]];
Array[si,100]

a(1) = 1 and if n > 1 has prime factorization n = prime(x_1)^y_1 * ... * prime(x_k)^y_k then a(n) = 1 + a(x_1)^y_1 * ... * a(x_k)^y_k.

A216649 Triangle T(n,k) in which n-th row lists in increasing order all positive integers with a representation as totally balanced 2n digit binary string such that all consecutive totally balanced substrings are in nondecreasing order; n>=1, 1<=k<=A000081(n+1).

Original entry on oeis.org

2, 10, 12, 42, 44, 52, 56, 170, 172, 180, 184, 204, 212, 216, 232, 240, 682, 684, 692, 696, 716, 724, 728, 744, 752, 820, 824, 852, 856, 872, 880, 920, 936, 944, 976, 992, 2730, 2732, 2740, 2744, 2764, 2772, 2776, 2792, 2800, 2868, 2872, 2900, 2904, 2920, 2928

Offset: 1

Alois P. Heinz, Sep 12 2012

There is a simple bijection between the elements of row n and the rooted trees with n+1 nodes. The tree has a root node. Each matching pair (1,0) in the binary string representation encodes an additional node, the totally balanced substrings encode lists of subtrees.

			172 is element of row 4, the binary string representation (with totally balanced substrings enclosed in parentheses) is (10)(10)(1(10)0).  The encoded rooted tree is:
.    o
.   /|\
.  o o o
.      |
.      o
Triangle T(n,k) begins:
2;
10,     12;
42,     44,   52,   56;
170,   172,  180,  184,  204,  212,  216,  232,  240;
682,   684,  692,  696,  716,  724,  728,  744,  752,  820,  824, ...
2730, 2732, 2740, 2744, 2764, 2772, 2776, 2792, 2800, 2868, 2872, ...
Triangle T(n,k) in binary:
10;
1010,       1100;
101010,     101100,     110100,     111000;
10101010,   10101100,   10110100,   10111000,   11001100,   11010100, ...
1010101010, 1010101100, 1010110100, 1010111000, 1011001100, 1011010100, ...

Alois P. Heinz, Rows n = 1..11, flattened

First column gives: A020988.
Last elements of rows give: A020522.
Row lengths are: A000081(n+1).
Subsequence of A014486, A031443.
Cf. A061773, A216349, A216350, A216648.

F:= proc(n) option remember; `if`(n=1, [10], sort(map(h->
      parse(cat(1, sort(h)[], 0)), g(n-1, n-1)))) end:
g:= proc(n, i) option remember; `if`(i=1, [[10$n]], [seq(seq(seq(
      [seq (F(i)[w[t]-t+1], t=1..j),v[]], w=combinat[choose](
      [$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)])
    end:
b:= proc(n) local h, i, r; h, r:= n/10, 0; for i from 0
      while h>1 do r:= r+2^i*irem(h, 10, 'h') od; r
    end:
T:= proc(n) option remember; map(b, F(n+1))[] end:
seq(T(n), n=1..6);

T(n,k) = A216648(n+1,k)/2 - 2^(2*n).

cp's OEIS Frontend

A279614 a(1)=1, a(d(x_1)*..*d(x_k)) = 1+a(x_1)+..+a(x_k) where d(n) = n-th Fermi-Dirac prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A304486 Number of inequivalent leaf-colorings of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Examples

Crossrefs

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

Views

Author

Keywords

References

Links

Crossrefs

Formula

A091238 Number of nodes in rooted tree with GF2X-Matula number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A245824 Triangle read by rows: row n>=1 contains in increasing order the Matula numbers of the rooted binary trees with n leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A366388 The number of edges minus the number of leafs in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A280994 Triangle read by rows giving Matula-Goebel numbers of planted achiral trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

A279614 a(1)=1, a(d(x_1)..d(x_k)) = 1+a(x_1)+..+a(x_k) where d(n) = n-th Fermi-Dirac prime.