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

%I #37 Mar 17 2022 23:59:36

%S 4,14,49,86,301,454,886,1589,1849,3101,3986,6418,9761,13766,13951,

%T 19049,22463,26798,31754,48181,51529,57026,75266,85699,93793,100561,

%U 111139,128074,137987,196249,199591,203878,263431,295969,298154,302426,426058,448259,452411

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

%C 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

%H Charles R Greathouse IV, <a href="/A111299/b111299.txt">Table of n, a(n) for n = 1..186</a>

%H Keith Briggs, <a href="http://keithbriggs.info/matula.html">Matula numbers and rooted trees</a>

%H F. Goebel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.

%H D. Matula, <a href="http://www.jstor.org/stable/2027327?seq=30">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%F The Matula tree of k is defined as follows:

%F matula(k):

%F create a node labeled k

%F for each prime factor m of k:

%F add the subtree matula(prime(m)), by an edge labeled m

%F return the node

%e From _Gus Wiseman_, May 04 2021: (Start)

%e The sequence of trees (starting with 1) begins:

%e 1: o

%e 4: (oo)

%e 14: (o(oo))

%e 49: ((oo)(oo))

%e 86: (o(o(oo)))

%e 301: ((oo)(o(oo)))

%e 454: (o((oo)(oo)))

%e 886: (o(o(o(oo))))

%e 1589: ((oo)((oo)(oo)))

%e 1849: ((o(oo))(o(oo)))

%e 3101: ((oo)(o(o(oo))))

%e 3986: (o((oo)(o(oo))))

%e 6418: (o(o((oo)(oo))))

%e 9761: ((o(oo))((oo)(oo)))

%e (End)

%t nn=20000;

%t primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];

%t Select[Range[2,nn],binQ] (* _Gus Wiseman_, Aug 28 2017 *)

%o (PARI) i(n)=n==2 || is(primepi(n))

%o 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

%o (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

%Y Cf. A245824 (by number of leaves).

%Y Cf. A005517, A005518, A061773, A245824.

%Y These trees are counted by 2*A001190 - 1.

%Y The semi-binary version is A292050 (counted by A001190).

%Y The semi-identity case is A339193 (counted by A063895).

%Y A000081 counts unlabeled rooted trees with n nodes.

%Y A007097 ranks rooted chains.

%Y A276625 ranks identity trees, counted by A004111.

%Y A306202 ranks semi-identity trees, counted by A306200.

%Y A306203 ranks balanced semi-identity trees, counted by A306201.

%Y A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.

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

%K nonn

%O 1,1

%A _Keith Briggs_, Nov 02 2005

%E Definition corrected by _Charles R Greathouse IV_, Mar 29 2013

%E a(27)-a(39) from _Charles R Greathouse IV_, Mar 29 2013