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

Offset: 1

Author

Keith Briggs, Nov 02 2005

Keywords

• nonn

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

Examples

			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)
		

Links

• 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

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.

Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

Programs

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

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

PARI

\\ Also see links.

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

Extensions

Definition corrected by Charles R Greathouse IV, Mar 29 2013

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