A338332 -id:A338332 - cp's OEIS frontend

A302698 Number of integer partitions of n into relatively prime parts that are all greater than 1.

0, 0, 0, 0, 1, 0, 3, 2, 5, 4, 13, 7, 23, 18, 32, 33, 65, 50, 104, 92, 148, 153, 252, 226, 376, 376, 544, 570, 846, 821, 1237, 1276, 1736, 1869, 2552, 2643, 3659, 3887, 5067, 5509, 7244, 7672, 10086, 10909, 13756, 15168, 19195, 20735, 26237, 28708, 35418, 39207

Offset: 1

Gus Wiseman, Apr 11 2018

nonn

Two or more numbers are relatively prime if they have no common divisor other than 1. A single number is not considered relatively prime unless it is equal to 1 (which is impossible in this case).

The Heinz numbers of these partitions are given by A302697.

			The a(5) = 1 through a(12) = 7 partitions (empty column indicated by dot):
  (32)  .  (43)   (53)   (54)    (73)    (65)     (75)
           (52)   (332)  (72)    (433)   (74)     (543)
           (322)         (432)   (532)   (83)     (552)
                         (522)   (3322)  (92)     (732)
                         (3222)          (443)    (4332)
                                         (533)    (5322)
                                         (542)    (33222)
                                         (632)
                                         (722)
                                         (3332)
                                         (4322)
                                         (5222)
                                         (32222)

Alois P. Heinz, Table of n, a(n) for n = 1..1000

A000837 is the version allowing 1's.
A002865 does not require relative primality.
A302697 gives the Heinz numbers of these partitions.
A337450 is the ordered version.
A337451 is the ordered strict version.
A337452 is the strict version.
A337485 is the pairwise coprime instead of relatively prime version.
A000740 counts relatively prime compositions.
A078374 counts relatively prime strict partitions.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A332004 counts strict relatively prime compositions.
A337561 counts pairwise coprime strict compositions.
A338332 is the case of length 3, with strict case A338333.
Cf. A007359, A018783, A051424, A101268, A289508, A289509, A302568, A337563, A337984, A338468.

b:= proc(n, i, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
      `if`(i<2, 0, b(n, i-1, g)+b(n-i, min(n-i, i), igcd(g, i))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=1..60);  # Alois P. Heinz, Apr 12 2018

Table[Length[Select[IntegerPartitions[n],FreeQ[#,1]&&GCD@@#===1&]],{n,30}]
(* Second program: *)
b[n_, i_, g_] := b[n, i, g] = If[n == 0, If[g == 1, 1, 0], If[i < 2, 0, b[n, i - 1, g] + b[n - i, Min[n - i, i], GCD[g, i]]]];
a[n_] := b[n, n, 0];
Array[a, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

a(n) = A002865(n) - A018783(n).

Extended by Gus Wiseman, Oct 29 2020

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

A338333 Number of relatively prime 3-part strict integer partitions of n with no 1's.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 4, 4, 7, 6, 10, 8, 14, 12, 18, 16, 24, 18, 30, 25, 34, 30, 44, 31, 52, 42, 56, 49, 69, 50, 80, 64, 83, 70, 102, 71, 114, 90, 112, 100, 140, 98, 153, 117, 153, 132, 184, 128, 195, 154, 196, 169, 234, 156, 252, 196, 241

Offset: 0

Gus Wiseman, Oct 30 2020

nonn

The Heinz numbers of these partitions are the intersection of A005117 (strict), A005408 (no 1's), A014612 (length 3), and A289509 (relatively prime).

			The a(9) = 1 through a(19) = 14 triples (A = 10, B = 11, C = 12, D = 13, E = 14):
  432   532   542   543   643   653   654   754   764   765   865
              632   732   652   743   753   763   854   873   874
                          742   752   762   853   863   954   964
                          832   932   843   943   872   972   973
                                      852   952   953   A53   982
                                      942   B32   962   B43   A54
                                      A32         A43   B52   A63
                                                  A52   D32   A72
                                                  B42         B53
                                                  C32         B62
                                                              C43
                                                              C52
                                                              D42
                                                              E32

A001399(n-9) does not require relative primality.
A005117 /\ A005408 /\ A014612 /\ A289509 gives the Heinz numbers.
A055684 is the 2-part version.
A284825 counts the case that is also pairwise non-coprime.
A337452 counts these partitions of any length.
A337563 is the pairwise coprime instead of relatively prime version.
A337605 is the pairwise non-coprime instead of relative prime version.
A338332 is the not necessarily strict version.
A338333*6 is the ordered version.
A000837 counts relatively prime partitions.
A008284 counts partitions by sum and length.
A078374 counts relatively prime strict partitions.
A101271 counts 3-part relatively prime strict partitions.
A220377 counts 3-part pairwise coprime strict partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000010, A000217, A000741, A023022, A082024, A302698, A307719, A337450, A337599, A338468.

Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&!MemberQ[#,1]&&GCD@@#==1&]],{n,0,30}]

cp's OEIS Frontend

A302698 Number of integer partitions of n into relatively prime parts that are all greater than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A055684 Number of different n-pointed stars.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A338333 Number of relatively prime 3-part strict integer partitions of n with no 1's.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica