login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A276625 Finitary numbers. Matula-Goebel numbers of rooted identity trees. 120
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 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

LINKS

Table of n, a(n) for n=1..71.

Index entries for sequences related to Matula-Goebel 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[n-1]+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).

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 15:14 EDT 2019. Contains 328030 sequences. (Running on oeis4.)