A316475 -id:A316475 - cp's OEIS frontend

A316476 Stable numbers. Numbers whose distinct prime indices are pairwise indivisible.

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 19, 23, 25, 27, 29, 31, 32, 33, 35, 37, 41, 43, 45, 47, 49, 51, 53, 55, 59, 61, 64, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 89, 91, 93, 95, 97, 99, 101, 103, 107, 109, 113, 119, 121, 123, 125, 127, 128, 131, 135, 137

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n.

			The prime indices of 45 are {2,2,3}, so the distinct prime indices are {2,3}, which are pairwise indivisible, so 45 belongs to the sequence.
The prime indices of 105 are {2,3,4}, which are not pairwise indivisible (2 divides 4), so 105 does not belong to the sequence.

Cf. A056239, A112798, A285572, A285573, A303362, A304713, A316468, A316475, A327393, A327394, A378442 (characteristic function).

Select[Range[100],Select[Tuples[If[#===1,{},Cases[FactorInteger[#],{p_,k_}:>PrimePi[p]]],2],UnsameQ@@#&&Divisible@@#&]=={}&]

ok(n)={my(v=apply(primepi, factor(n)[,1])); for(j=2, #v, for(i=1, j-1, if(v[j]%v[i]==0, return(0)))); 1} \\ Andrew Howroyd, Aug 26 2018

A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 137, 275, 541, 1098, 2208, 4521, 9240, 19084, 39451, 82113, 171240, 358794, 753460, 1587740, 3353192, 7100909, 15067924, 32044456, 68272854, 145730675, 311575140, 667221030, 1430892924, 3072925944, 6607832422, 14226665499

Offset: 1

N. J. A. Sloane

There is no planted tree on one node by definition.
Column k=2 of A144018. - Alois P. Heinz, Oct 17 2012
It appears that a(n) is also the number of locally non-intersecting unlabeled rooted trees with n nodes, where a tree is locally non-intersecting if the branches directly under of any non-leaf node have empty intersection. - Gus Wiseman, Aug 22 2018

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 10*x^7 + 20*x^8 + 36*x^9 + ...
From _Joerg Arndt_, Jun 23 2014: (Start)
The a(8) = 20 such trees have the following level sequences:
01:  [ 0 1 2 3 4 3 2 1 ]
02:  [ 0 1 2 3 3 3 2 1 ]
03:  [ 0 1 2 3 3 2 2 1 ]
04:  [ 0 1 2 3 3 2 1 1 ]
05:  [ 0 1 2 3 2 3 2 1 ]
06:  [ 0 1 2 3 2 2 2 1 ]
07:  [ 0 1 2 3 2 2 1 1 ]
08:  [ 0 1 2 3 2 1 2 1 ]
09:  [ 0 1 2 3 2 1 1 1 ]
10:  [ 0 1 2 2 2 2 2 1 ]
11:  [ 0 1 2 2 2 2 1 1 ]
12:  [ 0 1 2 2 2 1 2 1 ]
13:  [ 0 1 2 2 2 1 1 1 ]
14:  [ 0 1 2 2 1 2 2 1 ]
15:  [ 0 1 2 2 1 2 1 1 ]
16:  [ 0 1 2 2 1 1 1 1 ]
17:  [ 0 1 2 1 2 1 2 1 ]
18:  [ 0 1 2 1 2 1 1 1 ]
19:  [ 0 1 2 1 1 1 1 1 ]
20:  [ 0 1 1 1 1 1 1 1 ]
Successive levels change by at most 1 and the last level is 1, compare to the example in A000081.
(End)
From _Gus Wiseman_, Aug 22 2018: (Start)
The a(7) = 10 locally non-intersecting trees:
  (o(o(oo)))
  (o(oo(o)))
  (o(oooo))
  (oo(o(o)))
  (oo(ooo))
  (o(o)(oo))
  (ooo(oo))
  (oo(o)(o))
  (oooo(o))
  (oooooo)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000081, A000837, A004111, A007560, A144018, A289509, A316470, A316473, A316475.

with(numtheory): etr:= proc(p) local b; b:= proc(n) option remember; if n=0 then 1 else (add(d*p(d), d=divisors(n)) +add(add(d*p(d), d= divisors(j)) *b(n-j), j=1..n-1))/n fi end end: b:= etr(a): a:= n-> `if`(n<=1, n, b(n-2)): seq(a(n), n=1..40);  # Alois P. Heinz, Sep 06 2008

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, (Sum[ Sum[ d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}] + Sum[ d*p[d], {d, Divisors[n]}])/n]; b]; b = etr[a]; a[n_] := If[n <= 1, n, b[n-2]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Aug 01 2013, after Alois P. Heinz *)
purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Intersection@@#=={}&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[purt[n]],{n,10}] (* Gus Wiseman, Aug 22 2018 *)

{a(n) = local(A); if( n<2, n>0, A = x / (1 - x) + O(x^n); for(k=2, n-2, A /= (1 - x^k + O(x^n))^polcoeff(A, k-1)); polcoeff(A, n-1))}; /* Michael Somos, Oct 06 2003 */

Shifts left 2 places under Euler transform.
G.f.: x + x^2 / (Product_{k>0} (1 - x^k)^a(k)). - Michael Somos, Oct 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.246066877341161662499621547921... and  c = 0.68490297576105466417608032... . - Vaclav Kotesovec, Jun 23 2014
G.f. A(x) satisfies: A(x) = x + x^2 * exp(A(x) + A(x^2)/2 + A(x^3)/3 + A(x^4)/4 + ...). - Ilya Gutkovskiy, Jun 11 2021

Better description from Christian G. Bower, May 15 1998

A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 44, 99, 233, 554, 1346, 3300, 8219, 20635, 52300, 133488, 343033, 886360, 2302133, 6005835

Offset: 1

Gus Wiseman, Jul 04 2018

			The a(5) = 9 locally disjoint rooted trees:
((((o))))
(((oo)))
((o(o)))
((ooo))
(o((o)))
(o(oo))
((o)(o))
(oo(o))
(oooo)

Gus Wiseman, The a(6) = 19 locally disjoint rooted trees.

Cf. A000081, A285573, A302696, A304713, A316468, A316470, A316471, A316475, A316495.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],Select[Tuples[#,2],UnsameQ@@#&&(Intersection@@#=!={})&]=={}&]];
Table[Length[strut[n]],{n,15}]

a(20) from Jinyuan Wang, Jun 20 2020

A316495 Matula-Goebel numbers of locally disjoint unlabeled rooted trees, meaning no branch overlaps any other (unequal) branch of the same root.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 43, 44, 45, 47, 48, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 70, 71, 72, 74, 75, 76, 77, 79, 80, 82, 85

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff either it is equal to 1, it is a prime number whose prime index already belongs to the sequence, or its distinct prime indices are pairwise coprime and already belong to the sequence.

			The sequence of all locally disjoint rooted trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   6: (o(o))
   7: ((oo))
   8: (ooo)
  10: (o((o)))
  11: ((((o))))
  12: (oo(o))
  13: ((o(o)))
  14: (o(oo))
  15: ((o)((o)))
  16: (oooo)
  17: (((oo)))
  18: (o(o)(o))
  19: ((ooo))
  20: (oo((o)))

Cf. A000081, A007097, A302696, A303362, A304713, A316468, A316470, A316473, A316475, A316494.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
go[n_]:=Or[n==1,And[Or[PrimeQ[n],CoprimeQ@@Union[primeMS[n]]],And@@go/@primeMS[n]]];
Select[Range[100],go]

A316470 Matula-Goebel numbers of unlabeled rooted RPMG-trees, meaning the Matula-Goebel numbers of the branches of any non-leaf node are relatively prime.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 14, 16, 18, 24, 26, 28, 32, 36, 38, 42, 48, 52, 54, 56, 64, 72, 74, 76, 78, 84, 86, 96, 98, 104, 106, 108, 112, 114, 122, 126, 128, 144, 148, 152, 156, 162, 168, 172, 178, 182, 192, 196, 202, 208, 212, 214, 216, 222, 224, 228, 234, 244, 252

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff it is 1 or its prime indices are relatively prime and already belong to the sequence.

			The sequence of all RPMG-trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   4: (oo)
   6: (o(o))
   8: (ooo)
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  18: (o(o)(o))
  24: (ooo(o))
  26: (o(o(o)))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  42: (o(o)(oo))

Cf. A000081, A000837, A007097, A289509, A302796, A316468, A316469, A316473, A316475, A316495.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],Or[#==1,And[GCD@@primeMS[#]==1,And@@#0/@primeMS[#]]]&]

A316697 Number of series-reduced locally disjoint rooted trees with n unlabeled leaves.

Original entry on oeis.org

1, 1, 2, 5, 10, 24, 49, 112, 241, 548, 1218, 2839, 6547, 15572, 37179, 90555, 222065, 552576, 1384820, 3506475, 8936121, 22941280

Offset: 1

Gus Wiseman, Jul 10 2018

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other (unequal) branch of the same root.

			The a(5) = 10 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)
Missing from this list but counted by A000669 are ((oo)(o(oo))) and ((oo)(ooo)).

Cf. A000081, A000669, A001678, A141268, A316471, A316471, A316475, A316495.

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
nms[n_]:=nms[n]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],disjointQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,15}]

a(18)-a(22) from Robert Price, Sep 14 2018

A316468 Matula-Goebel numbers of locally stable rooted trees, meaning no branch is a submultiset of any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 23, 25, 27, 31, 32, 33, 35, 45, 47, 49, 51, 53, 55, 59, 64, 67, 69, 75, 77, 81, 83, 85, 93, 95, 97, 99, 103, 119, 121, 125, 127, 128, 131, 135, 137, 141, 149, 153, 155, 161, 165, 175, 177, 187, 197, 201, 207, 209

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff its distinct prime indices are pairwise indivisible and already belong to the sequence.

			Sequence of locally stable rooted trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  11: ((((o))))
  15: ((o)((o)))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  31: (((((o)))))

Cf. A000081, A004111, A007097, A112798, A277098, A285572, A285573, A303362, A304713, A316467, A316470, A316473, A316475, A316476, A316495.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Or[#==1,And[Select[Tuples[primeMS[#],2],UnsameQ@@#&&Divisible@@#&]=={},And@@#0/@primeMS[#]]]&]

A316474 Number of locally stable rooted identity trees with n nodes, meaning no branch is a subset of any other branch of the same root.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 5, 8, 14, 23, 42, 73, 133, 241, 442, 812, 1508, 2802, 5247, 9842, 18554, 35045, 66453, 126249

Offset: 1

Gus Wiseman, Jul 04 2018

			The a(9) = 8 locally stable rooted identity trees:
((((((((o))))))))
(((((o)((o))))))
((((o)(((o))))))
(((o)((((o))))))
((((o))(((o)))))
((o)(((((o))))))
((o)((o)((o))))
(((o))((((o)))))

Gus Wiseman, The a(10) = 14 locally stable rooted identity trees with 10 nodes.

Cf. A000081, A004111, A276625, A277098, A285572, A285573, A303362, A304713, A316467, A316471, A316471, A316475.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],UnsameQ@@#&&Select[Tuples[#,2],UnsameQ@@#&&Complement@@#=={}&]=={}&]];
Table[Length[strut[n]],{n,20}]

A317102 Powerful numbers whose distinct prime multiplicities are pairwise indivisible.

Original entry on oeis.org

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 169, 196, 200, 216, 225, 243, 256, 288, 289, 343, 361, 392, 432, 441, 484, 500, 512, 529, 625, 648, 675, 676, 729, 800, 841, 864, 900, 961, 968, 972, 1000, 1024, 1089, 1125, 1152, 1156, 1225

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

A number is powerful if its prime multiplicities are all greater than 1.

			144 = 2^4 * 3^2 is not in the sequence because 4 and 2 are not pairwise indivisible.

Robert Israel, Table of n, a(n) for n = 1..3000

Cf. A001694, A056239, A112798, A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317101, A317616.

filter:= proc(n) local L,i,j,q;
  L:= convert(map(t -> t[2],ifactors(n)[2]),set);
  if min(L) = 1 then return false fi;
  for j from 2 to nops(L) do
    for i from 1 to j-1 do
      q:= L[i]/L[j];
      if q::integer or (1/q)::integer then return false fi;
  od od;
  true
end proc:
select(filter, [$4..10000]); # Robert Israel, Jun 23 2019

Select[Range[1000],And[Max@@Last/@FactorInteger[#]>=2,Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}]&]

Definition corrected and a(1)=1 inserted by Robert Israel, Jun 23 2019

A328671 Numbers whose binary indices are relatively prime and pairwise indivisible.

Original entry on oeis.org

1, 6, 12, 18, 20, 22, 24, 28, 48, 56, 66, 68, 70, 72, 76, 80, 82, 84, 86, 88, 92, 96, 104, 112, 120, 132, 144, 148, 176, 192, 196, 208, 212, 224, 240, 258, 264, 272, 274, 280, 296, 304, 312, 320, 322, 328, 336, 338, 344, 352, 360, 368, 376, 384, 400, 416, 432

Offset: 1

Gus Wiseman, Oct 29 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The sequence of terms together with their binary expansions and binary indices begins:
    1:         1 ~ {1}
    6:       110 ~ {2,3}
   12:      1100 ~ {3,4}
   18:     10010 ~ {2,5}
   20:     10100 ~ {3,5}
   22:     10110 ~ {2,3,5}
   24:     11000 ~ {4,5}
   28:     11100 ~ {3,4,5}
   48:    110000 ~ {5,6}
   56:    111000 ~ {4,5,6}
   66:   1000010 ~ {2,7}
   68:   1000100 ~ {3,7}
   70:   1000110 ~ {2,3,7}
   72:   1001000 ~ {4,7}
   76:   1001100 ~ {3,4,7}
   80:   1010000 ~ {5,7}
   82:   1010010 ~ {2,5,7}
   84:   1010100 ~ {3,5,7}
   86:   1010110 ~ {2,3,5,7}
   88:   1011000 ~ {4,5,7}

The version for prime indices (instead of binary indices) is A328677.
Numbers whose binary indices are relatively prime are A291166.
Numbers whose distinct prime indices are pairwise indivisible are A316476.
BII-numbers of antichains are A326704.
Relatively prime partitions whose distinct parts are pairwise indivisible are A328676, with strict case A328678.
Cf. A000120, A121016, A285573, A303362, A304713, A305148, A316468, A316475.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[100],GCD@@bpe[#]==1&&stableQ[bpe[#],Divisible]&]

Intersection of A291166 with A326704.

cp's OEIS Frontend

A316476 Stable numbers. Numbers whose distinct prime indices are pairwise indivisible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A007562 Number of planted trees where non-root, non-leaf nodes an even distance from root are of degree 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A316473 Number of locally disjoint rooted trees with n nodes, meaning no branch overlaps any other (unequal) branch of the same root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A316495 Matula-Goebel numbers of locally disjoint unlabeled rooted trees, meaning no branch overlaps any other (unequal) branch of the same root.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316470 Matula-Goebel numbers of unlabeled rooted RPMG-trees, meaning the Matula-Goebel numbers of the branches of any non-leaf node are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316697 Number of series-reduced locally disjoint rooted trees with n unlabeled leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A316468 Matula-Goebel numbers of locally stable rooted trees, meaning no branch is a submultiset of any other branch of the same root.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316474 Number of locally stable rooted identity trees with n nodes, meaning no branch is a subset of any other branch of the same root.

Views

Author

Keywords

Examples

Links