A276625 Finitary numbers. Matula-Goebel numbers of rooted identity trees.

1, 2, 3, 5, 6, 10, 11, 13, 15, 22, 26, 29, 30, 31, 33, 39, 41, 47, 55, 58, 62, 65, 66, 78, 79, 82, 87, 93, 94, 101, 109, 110, 113, 123, 127, 130, 137, 141, 143, 145, 155, 158, 165, 167, 174, 179, 186, 195, 202, 205, 211, 218, 226, 235, 237, 246, 254, 257, 271, 274, 282, 286, 290, 293, 303, 310, 313, 317, 319, 327, 330

Offset: 1

Author

Gus Wiseman, Sep 29 2016

Keywords

• nonn

Comments

For any positive integer n the following are equivalent:

(1) n is a finitary number.

(2) prime(n) is a finitary number.

(3) n is a product of distinct finitary prime numbers.

These conditions are necessary and sufficient to define an infinite set of positive integers but do not specify how this set should be enumerated or indexed (is there a more natural way? viz. A215366) so here they are listed in increasing order of the corresponding Matula-Goebel numbers. The following comment is from A007097.

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. - Emeric Deutsch, Feb 18 2012

Notes on use of the word "finitary": It is possible to have a finite set containing an infinite set. For example {{1,2,3...}} contains only one element. In contrast, a finitary set is a finite set whose elements are also required to be finitary sets. There are also no multisets allowed in finitary sets, although you can have repeated elements. For example {{{}},{{},{{}}}} is still considered a finitary set even though the multiset union {{},{},{{}}} is not a set. The finitary numbers of A276625 refer to multisets (trees) that don't involve any proper multisets (i.e. only sets). This is in addition to the (somewhat redundant) meaning of finitary sets as described in this comment on A004111 "There is a natural correspondence between rooted identity trees and finitary sets (sets whose transitive closure is finite); each node represents a set, with the children of that node representing the members of that set. When the set corresponding to an identity tree is written out using braces, there is one set of braces for each node of the tree; thus a(n) is also the number of sets that can be made using n pairs of braces. - Franklin T. Adams-Watters, Oct 25 2011" - Gus Wiseman, Oct 03 2016

Examples

			This sequence is proposed to be a canonical representation for rooted identity trees. The first thirty terms are the following.
1  ()           26 (()(()(())))     62  (()((((())))))
2  (())         29 ((()((()))))     65  (((()))(()(())))
3  ((()))       30 (()(())((())))   66  (()(())(((()))))
5  (((())))     31 (((((())))))     78  (()(())(()(())))
6  (()(()))     33 ((())(((()))))   79  ((()(((())))))
10 (()((())))   39 ((())(()(())))   82  (()((()(()))))
11 ((((()))))   41 (((()(()))))     87  ((())(()((()))))
13 ((()(())))   47 (((())((()))))   93  ((())((((())))))
15 ((())((()))) 55 (((()))(((())))) 94  (()((())((()))))
22 (()(((())))) 58 (()(()((()))))   101 ((()(()(()))))
We build the sequence as follows: The empty product is 1, so by (3) 1 is finitary. So is prime(1) = 2 by (2), so is prime(2) = 3 by (2), so is prime(3) = 5 by (2), so is 2*3 = 6 by (3), and so on. - _N. J. A. Sloane_, Oct 03 2016
		

Links

• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Cf. A000040 (prime numbers), A000720 (PrimePi).

Cf. A004111 (identity trees), A116540 (set multipartitions). Contained in A005117 (squarefree numbers). Contains A076146 (ordinal numbers), A007097 (rooted paths), A277098 (finitary primes).

Cf. A206497 (automorphism group sizes), A348066 (reduce to identity tree).

Programs

Mathematica

primeMS[n_Integer?Positive]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
finitaryQ[n_Integer?Positive]:=finitaryQ[n]=Or[n===1,With[{m=primeMS[n]},{UnsameQ@@m,finitaryQ/@m}]/.List->And];
fin[n_Integer?Positive]:=If[n===1,1,Block[{x=fin[n-1]+1},While[Not[finitaryQ[x]],x++];x]];
Array[fin,200]

Formula

a(n) = primePi(A277098(n)).