A111299 - OEIS

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..186

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.

Index entries for sequences related to Matula-Goebel numbers

FORMULA

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

EXAMPLE

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)

MATHEMATICA

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

PROG

(PARI) 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

(PARI) 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

CROSSREFS

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.