A082023 -id:A082023 - cp's OEIS frontend

A055684 Number of different n-pointed stars.

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

A082024 Number of partitions of n into 3 parts which have common divisors.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 4, 0, 4, 3, 5, 0, 9, 0, 9, 5, 10, 0, 16, 2, 14, 7, 17, 0, 27, 0, 21, 11, 24, 6, 36, 0, 30, 15, 37, 0, 51, 0, 41, 25, 44, 0, 64, 4, 58, 25, 57, 0, 81, 12, 69, 31, 70, 0, 108, 0, 80, 43, 85, 16, 123, 0, 97, 45, 120, 0, 144, 0, 114, 69, 121, 14, 171, 0

Offset: 0

Amarnath Murthy, Apr 07 2003

a(p) = 0 if p is a prime. Can anyone suggest a formula?

See example for a method to find a(n). - David A. Corneth, Aug 24 2020

			a(14) = 4 and the partitions are (10,2,2), (8,4,2),(6,6,2) and (6,4,4).
a(13) = 0 as for all r + s + t = 13,r > 0, s > 0,t> 0 gcd(r,s,t) = 1.
From _David A. Corneth_, Aug 24 2020: (Start)
a(100) = 233. The squarefree part of 100 is 10. The divisors of 10 are 1, 2, 5 and 10.
These are the possible squarefree divisors of parts. As parts must not be coprime, we exclude 1, leaving 2, 5 and 10. We then compute 100/k for each of these numbers.
This gives 50, 20 and 10 respectively. Now a(100) is found by adding -(round(50^2/12)*(-1)^omega(2) + round(20^2/12)*(-1)^omega(5) + round(10^2/12)*(-1)^omega(10)) = -(-208 - 33 + 8) = 233 where omega(m) is the number of distinct divisors of m (Cf. A001221) and round(m^2/12) is the number of partitions of m into 3 parts (Cf. A069905) (End)

David A. Corneth, Table of n, a(n) for n = 0..9999 (first 5001 terms from Alois P. Heinz)

Cf. A001221, A069905, A082023, A284825.

a[n_] := Length[Select[Flatten[Table[{a, b, n-a-b}, {a, 1, Floor[n/3]}, {b, a, Floor[(n-a)/2]}], 1], GCD@@#1>1&]]

a(n) = if(n==0, return(0)); cn = factorback(factor(n)[, 1]); d = divisors(cn); -sum(i = 2, #d, round((n/d[i])^2/12) * (-1)^omega(d[i])) \\ David A. Corneth, Aug 24 2020

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 20 2003 and Dean Hickerson, Apr 22 2003

A338909 Numbers of the form prime(x) * prime(y) where x and y have a common divisor > 1.

Original entry on oeis.org

9, 21, 25, 39, 49, 57, 65, 87, 91, 111, 115, 121, 129, 133, 159, 169, 183, 185, 203, 213, 235, 237, 247, 259, 267, 289, 299, 301, 303, 305, 319, 321, 339, 361, 365, 371, 377, 393, 417, 427, 445, 453, 481, 489, 497, 515, 517, 519, 529, 543, 551, 553, 559, 565

Offset: 1

Gus Wiseman, Nov 20 2020

nonn

			The sequence of terms together with their prime indices begins:
      9: {2,2}     169: {6,6}     319: {5,10}
     21: {2,4}     183: {2,18}    321: {2,28}
     25: {3,3}     185: {3,12}    339: {2,30}
     39: {2,6}     203: {4,10}    361: {8,8}
     49: {4,4}     213: {2,20}    365: {3,21}
     57: {2,8}     235: {3,15}    371: {4,16}
     65: {3,6}     237: {2,22}    377: {6,10}
     87: {2,10}    247: {6,8}     393: {2,32}
     91: {4,6}     259: {4,12}    417: {2,34}
    111: {2,12}    267: {2,24}    427: {4,18}
    115: {3,9}     289: {7,7}     445: {3,24}
    121: {5,5}     299: {6,9}     453: {2,36}
    129: {2,14}    301: {4,14}    481: {6,12}
    133: {4,8}     303: {2,26}    489: {2,38}
    159: {2,16}    305: {3,18}    497: {4,20}

A082023 counts partitions with these as Heinz numbers, complement A023022.
A300912 is the complement in A001358.
A339002 is the squarefree case.
A001221 counts distinct prime indices.
A001222 counts prime indices.
A001358 lists semiprimes, with odds A046315 and evens A100484.
A004526 counts 2-part partitions, with strict case A140106 (shifted left).
A006881 lists squarefree semiprimes, with odds A046388 and evens A100484.
A176504/A176506/A087794 give sum/difference/product of semiprime indices.
A318990 lists semiprimes with divisible indices.
A320655 counts factorizations into semiprimes.
A338898, A338912, and A338913 give semiprime indices.
A338899, A270650, and A270652 give squarefree semiprime indices.
A338910 lists semiprimes with odd indices.
A338911 lists semiprimes with even indices.
Cf. A005117, A037143, A055684, A056239, A065516, A112798, A115392, A128301, A289182, A338900, A338904.

Select[Range[100],PrimeOmega[#]==2&&GCD@@PrimePi/@First/@FactorInteger[#]>1&]

Equals A001358 \ A300912.

Equals A339002 \/ (A001248 \ {4}).

A338554 Number of non-constant integer partitions of n whose parts have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 2, 1, 5, 0, 9, 0, 13, 6, 18, 0, 33, 0, 40, 14, 54, 0, 87, 5, 99, 27, 133, 0, 211, 0, 226, 55, 295, 18, 443, 0, 488, 100, 637, 0, 912, 0, 1000, 198, 1253, 0, 1775, 13, 1988, 296, 2434, 0, 3358, 59, 3728, 489, 4563, 0, 6241, 0, 6840, 814

Offset: 0

Gus Wiseman, Nov 07 2020

nonn

			The a(6) = 2 through a(15) = 6 partitions (empty columns indicated by dots, A = 10, B = 11, C = 12):
  (42)  .  (62)   (63)  (64)    .  (84)     .  (86)      (96)
           (422)        (82)       (93)        (A4)      (A5)
                        (442)      (A2)        (C2)      (C3)
                        (622)      (633)       (644)     (663)
                        (4222)     (642)       (662)     (933)
                                   (822)       (842)     (6333)
                                   (4422)      (A22)
                                   (6222)      (4442)
                                   (42222)     (6422)
                                               (8222)
                                               (44222)
                                               (62222)
                                               (422222)

A046022 lists positions of zeros.
A082023(n) - A059841(n) is the 2-part version, n > 2.
A303280(n) - 1 is the strict case (n > 1).
A338552 lists the Heinz numbers of these partitions.
A338553 counts the complement, with Heinz numbers A338555.
A000005 counts constant partitions, with Heinz numbers A000961.
A000837 counts relatively prime partitions, with Heinz numbers A289509.
A018783 counts non-relatively prime partitions (ordered: A178472), with Heinz numbers A318978.
A282750 counts relatively prime partitions by sum and length.
Cf. A000010, A008284, A051424, A082024, A289508, A302698, A304712.

Table[Length[Select[IntegerPartitions[n],!SameQ@@#&&GCD@@#>1&]],{n,0,30}]

For n > 0, a(n) = A018783(n) - A000005(n) + 1.

A378514 Number of partitions of 2^n-1 into two summands >= 0 having a common divisor > 1.

Original entry on oeis.org

0, 1, 1, 4, 1, 14, 1, 64, 40, 212, 56, 1184, 1, 2900, 2884, 16384, 1, 61088, 1, 284288, 159520, 776800, 89264, 5070848, 577216, 11195732, 10375168, 67834880, 1522240, 269570912, 1, 1073741824, 813199072, 2863486292, 917553184, 21299044352, 308159200, 45813683540

Offset: 1

Dmytro Inosov, Nov 29 2024

nonn

a(n) counts binary numbers (A007088) of length n that are not coprime with their bitwise inverse as integers in base 2.
Equivalently, m from A007088 is counted toward a(A055642(m)) iff GCD(m, A002275(A055642(m)) - m) > 1, assuming base 2 in the calculation of GCD. Therefore a(n) is the base-2 analog of A378511.
For any n > 1, a(n) > 0 because the trivial partition A002275(n) = A002275(n) + 0 always counts toward a(n): GCD(A002275(n), 0) = A002275(n) > 1.
a(n) = 1 iff n is a Mersenne exponent (A000043). Indeed, if a partition 2^n-1 = k + m exists with GCD(k, m) = q > 1, then 2^n-1 itself is divisible by q. Whenever 2^n-1 is a Mersenne prime (A000668), this is only possible for q = 2^n-1, therefore the only such partition is the trivial one, {2^n-1, 0}. The inverse is also true. If n is not a Mersenne exponent, 2^n-1 has a nontrivial divisor q, and the partition 2^n-1 = q + (2^n-1-q) counts toward a(n) because GCD(q, 2^n-1-q) = q > 1. Therefore, a(n) > 1.

			a(2) = 1 because there are only 2 possible partitions of 2^2-1 = 3 into a sum of two nonnegative integers, namely: 3 = 3 + 0 and 3 = 2 + 1. The partition {3, 0} counts toward a(2) since GCD(3,0) = 3 > 1. The partition {2, 1} does not count since GCD(2,1) = 1.
a(4) = 4 because among the 8 possible partitions of 2^4-1 = 15 into a sum of two nonnegative integers, the summands are non-coprime in exactly 4 cases:
----------------------------------------------
partition   binary vectors       GCD
(base 10)      (base 2)
----------------------------------------------
15 = 8 + 7   {1000, 0111}   GCD(8, 7) = 1;
15 = 9 + 6   {1001, 0110}   GCD(9, 6) = 3;
15 = 10 + 5  {1010, 0110}   GCD(10, 5) = 5;
15 = 11 + 4  {1011, 0100}   GCD(11, 4) = 1;
15 = 12 + 3  {1100, 0011}   GCD(12, 3) = 3;
15 = 13 + 2  {1101, 0010}   GCD(13, 2) = 1;
15 = 14 + 1  {1110, 0001}   GCD(14, 1) = 1;
15 = 15 + 0  {1111, 0000}   GCD(15, 0) = 15.
----------------------------------------------
a(7) = 1 because 7 is a term in A000043.

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 250 terms from Dmytro Inosov)

Cf. A000010, A000043, A000079, A000225, A000668, A056742, A082023, A378511.

a:= n-> (m-> ceil((m-numtheory[phi](m))/2))(2^n-1):
seq(a(n), n=1..38);  # Alois P. Heinz, Nov 29 2024

CountNonCoprimes2[i_] := Table[If[!CoprimeQ @@ #, #, ##&[]] &[{n, 2^i-1-n}], {n, 2^(i-1), 2^i-1}] // Length; Table[CountNonCoprimes2[i], {i, 25}]
(* Version that uses the built-in EulerPhi[] function *)
Table[Ceiling[(# - EulerPhi[#])/2] &[2^m-1], {m, 100}]

def a(n): return 2^(n-1) - euler_phi(2^n-1) / 2 if n > 1 else 0
print([a(n) for n in range(1, 39)])  # Peter Luschny, Nov 29 2024

a(n) <= A000325(n-1) = 2^(n-1) - n + 1;
a(A000043(n)) = 1;
From Alois P. Heinz, Nov 29 2024: (Start)
a(n) = A082023(2^n-1) + signum(n-1).
a(n) = ceiling((2^n-1 - phi(2^n-1))/2). (End)
From Peter Luschny, Nov 30 2024: (Start)
a(n) = A000079(n-1) - A056742(n) for n > 1.
a(n) = 2^(n - 1) - phi(2^n - 1)/2 for n > 1. (End)

a(32)-a(38) from Alois P. Heinz, Nov 29 2024

cp's OEIS Frontend

A055684 Number of different n-pointed stars.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A082024 Number of partitions of n into 3 parts which have common divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A338909 Numbers of the form prime(x) * prime(y) where x and y have a common divisor > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A338554 Number of non-constant integer partitions of n whose parts have a common divisor > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A378514 Number of partitions of 2^n-1 into two summands >= 0 having a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions