A000837 -id:A000837 - cp's OEIS frontend

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.

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[#]]]&]

A356606 Number of strict integer partitions of n where all parts have neighbors.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 2, 3, 2, 2, 5, 2, 4, 5, 5, 4, 8, 5, 7, 9, 8, 8, 13, 10, 11, 16, 13, 15, 20, 18, 18, 27, 21, 26, 31, 30, 30, 43, 34, 42, 49, 48, 48, 65, 56, 65, 76, 74, 77, 97, 88, 98, 117, 111, 119, 143, 137, 146, 175, 165, 182, 208

Offset: 0

Gus Wiseman, Aug 24 2022

nonn

A part x has a neighbor if either x - 1 or x + 1 is a part.

			The a(n) partitions for n = 0, 1, 3, 9, 15, 18, 20, 24 (A = 10, B = 11):
  ()  .  (21)  (54)   (87)     (765)    (7643)   (987)
               (432)  (654)    (6543)   (8732)   (8754)
                      (54321)  (7632)   (9821)   (9843)
                               (8721)   (65432)  (A932)
                               (65421)           (BA21)
                                                 (87432)
                                                 (87621)
                                                 (765321)

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 301 terms from John Tyler Rascoe)
John Tyler Rascoe, Python program

This is the strict case of A355393 and A355394.
The complement is counted by A356607, non-strict A356235 and A356236.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A137921, A325160, A328171, A328172, A328187, A328220, A328221, A356237.

Table[Length[Select[IntegerPartitions[n], Function[ptn,UnsameQ@@ptn&&And@@Table[MemberQ[ptn,x-1]||MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

Python
```
# see linked program
```

G.f.: 1 + Sum_{i>0} A(x,i), where A(x,i) = x^((2*i)+1) * G(x,i+1) for i > 0, is the g.f. for partitions of this kind with least part i, and G(x,k) = 1 + x^(k+1) * G(x,k+1) + Sum_{m>=0} x^(2*(k+m)+5) * G(x,m+k+3). - John Tyler Rascoe, Feb 16 2024

A055684 Number of different n-pointed stars.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 2, 1, 4, 1, 5, 2, 3, 3, 7, 2, 8, 3, 5, 4, 10, 3, 9, 5, 8, 5, 13, 3, 14, 7, 9, 7, 11, 5, 17, 8, 11, 7, 19, 5, 20, 9, 11, 10, 22, 7, 20, 9, 15, 11, 25, 8, 19, 11, 17, 13, 28, 7, 29, 14, 17, 15, 23, 9, 32, 15, 21, 11, 34, 11, 35, 17, 19, 17, 29, 11

Offset: 3

Robert G. Wilson v, Jun 09 2000

Does not count rotations or reflections.
This is also the distinct ways of writing a number as the sum of two positive integers greater than one that are coprimes. - Lei Zhou, Mar 19 2014
Equivalently, a(n) is the number of relatively prime 2-part partitions of n without 1's. The Heinz numbers of these partitions are the intersection of A001358 (pairs), A005408 (no 1's), and A000837 (relatively prime) or A302696 (pairwise coprime). - Gus Wiseman, Oct 28 2020

			The first star has five points and is unique. The next is the seven pointed star and it comes in two varieties.
From _Gus Wiseman_, Oct 28 2020: (Start)
The a(5) = 1 through a(17) = 7 irreducible pairs > 1 (shown as fractions, empty column indicated by dot):
  2/3  .  2/5  3/5  2/7  3/7  2/9  5/7  2/11  3/11  2/13  3/13  2/15
          3/4       4/5       3/8       3/10  5/9   4/11  5/11  3/14
                              4/7       4/9         7/8   7/9   4/13
                              5/6       5/8                     5/12
                                        6/7                     6/11
                                                                7/10
                                                                8/9
(End)

Mark A. Herkommer, "Number Theory, A Programmer's Guide," McGraw-Hill, New York, 1999, page 58.

Lei Zhou, Table of n, a(n) for n = 3..10002
Alexander Bogomolny, Polygons: formality and intuition.. Includes applet to draw star polygons.
Vi Hart, Doodling in Math Class: Stars, Video (2010).
Hugo Pfoertner, Star-shaped regular polygons up to n=25.
Eric Weisstein's World of Mathematics, Star Polygon

Cf. A023022.
Cf. A053669 smallest skip increment, A102302 skip increment of densest star polygon.
A055684*2 is the ordered version.
A082023 counts the complement (reducible pairs > 1).
A220377, A337563, and A338332 count triples instead of pairs.
A000837 counts relatively prime partitions, with strict case A078374.
A002865 counts partitions with no 1's, with strict case A025147.
A007359 and A337485 count pairwise coprime partitions with no 1's.
A302698 counts relatively prime partitions with no 1's, with strict case A337452.
A327516 counts pairwise coprime partitions, with strict case A305713.
A337450 counts relatively prime compositions with no 1's, with strict case A337451.
Cf. A001399, A101268, A140106, A337461, A337462, A338333.

with(numtheory): A055684 := n->(phi(n)-2)/2; seq(A055684(n), n=3..100);

Table[(EulerPhi[n]-2)/2, {n, 3, 50}]
Table[Length[Select[IntegerPartitions[n,{2}],!MemberQ[#,1]&&CoprimeQ@@#&]],{n,0,30}] (* Gus Wiseman, Oct 28 2020 *)

a(n) = A023022(n) - 1.

a(n) + A082023(n) = A140106(n). - Gus Wiseman, Oct 28 2020

A302697 Odd numbers whose prime indices are relatively prime. Heinz numbers of integer partitions with no 1's and with relatively prime parts.

Original entry on oeis.org

15, 33, 35, 45, 51, 55, 69, 75, 77, 85, 93, 95, 99, 105, 119, 123, 135, 141, 143, 145, 153, 155, 161, 165, 175, 177, 187, 195, 201, 205, 207, 209, 215, 217, 219, 221, 225, 231, 245, 249, 253, 255, 265, 275, 279, 285, 287, 291, 295, 297, 309, 315, 323, 327, 329

Offset: 1

Gus Wiseman, Apr 11 2018

nonn

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

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of integer partitions with no 1's and with relatively prime parts begins:
015: (3,2)
033: (5,2)
035: (4,3)
045: (3,2,2)
051: (7,2)
055: (5,3)
069: (9,2)
075: (3,3,2)
077: (5,4)
085: (7,3)
093: (11,2)
095: (8,3)
099: (5,2,2)
105: (4,3,2)
119: (7,4)
123: (13,2)
135: (3,2,2,2)

Cf. A000837, A000961, A001222, A005117, A007359, A051424, A076078, A101268, A275024, A285572, A289509, A298748, A302568, A302569, A302696, A302698.

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

A318990 Numbers of the form prime(x) * prime(y) where x divides y.

Original entry on oeis.org

4, 6, 9, 10, 14, 21, 22, 25, 26, 34, 38, 39, 46, 49, 57, 58, 62, 65, 74, 82, 86, 87, 94, 106, 111, 115, 118, 121, 122, 129, 133, 134, 142, 146, 158, 159, 166, 169, 178, 183, 185, 194, 202, 206, 213, 214, 218, 226, 235, 237, 254, 259, 262, 267, 274, 278, 289

Offset: 1

Gus Wiseman, Sep 06 2018

nonn

			The sequence of all dividing pairs (columns) begins:
  1  1  2  1  1  2  1  3  1  1  1  2  1  4  2  1  1  3  1  1  1  2  1  1
  1  2  2  3  4  4  5  3  6  7  8  6  9  4  8 10 11  6 12 13 14 10 15 16

Andrew Howroyd, Table of n, a(n) for n = 1..10000

A subset of A001358 (semiprimes), squarefree A006881.
The squarefree version is A339005.
The quotient is A358103 = A358104 / A358105.
A000040 lists the primes.
A001222 counts prime indices, distinct A001221.
A003963 multiplies together prime indices.
A056239 adds up prime indices.
A358192/A358193 gives quotients of semiprime indices.
Cf. A000837, A300912, A318991, A318992, A318993.
Cf. A000720, A027751, A032741, A215366, A296150.
Cf. A289508, A289509, A358106.

Select[Range[100],And[PrimeOmega[#]==2,Or[PrimePowerQ[#],Divisible@@Reverse[PrimePi/@FactorInteger[#][[All,1]]]]]&]

ok(n)={my(f=factor(n)); bigomega(f)==2 && (#f~==1 || primepi(f[2,1]) % primepi(f[1,1]) == 0)} \\ Andrew Howroyd, Oct 26 2018

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 3, 38, 4, 46, 19, 58, 9, 94, 18, 106, 41, 144, 28, 221, 37, 246, 92, 318, 87, 465, 95, 530, 198, 693, 169, 963, 220, 1108, 424, 1383, 381, 1899, 492, 2216, 815, 2732, 799, 3644, 1041, 4231, 1585, 5194, 1608

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

			The a(1) = 1 through a(15) = 9 partitions (A..F = 10..15):
  1  2  3  4   5  6    7  8     9    A      B  C       D  E        F
           22     33      44    63   55        66         77       96
                  42      62    333  64        84         86       A5
                  222     422        82        93         A4       C3
                          2222       442       A2         C2       555
                                     622       444        644      663
                                     4222      633        662      933
                                     22222     642        842      6333
                                               822        A22      33333
                                               3333       4442
                                               4422       6422
                                               6222       8222
                                               42222      44222
                                               222222     62222
                                                          422222
                                                          2222222

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..300

The Heinz numbers of these partitions are given by A328336.
The case of compositions is A178470.
The strict case is A328220.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Cf. A000837, A018783, A328028, A328170, A328171, A328188.

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A000741 Number of compositions of n into 3 ordered relatively prime parts.

Original entry on oeis.org

0, 0, 1, 3, 6, 9, 15, 18, 27, 30, 45, 42, 66, 63, 84, 84, 120, 99, 153, 132, 174, 165, 231, 180, 270, 234, 297, 270, 378, 276, 435, 360, 450, 408, 540, 414, 630, 513, 636, 552, 780, 558, 861, 690, 828, 759, 1035, 744, 1113, 870, 1104, 972, 1326, 945, 1380, 1116, 1386, 1218

Offset: 1

N. J. A. Sloane

			From _Gus Wiseman_, Oct 14 2020: (Start)
The a(3) = 1 through a(8) = 18 triples:
  (1,1,1)  (1,1,2)  (1,1,3)  (1,1,4)  (1,1,5)  (1,1,6)
           (1,2,1)  (1,2,2)  (1,2,3)  (1,2,4)  (1,2,5)
           (2,1,1)  (1,3,1)  (1,3,2)  (1,3,3)  (1,3,4)
                    (2,1,2)  (1,4,1)  (1,4,2)  (1,4,3)
                    (2,2,1)  (2,1,3)  (1,5,1)  (1,5,2)
                    (3,1,1)  (2,3,1)  (2,1,4)  (1,6,1)
                             (3,1,2)  (2,2,3)  (2,1,5)
                             (3,2,1)  (2,3,2)  (2,3,3)
                             (4,1,1)  (2,4,1)  (2,5,1)
                                      (3,1,3)  (3,1,4)
                                      (3,2,2)  (3,2,3)
                                      (3,3,1)  (3,3,2)
                                      (4,1,2)  (3,4,1)
                                      (4,2,1)  (4,1,3)
                                      (5,1,1)  (4,3,1)
                                               (5,1,2)
                                               (5,2,1)
                                               (6,1,1)
(End)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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..10000
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
N. J. A. Sloane, Transforms

A000010 is the length-2 version.
A000217(n-2) does not require relative primality.
A000740 counts these compositions of any length.
A000742 is the length-4 version.
A000837 counts relatively prime partitions.
A023023 is the unordered version.
A101271 is the strict case.
A101391 has this as column k = 3.
A284825*6 is the pairwise non-coprime case.
A291166 intersected with A014311 ranks these compositions.
A337461 is the pairwise coprime instead of relatively prime version.
A337603 counts length-3 compositions whose distinct parts are pairwise coprime.
A337604 is the pairwise non-coprime instead of relatively prime version.
Cf. A001399, A007997, A023022, A078374, A337450, A337451, A337602.

with(numtheory):
mobtr:= proc(p)
          proc(n) option remember;
            add(mobius(n/d)*p(d), d=divisors(n))
          end
        end:
A000217:= n-> n*(n+1)/2:
a:= mobtr(n-> A000217(n-2)):
seq(a(n), n=1..58);  # Alois P. Heinz, Feb 08 2011

mobtr[p_] := Module[{f}, f[n_] := f[n] = Sum[MoebiusMu[n/d]*p[d], {d, Divisors[n]}]; f]; A000217[n_] := n*(n+1)/2; a = mobtr[A000217[#-2]&]; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Mar 12 2014, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{3}],GCD@@#==1&]],{n,0,30}] (* Gus Wiseman, Oct 14 2020 *)

Moebius transform of A000217(n-2).

G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = (1 - 3*x + 3*x^2)/(1 - x)^3. - Ilya Gutkovskiy, Apr 26 2017

Edited by Alois P. Heinz, Feb 08 2011

A356607 Number of strict integer partitions of n with at least one neighborless part.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 3, 4, 6, 6, 9, 11, 13, 17, 20, 24, 30, 36, 41, 52, 60, 71, 84, 100, 114, 137, 158, 183, 214, 248, 283, 330, 379, 432, 499, 570, 648, 742, 846, 955, 1092, 1234, 1395, 1580, 1786, 2005, 2270, 2548, 2861, 3216, 3610, 4032, 4526, 5055, 5642, 6304, 7031, 7820, 8720, 9694

Offset: 0

Gus Wiseman, Aug 26 2022

nonn

A part x is neighborless if neither x - 1 nor x + 1 are parts.

			The a(0) = 0 through a(9) = 6 partitions:
  .  (1)  (2)  (3)  (4)   (5)   (6)   (7)    (8)    (9)
                    (31)  (41)  (42)  (52)   (53)   (63)
                                (51)  (61)   (62)   (72)
                                      (421)  (71)   (81)
                                             (431)  (531)
                                             (521)  (621)

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 101 terms from Lucas A. Brown)
Lucas A. Brown, A356607.py

This is the strict case of A356235 and A356236.
The complement is counted by A356606, non-strict A355393 and A355394.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A073492, A137921, A325160, A328171, A328172, A328187, A328220, A328221.

Table[Length[Select[IntegerPartitions[n],Function[ptn,UnsameQ@@ptn&&Or@@Table[!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

a(31)-a(59) from Lucas A. Brown, Sep 09 2022

A300912 Numbers of the form prime(x)*prime(y) where x and y are relatively prime.

Original entry on oeis.org

4, 6, 10, 14, 15, 22, 26, 33, 34, 35, 38, 46, 51, 55, 58, 62, 69, 74, 77, 82, 85, 86, 93, 94, 95, 106, 118, 119, 122, 123, 134, 141, 142, 143, 145, 146, 155, 158, 161, 166, 177, 178, 187, 194, 201, 202, 205, 206, 209, 214, 215, 217, 218, 219, 221, 226, 249

Offset: 1

Gus Wiseman, Sep 06 2018

nonn

			The sequence of all relatively prime pairs (columns) begins:
  1  1  1  1  2  1  1  2  1  3  1  1  2  3  1  1  2  1  4  1  3  1  2  1  3
  1  2  3  4  3  5  6  5  7  4  8  9  7  5 10 11  9 12  5 13  7 14 11 15  8

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A001358, A000837, A001221, A001222, A006881, A289508, A289509, A318990.

Select[Range[100],And[PrimeOmega[#]==2,GCD@@PrimePi/@If[#==1,{},FactorInteger[#]][[All,1]]==1]&]
With[{nn=40},Join[{4},Take[Prime[#[[1]]]Prime[#[[2]]]&/@Select[Subsets[ Range[ nn],{2}],CoprimeQ@@#&]//Union,Floor[Prime[nn]/2]]]] (* Harvey P. Dale, Jan 04 2021 *)

ok(n)={my(f=factor(n)); bigomega(f)==2 && gcd(apply(primepi, f[,1]))==1} \\ Andrew Howroyd, Oct 26 2018

A300486 Number of relatively prime or monic partitions of n.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 15, 18, 28, 35, 56, 64, 101, 120, 168, 210, 297, 348, 490, 583, 776, 946, 1255, 1482, 1952, 2335, 2981, 3581, 4565, 5387, 6842, 8119, 10086, 12013, 14863, 17527, 21637, 25525, 31083, 36695, 44583, 52256, 63261, 74171, 88932, 104303, 124754

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime or monic partition of n is an integer partition of n that is either of length 1 (monic) or whose parts have no common divisor other than 1 (relatively prime).

			The a(6) = 8 relatively prime or monic partitions are (6), (51), (411), (321), (3111), (2211), (21111), (111111). Missing from this list are (42), (33), (222).

Andrew Howroyd, Table of n, a(n) for n = 1..1000
A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Cf. A000837, A001383, A063834, A093637, A196545, A281113, A289501, A300383, A301462, A301467, A301480, A302094, A302698, A302915, A302916, A302917.

Table[Length[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]],{n,20}]

a(n)={(n > 1) + sumdiv(n, d, moebius(d)*numbpart(n/d))} \\ Andrew Howroyd, Aug 29 2018

a(n > 1) = 1 + A000837(n) = 1 + Sum_{d|n} mu(d) * A000041(n/d).

cp's OEIS Frontend

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

A356606 Number of strict integer partitions of n where all parts have neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A055684 Number of different n-pointed stars.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302697 Odd numbers whose prime indices are relatively prime. Heinz numbers of integer partitions with no 1's and with relatively prime parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318990 Numbers of the form prime(x) * prime(y) where x divides y.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A000741 Number of compositions of n into 3 ordered relatively prime parts.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A356607 Number of strict integer partitions of n with at least one neighborless part.

Views

Author

Keywords