|
|
A214577
|
|
The Matula-Goebel numbers of the generalized Bethe trees. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree.
|
|
66
|
|
|
2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 23, 25, 27, 31, 32, 49, 53, 59, 64, 67, 81, 83, 97, 103, 121, 125, 127, 128, 131, 227, 241, 243, 256, 277, 289, 311, 331, 343, 361, 419, 431, 509, 512, 529, 563, 625, 661, 691, 709, 719, 729, 739, 961, 1024, 1331, 1433, 1523, 1543, 1619, 1787, 1879, 2048, 2063, 2187, 2221, 2309, 2401, 2437, 2809, 2897
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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.
Generalized Bethe trees are called uniform trees in the Goldberg - Livshits reference.
There is a simple bijection between generalized Bethe trees with n edges and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges --- sum of parts; root degree --- last part; number of leaves --- first part; height --- number of parts.
|
|
LINKS
|
M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
|
|
FORMULA
|
In A214578 one has defined Q(n)=0 if n is the Matula-Goebel number of a rooted tree that is not a generalized Bethe tree and Q(n) to be a certain polynomial if n corresponds to a generalized Bethe tree. The Maple program makes use of this to find the Matula-Goebel numbers corresponding to the generalized Bethe trees.
|
|
EXAMPLE
|
7 is in the sequence because the corresponding rooted tree is Y, a generalized Bethe tree.
|
|
MAPLE
|
with(numtheory): Q := 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 0 elif n = 2 then 1 elif bigomega(n) = 1 and Q(pi(n)) = 0 then 0 elif bigomega(n) = 1 then sort(expand(1+x*Q(pi(n)))) elif Q(r(n)) <> 0 and Q(s(n)) <> 0 and type(simplify(Q(r(n))/Q(s(n))), constant) = true then sort(Q(r(n))+Q(s(n))) else 0 end if end proc: A := {}; for n to 3000 do if Q(n) = 0 then else A := `union`(A, {n}) end if end do: A;
|
|
CROSSREFS
|
Differs from A243497 for the first time at n=31.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|