

A276625


Finitary numbers. MatulaGoebel numbers of rooted identity trees.


138



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 MatulaGoebel numbers. The following comment is from A007097.
The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel 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 MatulaGoebel 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. AdamsWatters, Oct 25 2011."  Gus Wiseman, Oct 03 2016


LINKS

Table of n, a(n) for n=1..71.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

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


EXAMPLE

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


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[n1]+1}, While[Not[finitaryQ[x]], x++]; x]];
Array[fin, 200]


CROSSREFS

Cf. A000040 (prime numbers), 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).
Sequence in context: A302494 A302534 A063451 * A297571 A316503 A316494
Adjacent sequences: A276622 A276623 A276624 * A276626 A276627 A276628


KEYWORD

nonn


AUTHOR

Gus Wiseman, Sep 29 2016


STATUS

approved



