A076146 -id:A076146 - cp's OEIS frontend

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

Gus Wiseman, Sep 29 2016

nonn

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

			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

Index entries for sequences related to Matula-Goebel numbers

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

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]

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

A062457 a(n) = prime(n)^n.

Original entry on oeis.org

2, 9, 125, 2401, 161051, 4826809, 410338673, 16983563041, 1801152661463, 420707233300201, 25408476896404831, 6582952005840035281, 925103102315013629321, 73885357344138503765449, 12063348350820368238715343, 3876269050118516845397872321

Offset: 1

Labos Elemer, Jul 09 2001

Heinz numbers of square integer partitions, where the Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). - Gus Wiseman, Apr 14 2018
Main diagonal of A182944. - Omar E. Pol, Sep 12 2018
Second diagonal of A319075. - Omar E. Pol, Sep 13 2018

T. D. Noe, Table of n, a(n) for n = 1..100

Cf. A000040, A000312, A000720, A000961, A001222, A051674, A062006, A076146, A093358, A201614, A275024, A302242, A302493, A302498, A319075.

[NthPrime(n)^n : n in [1..20]]; // Wesley Ivan Hurt, Jan 18 2016

A062457:=n->ithprime(n)^n: seq(A062457(n), n=1..20); # Wesley Ivan Hurt, Jan 18 2016

Table[Prime[n]^n, {n,20}] (* Harvey P. Dale, Jun 22 2011 *)

a(n) = prime(n)^n; \\ Harry J. Smith, Aug 07 2009

a(n) = A062006(n) - 1. - Wesley Ivan Hurt, Jan 18 2016
From Amiram Eldar, Nov 16 2020: (Start)
Sum_{n>=1} 1/a(n) = A093358.
Sum_{n>=1} (-1)^(n+1)/a(n) = A201614. (End)

A033286 a(n) = n * prime(n).

Original entry on oeis.org

2, 6, 15, 28, 55, 78, 119, 152, 207, 290, 341, 444, 533, 602, 705, 848, 1003, 1098, 1273, 1420, 1533, 1738, 1909, 2136, 2425, 2626, 2781, 2996, 3161, 3390, 3937, 4192, 4521, 4726, 5215, 5436, 5809, 6194, 6513, 6920, 7339, 7602, 8213, 8492, 8865, 9154, 9917

Offset: 1

N. J. A. Sloane

Does an n exist such that n*prime(n)/(n+prime(n)) is an integer? - Ctibor O. Zizka, Mar 04 2008. The answer to Zizka's question is easily seen to be No: such an integer k would be positive and less than prime(n), but then k*(n + prime(n)) = prime(n)*n would be impossible. - Robert Israel, Apr 20 2015
Sums of rows of the triangle in A005145. - Reinhard Zumkeller, Aug 05 2009
Complement of A171520(n). - Jaroslav Krizek, Dec 13 2009
Partial sums of A090942. - Omar E. Pol, Apr 20 2015

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Albert Frank, International Contest Of Logical Sequences, 2002 - 2003. Item 1.
Albert Frank, Solutions of International Contest Of Logical Sequences, 2002 - 2003.

Cf. A000040, A007504, A014689, A090942, A124012, A141042, A152535.

Cf. A005145 (primes repeated), A171520 (complement), A076146 (iterated).

a033286 n = a000040 n * n  -- Reinhard Zumkeller, Jul 24 2013

[ n*NthPrime(n): n in [1..47] ]; // Klaus Brockhaus, Sep 09 2009

A033286 := proc(n) n*ithprime(n) ; end proc:
seq(A033286(n),n=1..20) ; # R. J. Mathar, Mar 21 2011

Table[Prime[n]*n, {n, 38}] (* Alonso del Arte *)

ithprime(i)*i $ i = 1..47 // Zerinvary Lajos, Feb 26 2007

a(n)=n*prime(n) \\ Charles R Greathouse IV, Jul 01 2013

a(n) = n * A000040(n) = n * A008578(n+1) = n * A158611(n+2). - Jaroslav Krizek, Aug 31 2009
a(n) = A007504(n) + A152535(n). - Omar E. Pol, Aug 09 2012
Sum_{n>=1} 1/a(n) = A124012. - Amiram Eldar, Oct 15 2020

Correction for change of offset in A158611 and A008578 in Aug 2009 from Jaroslav Krizek, Jan 27 2010

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 3, 4, 5, 3, 4, 3, 4, 2, 4, 3, 3, 4, 4, 5, 4, 3, 4, 4, 3, 3, 5, 4, 6, 2, 5, 4, 5, 3, 4, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 3, 3, 4, 5, 4, 3, 3, 5, 3, 4, 5, 5, 4, 4, 6, 4, 2, 5, 5, 4, 4, 4, 5, 5, 3, 5, 4, 4, 3, 6, 4, 6, 4, 3, 5, 5, 4, 6, 4, 5, 5, 4, 4, 5, 4, 6, 5, 5, 3, 5, 3, 5, 4, 5, 5, 4, 4, 5, 3, 4, 3

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

			20 is the Matula-Goebel number of the tree (oo((o))), which has 4 distinct terminal subtrees: {(oo((o))), ((o)), (o), o}. So a(20) = 4.
See also illustrations in A061773.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to Matula-Göbel numbers

One more than A324923.

Cf. A000081, A007097, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476.

ids[n_]:=Union@@FixedPointList[Union@@(Cases[If[#==1,{},FactorInteger[#]],{p_,_}:>PrimePi[p]]&/@#)&,{n}];
Table[Length[ids[n]],{n,100}]

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A324923(n) = { my(lista = List([]), gpf, i); while(n > 1, gpf=A006530(n); i = primepi(gpf); n /= gpf; n *= i; listput(lista,i)); #Set(lista); }; \\ Antti Karttunen, Oct 23 2023
A317713(n) = (1+A324923(n)); \\ Antti Karttunen, Oct 23 2023

a(n) = 1+A324923(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A290760 Matula-Goebel numbers of transitive rooted identity trees (or transitive finitary sets).

Original entry on oeis.org

1, 2, 6, 30, 78, 330, 390, 870, 1410, 3198, 3390, 4290, 7878, 9570, 10230, 11310, 13026, 15510, 15990, 18330, 26070, 30966, 37290, 39390, 40890, 44070, 45210, 65130, 84810, 94830, 98310, 104610, 122070, 124410, 132990, 154830, 159330, 175890, 198330, 201630

Offset: 1

Gus Wiseman, Oct 19 2017

nonn

A rooted tree is transitive if every terminal subtree is a branch of the root. A finitary set is transitive if every element is also a subset.

			Let o = {}. The sequence of transitive finitary sets begins:
1     o
2     {o}
6     {o,{o}}
30    {o,{o},{{o}}}
78    {o,{o},{o,{o}}}
330   {o,{o},{{o}},{{{o}}}}
390   {o,{o},{{o}},{o,{o}}}
870   {o,{o},{{o}},{o,{{o}}}}
1410  {o,{o},{{o}},{{o},{{o}}}}
3198  {o,{o},{o,{o}},{{o,{o}}}}
3390  {o,{o},{{o}},{o,{o},{{o}}}}
4290  {o,{o},{{o}},{{{o}}},{o,{o}}}
7878  {o,{o},{o,{o}},{o,{o,{o}}}}
9570  {o,{o},{{o}},{{{o}}},{o,{{o}}}}
10230 {o,{o},{{o}},{{{o}}},{{{{o}}}}}
11310 {o,{o},{{o}},{o,{o}},{o,{{o}}}}
13026 {o,{o},{o,{o}},{{o},{o,{o}}}}
15510 {o,{o},{{o}},{{{o}}},{{o},{{o}}}}
15990 {o,{o},{{o}},{o,{o}},{{o,{o}}}}
18330 {o,{o},{{o}},{o,{o}},{{o},{{o}}}}

Cf. A000081, A001192, A004111, A007097, A076146, A276625, A279861, A290689, A290822.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
finitaryQ[n_]:=finitaryQ[n]=Or[n===1,With[{m=primeMS[n]},{UnsameQ@@m,finitaryQ/@m}]/.List->And];
subprimes[n_]:=If[n===1,{},Union@@Cases[FactorInteger[n],{p_,_}:>FactorInteger[PrimePi[p]][[All,1]]]];
transitaryQ[n_]:=Divisible[n,Times@@subprimes[n]];
nn=100000;Fold[Select,Range[nn],{finitaryQ,transitaryQ}]

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 5, 4, 5, 3, 4, 3, 7, 2, 4, 5, 3, 4, 5, 5, 6, 3, 10, 4, 9, 3, 5, 7, 6, 2, 9, 4, 7, 5, 4, 3, 7, 4, 5, 5, 4, 5, 13, 6, 8, 3, 5, 10, 7, 4, 3, 9, 13, 3, 5, 5, 5, 7, 6, 6, 9, 2, 10, 9, 4, 4, 11, 7, 5, 5, 6, 4, 19, 3, 9, 7, 6, 4, 17, 5, 7, 5

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

We require that an initial subtree contain either all or none of the branchings under any given node.

			70 is the Matula-Goebel number of the tree (o((o))(oo)), which has 7 distinct initial subtrees: {o, (ooo), (oo(oo)), (o(o)o), (o(o)(oo)), (o((o))o), (o((o))(oo))}. So a(70) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476, A317713.

si[n_]:=If[n==1,1,1+Product[si[PrimePi[b[[1]]]]^b[[2]],{b,FactorInteger[n]}]];
Array[si,100]

a(1) = 1 and if n > 1 has prime factorization n = prime(x_1)^y_1 * ... * prime(x_k)^y_k then a(n) = 1 + a(x_1)^y_1 * ... * a(x_k)^y_k.

A348067 Matula-Goebel tree number of tree n with a new leaf added below each existing vertex.

Original entry on oeis.org

2, 6, 26, 18, 202, 78, 122, 54, 338, 606, 2462, 234, 794, 366, 2626, 162, 1346, 1014, 502, 1818, 1586, 7386, 4546, 702, 20402, 2382, 4394, 1098, 8914, 7878, 43954, 486, 32006, 4038, 12322, 3042, 2962, 1506, 10322, 5454, 12178, 4758, 4946, 22158, 34138, 13638

Offset: 1

Kevin Ryde, Oct 01 2021

nonn

k times nested a(a(...a(1))) = A076146(k+1) is the Matula-Goebel number of the binomial tree order k constructed by an "expansion" method starting from a singleton and successively adding a new leaf under every vertex.

			tree n=6   tree a(6) = 78
  R             R___        root R
  | \           |\  \
  A  B          A @  B      new vertices
  |             |\    \     "@" below each
  C             C @    @    existing
                 \
                  @

Cf. A027746 (prime factors), A076146 (binomial tree).

Cf. A297002 (add leaves under children of the root).

a(n) = my(f=factor(n)); 2*factorback([prime(self()(primepi(p))) | p<-f[,1]], f[,2]);

a(n) = 2 * Product_{i=1..k} prime(a(primepi(p[i]))), where n = p[1]*...*p[k] is the prime factorization of n with multiplicity (A027746).

A358650 Matula-Goebel tree number of the binomial tree of n vertices.

Original entry on oeis.org

1, 2, 4, 6, 12, 18, 42, 78, 156, 234, 546, 1014, 2886, 4758, 14118, 30966, 61932, 92898, 216762, 402558, 1145742, 1888926, 5604846, 12293502, 28210026, 45860646, 121727346, 249864654, 813198126, 1423166394, 4740553974, 11234495766, 22468991532, 33703487298

Offset: 1

Kevin Ryde, Nov 25 2022

The top-down definition of the binomial tree suits Matula-Goebel numbering: The tree of n = 2^k + r vertices, for 1 <= r <= 2^k is the binomial tree of 2^k vertices and a child subtree under the root which is the binomial tree of r vertices.

In the tree of n vertices, adding a new singleton child under each vertex gives the tree of 2*n vertices, so that a(2*n) = A348067(a(n)).

			The tree of n=13 vertices numbered 0..12 is
  0
  | \  \    \
  1  2  4     8
     |  | \   | \  \
     3  5  6  9 10  12
           |     |
           7    11
Vertices 0..7 are the binomial tree of 2^k = 8 vertices, and vertices 8..12 are the binomial tree of 5 vertices.
Using the recurrence, a(13) = a(8 + 5) = a(8) * prime(a(5)) = 78*37 = 2886.

Kevin Ryde, Table of n, a(n) for n = 1..117
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A076146, A348067.

PARI
```
\\ See links.
```

a(2^k + r) = a(2^k) * prime(a(r)) for 1 <= r <= 2^k.

a(2^k) = A076146(k+1), being a tree of order k.

A292433 a(0) = 0, a(1) = 1; a(n) = prime(a(n-1))*a(n-1) + a(n-2).

Original entry on oeis.org

0, 1, 2, 7, 121, 79988, 81600798165, 182421074243967704954243

Offset: 0

Ilya Gutkovskiy, Dec 08 2017

			+---+-------------+--------------------+-------------------+
| n | a(n)/a(n+1) | Continued fraction |      Comment      |
+---+-------------+--------------------+-------------------+
| 1 |    1/2      | [0; 2]             |   2 = prime(a(1)) |
+---+-------------+--------------------+-------------------+
| 2 |    2/7      | [0; 3, 2]          |   3 = prime(a(2)) |
+---+-------------+--------------------+-------------------+
| 3 |    7/121    | [0; 17, 3, 2]      |  17 = prime(a(3)) |
+---+-------------+--------------------+-------------------+
| 4 |  121/79988  | [0; 661, 17, 3, 2] | 661 = prime(a(4)) |
+---+-------------+--------------------+-------------------+

Cf. A000040, A000278, A006277, A007097, A036247, A036248, A058182, A076146, A083659.

RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == Prime[a[n - 1]] a[n - 1] + a[n - 2]}, a[n], {n, 7}]

A333373 a(n) = n + 1 for n <= 1; thereafter a(n) = a(n-1) * prime(gpf(a(n-1))).

Original entry on oeis.org

1, 2, 6, 30, 330, 10230, 1299210, 921139890, 4956653748090, 261270175715571990, 169405230502395438168090, 1649555141343581679123602303970, 287748466487735183193170029972221262770, 1052440045241486547790272887133572295775622539770

Offset: 0

Ilya Gutkovskiy, Mar 17 2020

nonn

For n > 1, a(n) belongs to A083207 (see "product" formula below and my Jan 16 2020 comment in A083207). - Ivan N. Ianakiev, Mar 17 2020

			a(7) = a(6) * prime(gpf(a(6))) = prime(1) * prime(2) * prime(3) * prime(5) * prime(11) * prime(31) * prime(127) = 2 * 3 * 5 * 11 * 31 * 127 * 709 = 921139890.

Cf. A006450, A006530, A007097, A052126, A076146, A156061.

a[0] = 1; a[n_] := a[n] = a[n - 1] Prime[FactorInteger[a[n - 1]][[-1, 1]]]; Table[a[n], {n, 0, 13}]
Table[Times @@ NestList[Prime@# &, 1, n], {n, 0, 13}]

a(n) = Product_{k=0..n} A007097(k).
A156061(a(n+1)) = a(n).
A052126(a(n+1)) = a(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A062457 a(n) = prime(n)^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A033286 a(n) = n * prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Formula

Extensions

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A290760 Matula-Goebel numbers of transitive rooted identity trees (or transitive finitary sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A348067 Matula-Goebel tree number of tree n with a new leaf added below each existing vertex.

Views

Author

Keywords

Comments

Examples

Links