A055684 -id:A055684 - cp's OEIS frontend

A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).

1, 1, 1, 2, 1, 3, 2, 3, 2, 5, 2, 6, 3, 4, 4, 8, 3, 9, 4, 6, 5, 11, 4, 10, 6, 9, 6, 14, 4, 15, 8, 10, 8, 12, 6, 18, 9, 12, 8, 20, 6, 21, 10, 12, 11, 23, 8, 21, 10, 16, 12, 26, 9, 20, 12, 18, 14, 29, 8, 30, 15, 18, 16, 24, 10, 33, 16, 22, 12, 35, 12, 36, 18, 20, 18, 30, 12, 39, 16, 27, 20, 41, 12

Offset: 2

N. J. A. Sloane

The number of distinct linear fractional transformations of order n. Also the half-totient function can be used to construct a tree containing all the integers. On the zeroth rank we have just the integers 1 and 2: immediate "ancestors" of 1 and 2 are (1: 3,4,6 2: 5,8,10,12) etc. - Benoit Cloitre, Jun 03 2002
Moebius transform of floor(n/2). - Paul Barry, Mar 20 2005
Also number of different kinds of regular n-gons, one convex, the others self-intersecting. - Reinhard Zumkeller, Aug 20 2005
From Artur Jasinski, Oct 28 2008: (Start)
Degrees of minimal polynomials of cos(2*Pi/n). The first few are
   1: x - 1
   2: x + 1
   3: 2*x + 1
   4: x
   5: 4*x^2 + 2*x - 1
   6: 2*x - 1
   7: 8*x^3 + 4*x^2 - 4*x - 1
   8: 2*x^2 - 1
   9: 8*x^3 - 6*x + 1
  10: 4*x^2 - 2*x - 1
  11: 32*x^5 + 16*x^4 - 32*x^3 - 12*x^2 + 6*x + 1
These polynomials have solvable Galois groups, so their roots can be expressed by radicals. (End)
a(n) is the number of rationals p/q in the interval [0,1] such that p + q = n. - Geoffrey Critzer, Oct 10 2011
It appears that, for n > 2, a(n) = A023896(n)/n. Also, it appears that a record occurs at n > 2 in this sequence if and only if n is a prime.  For example, records occur at n=5, 7, 11, 13, 17, ..., all of which are prime. - John W. Layman, Mar 26 2012
From Wolfdieter Lang, Dec 19 2013: (Start)
a(n) is the degree of the algebraic number of s(n)^2 = (2*sin(Pi/n))^2, starting at a(1)=1. s(n) = 2*sin(Pi/n) is the length ratio side/R for a regular n-gon inscribed in a circle of radius R (in some length units). For the coefficient table of the minimal polynomials of s(n)^2 see A232633.
Because for even n, s(n)^2 lives in the algebraic number field Q(rho(n/2)), with rho(k) = 2*cos(Pi/k), the degree is a(2*l) = A055034(l). For odd n, s(n)^2 is an integer in Q(rho(n)), and the degree is a(2*l+1) = A055034(2*l+1) = phi(2*l+1)/2, l >= 1, with Euler's totient phi=A000010 and a(1)=1. See also A232631-A232633.
(End)
Also for n > 2: number of fractions A182972(k)/A182973(k) such that A182972(k) + A182973(k) = n, A182972(n) and A182973(n) provide an enumeration of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator. - Reinhard Zumkeller, Jul 30 2014
Number of distinct rectangles with relatively prime length and width such that L + W = n, W <= L. For a(17)=8; the rectangles are 1 X 16, 2 X 15, 3 X 14, 4 X 13, 5 X 12, 6 X 11, 7 X 10, 8 X 9. - Wesley Ivan Hurt, Nov 12 2017
After including a(1) = 1, the number of elements of any reduced residue system mod* n used by Brändli and Beyne is a(n). See the examples below. - Wolfdieter Lang, Apr 22 2020
a(n) is the number of ABC triples with n = c. - Felix Huber, Oct 12 2023

			a(15)=4 because there are 4 partitions of 15 into two parts that are relatively prime: 14 + 1, 13 + 2, 11 + 4, 8 + 7. - _Geoffrey Critzer_, Jan 25 2015
The smallest nonnegative reduced residue system mod*(n) for n = 1 is {0}, hence a(1) = 1; for n = 9 it is {1, 2, 4}, because 5 == 4 (mod* 9) since -5 == 4 (mod 9), 7 == 2 (mod* 9) and 8 == 1 (mod* 9). Hence a(9) = phi(9)/2 = 3. See the comment on Brändli and Beyne above. - _Wolfdieter Lang_, Apr 22 2020

G. Pólya and G. Szegő, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Sect. 6, Problems 60&61.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 2..10000
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
K. S. Brown, The Half-Totient Tree
Tianxin Cai, Zhongyan Shen, and Mengjun Hu, On the Parity of the Generalized Euler Function, Advances in Mathematics (China), 2013, 42(4): 505-510.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Sameen Ahmed Khan, Trigonometric Ratios Using Algebraic Methods, Mathematics and Statistics (2021) Vol. 9, No. 6, 899-907.
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 518.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Pinthira Tangsupphathawat, Takao Komatsu, and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
Eric Weisstein's World of Mathematics, Polygon Triangle Picking
Eric Weisstein's World of Mathematics, Trigonometry Angles
Canze Zhu and Qunying Liao, A recursion formula for the generalized Euler function phi_e(n), arXiv:2105.10870 [math.NT], 2021.

Cf. A000010, A055684, A046657, A049806, A049703, A062956.
Cf. A181875, A181876, A181877, A183918.
Cf. A023896.
Cf. A182972, A182973, A245497, A245718.

a023022 n = length [(u, v) | u <- [1 .. div n 2],
                             let v = n - u, gcd u v == 1]
-- Reinhard Zumkeller, Jul 30 2014

[1] cat [EulerPhi(n)/ 2: n in [3..100]]; // Vincenzo Librandi, Aug 19 2018

A023022 := proc(n)
    if n =2 then
        1;
    else
        numtheory[phi](n)/2 ;
    end if;
end proc:
seq(A023022(n),n=2..60) ; # R. J. Mathar, Sep 19 2017

Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by Vincenzo Librandi, Aug 19 2018 *)

a(n)=if(n<=2,1,eulerphi(n)/2);
/* for printing minimal polynomials of cos(2*Pi/n) */
default(realprecision,110);
for(n=1,33,print(n,": ",algdep(cos(2*Pi/n),a(n))));

from sympy.ntheory import totient
def a(n): return 1 if n<3 else totient(n)/2 # Indranil Ghosh, Mar 30 2017

a(n) = phi(n)/2 for n >= 3.
a(n) = (1/n)*Sum_{k=1..n-1, gcd(n, k)=1} k = A023896(n)/n for n>2. - Reinhard Zumkeller, Aug 20 2005
G.f.: x*(x - 1)/2 + (1/2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Apr 13 2017
a(n) = Sum_{d|n} moebius(n/d)*floor(d/2). - Michel Marcus, May 25 2021

This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by David W. Wilson
Entry revised by N. J. A. Sloane, Jun 10 2012
Polynomials edited with the consent of Artur Jasinski by Wolfdieter Lang, Jan 08 2011
Name clarified by Geoffrey Critzer, Jan 25 2015

A023023 Number of partitions of n into 3 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 8, 14, 12, 16, 16, 24, 18, 30, 24, 32, 30, 44, 32, 50, 42, 54, 48, 70, 48, 80, 64, 80, 72, 96, 72, 114, 90, 112, 96, 140, 96, 154, 120, 144, 132, 184, 128, 196, 150, 192, 168, 234, 162, 240, 192, 240, 210, 290, 192, 310, 240, 288, 256, 336, 240, 374

Offset: 3

David W. Wilson

nonn

			From _Gus Wiseman_, Oct 08 2020: (Start)
The a(3) = 1 through a(13) = 14 triples (A = 10, B = 11):
  111   211   221   321   322   332   432   433   443   543   544
              311   411   331   431   441   532   533   552   553
                          421   521   522   541   542   651   643
                          511   611   531   631   551   732   652
                                      621   721   632   741   661
                                      711   811   641   831   733
                                                  722   921   742
                                                  731   A11   751
                                                  821         832
                                                  911         841
                                                              922
                                                              931
                                                              A21
                                                              B11
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 3..10000
Mohamed El Bachraoui, Relatively Prime Partitions with Two and Three Parts, Fibonacci Quart. 46/47 (2008/2009), no. 4, 341-345.

Cf. A023024-A023030, A000742-A000743, A023032-A023035.
A000741 is the ordered version.
A000837 counts these partitions of any length.
A001399(n-3) does not require relative primality.
A023022 is the 2-part version.
A101271 is the strict case.
A284825 counts the case that is also pairwise non-coprime.
A289509 intersected with A014612 gives the Heinz numbers.
A307719 is the pairwise coprime instead of relatively prime version.
A337599 is the pairwise non-coprime instead of relative prime version.
A008284 counts partitions by sum and length.
A078374 counts relatively prime strict partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000010, A000217, A007434, A055684, A078374, A200976, A220377, A302698, A327516, A337563, A337600, A337605.

Table[Length[Select[IntegerPartitions[n,{3}],GCD@@#==1&]],{n,3,50}] (* Gus Wiseman, Oct 08 2020 *)

G.f. for the number of partitions of n into m unordered relatively prime parts is Sum(moebius(k)*x^(m*k)/Product(1-x^(i*k), i=1..m), k=1..infinity). - Vladeta Jovovic, Dec 21 2004
a(n) = (n^2/12)*Product_{prime p|n} (1 - 1/p^2) = A007434(n)/12 for n > 3 (proved by Mohamed El Bachraoui). [Jonathan Sondow, May 27 2009]
a(n) = Sum_{k=1..floor(n/3)} Sum_{i=k..floor((n-k)/2)} floor(1/gcd(i,k,n-i-k)). - Wesley Ivan Hurt, Jan 02 2021

A101271 Number of partitions of n into 3 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 8, 9, 12, 12, 16, 15, 21, 20, 26, 25, 33, 28, 40, 36, 45, 42, 56, 44, 65, 56, 70, 64, 84, 66, 96, 81, 100, 88, 120, 90, 133, 110, 132, 121, 161, 120, 175, 140, 176, 156, 208, 153, 220, 180, 222, 196, 261, 184, 280, 225, 270, 240, 312, 230, 341, 272

Offset: 6

Vladeta Jovovic, Dec 19 2004

The Heinz numbers of these partitions are the intersection of A289509 (relatively prime), A005117 (strict), and A014612 (triple). - Gus Wiseman, Oct 15 2020

			For n=10 we have 4 such partitions: 1+2+7, 1+3+6, 1+4+5 and 2+3+5.
From _Gus Wiseman_, Oct 13 2020: (Start)
The a(6) = 1 through a(18) = 15 triples (A..F = 10..15):
  321  421  431  432  532  542  543  643  653  654  754  764  765
            521  531  541  632  651  652  743  753  763  854  873
                 621  631  641  732  742  752  762  853  863  954
                      721  731  741  751  761  843  871  872  972
                           821  831  832  851  852  943  953  981
                                921  841  932  861  952  962  A53
                                     931  941  942  961  971  A71
                                     A21  A31  951  A51  A43  B43
                                          B21  A32  B32  A52  B52
                                               A41  B41  A61  B61
                                               B31  C31  B42  C51
                                               C21  D21  B51  D32
                                                         C32  D41
                                                         C41  E31
                                                         D31  F21
                                                         E21
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 6..10000

Cf. A023024-A023030, A000742-A000743, A023031-A023035.
A000741 is the ordered non-strict version.
A001399(n-6) does not require relative primality.
A023022 counts pairs instead of triples.
A023023 is the not necessarily strict version.
A078374 counts these partitions of any length, with Heinz numbers A302796.
A101271*6 is the ordered version.
A220377 is the pairwise coprime instead of relatively prime version.
A284825 counts the case that is pairwise non-coprime also.
A337605 is the pairwise non-coprime instead of relatively prime version.
A008289 counts strict partitions by sum and length.
A007304 gives the Heinz numbers of 3-part strict partitions.
A307719 counts 3-part pairwise coprime partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000010, A000217, A000837, A007360, A014612, A055684, A289509, A332004, A337452, A337563.

m:=3: with(numtheory): g:=sum(mobius(k)*x^(m*(m+1)/2*k)/Product(1-x^(i*k),i=1..m),k=1..20): gser:=series(g,x=0,80): seq(coeff(gser,x^n),n=6..77); # Emeric Deutsch, May 31 2005

Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&GCD@@#==1&]],{n,6,50}] (* Gus Wiseman, Oct 13 2020 *)

G.f. for the number of partitions of n into m distinct and relatively prime parts is Sum(moebius(k)*x^(m*(m+1)/2*k)/Product(1-x^(i*k), i=1..m), k=1..infinity).

More terms from Emeric Deutsch, May 31 2005

A337563 Number of pairwise coprime unordered triples of positive integers > 1 summing to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 7, 1, 7, 3, 9, 2, 15, 3, 13, 5, 17, 4, 29, 5, 20, 8, 28, 8, 42, 8, 31, 14, 42, 10, 59, 12, 45, 21, 52, 14, 77, 17, 68, 26, 69, 19, 101, 26, 84, 34, 86, 25, 138, 28, 95, 43, 111, 36, 161, 35, 118, 52, 151

Offset: 0

Gus Wiseman, Sep 21 2020

nonn

Such partitions are necessarily strict.

The Heinz numbers of these partitions are the intersection of A005408 (no 1's), A014612 (triples), and A302696 (coprime).

			The a(10) = 1 through a(24) = 15 triples (empty columns indicated by dots, A..J = 10..19):
  532  .  543  .  743  753  754  .  765  B53  875  975  985  B75  987
          732     752       853     873       974  B73  B65  D73  B76
                            952     954       A73  D53  B74       B85
                            B32     972       B54       B83       B94
                                    B43       B72       B92       BA3
                                    B52       D43       D54       C75
                                    D32       D52       D72       D65
                                                        E53       D74
                                                        H32       D83
                                                                  D92
                                                                  F72
                                                                  G53
                                                                  H43
                                                                  H52
                                                                  J32

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

A055684 is the version for pairs.
A220377 allows 1's, with non-strict version A307719.
A337485 counts these partitions of any length.
A337563*6 is the ordered version.
A001399(n - 3) = A069905(n) = A211540(n + 2) counts 3-part partitions.
A002865 counts partitions with no 1's, with strict case A025147.
A007359 counts pairwise coprime partitions with no 1's.
A078374 counts relatively prime strict partitions.
A200976 and A328673 count pairwise non-coprime partitions.
A302696 ranks pairwise coprime partitions.
A302698 counts relatively prime partitions with no 1's.
A305713 counts pairwise coprime strict partitions.
A327516 counts pairwise coprime partitions.
A337452 counts relatively prime strict partitions with no 1's.
Cf. A007304, A082024, A101268, A284825, A332004, A337451, A337461, A337462, A337561, A337599, A337601, A337605.

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

A338910 Numbers of the form prime(x) * prime(y) where x and y are both odd.

Original entry on oeis.org

4, 10, 22, 25, 34, 46, 55, 62, 82, 85, 94, 115, 118, 121, 134, 146, 155, 166, 187, 194, 205, 206, 218, 235, 253, 254, 274, 289, 295, 298, 314, 334, 335, 341, 358, 365, 382, 391, 394, 415, 422, 451, 454, 466, 482, 485, 514, 515, 517, 527, 529, 538, 545, 554

Offset: 1

Gus Wiseman, Nov 20 2020

nonn

			The sequence of terms together with their prime indices begins:
      4: {1,1}     146: {1,21}    314: {1,37}
     10: {1,3}     155: {3,11}    334: {1,39}
     22: {1,5}     166: {1,23}    335: {3,19}
     25: {3,3}     187: {5,7}     341: {5,11}
     34: {1,7}     194: {1,25}    358: {1,41}
     46: {1,9}     205: {3,13}    365: {3,21}
     55: {3,5}     206: {1,27}    382: {1,43}
     62: {1,11}    218: {1,29}    391: {7,9}
     82: {1,13}    235: {3,15}    394: {1,45}
     85: {3,7}     253: {5,9}     415: {3,23}
     94: {1,15}    254: {1,31}    422: {1,47}
    115: {3,9}     274: {1,33}    451: {5,13}
    118: {1,17}    289: {7,7}     454: {1,49}
    121: {5,5}     295: {3,17}    466: {1,51}
    134: {1,19}    298: {1,35}    482: {1,53}

A338911 is the even instead of odd version.
A339003 is the squarefree case.
A001221 counts distinct prime indices.
A001222 counts prime indices.
A001358 lists semiprimes, with odd/even terms A046315/A100484.
A006881 lists squarefree semiprimes, with odd/even terms A046388/A100484.
A289182/A115392 list the positions of odd/even terms of A001358.
A300912 lists semiprimes with relatively prime indices.
A318990 lists semiprimes with divisible indices.
A338904 groups semiprimes by weight.
A338906/A338907 are semiprimes of even/odd weight.
A338898, A338912, and A338913 give the prime indices of semiprimes, with product A087794, sum A176504, and difference A176506.
A338899, A270650, and A270652 give prime indices of squarefree semiprimes.
A338909 lists semiprimes with non-relatively prime indices.
Cf. A005117, A037143, A055684, A056239, A065516, A112798, A195017, A320655, A320732, A320892, A339004.

q:= n-> (l-> add(i[2], i=l)=2 and andmap(i->
    numtheory[pi](i[1])::odd, l))(ifactors(n)[2]):
select(q, [$1..1000])[];  # Alois P. Heinz, Nov 23 2020

Select[Range[100],PrimeOmega[#]==2&&OddQ[Times@@PrimePi/@First/@FactorInteger[#]]&]

from math import isqrt
from sympy import primepi, primerange
def A338910(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(primepi(x//p)-a>>1 for a,p in enumerate(primerange(isqrt(x)+1),-1) if a&1)
    return bisection(f,n,n) # Chai Wah Wu, Apr 03 2025

Numbers m such that A001222(m) = A195017(m) = 2. - Peter Munn, Jan 17 2021

A338911 Numbers of the form prime(x) * prime(y) where x and y are both even.

Original entry on oeis.org

9, 21, 39, 49, 57, 87, 91, 111, 129, 133, 159, 169, 183, 203, 213, 237, 247, 259, 267, 301, 303, 321, 339, 361, 371, 377, 393, 417, 427, 453, 481, 489, 497, 519, 543, 551, 553, 559, 579, 597, 623, 669, 687, 689, 703, 707, 717, 749, 753, 789, 791, 793, 813, 817

Offset: 1

Gus Wiseman, Nov 20 2020

nonn

			The sequence of terms together with their prime indices begins:
      9: {2,2}     237: {2,22}    481: {6,12}
     21: {2,4}     247: {6,8}     489: {2,38}
     39: {2,6}     259: {4,12}    497: {4,20}
     49: {4,4}     267: {2,24}    519: {2,40}
     57: {2,8}     301: {4,14}    543: {2,42}
     87: {2,10}    303: {2,26}    551: {8,10}
     91: {4,6}     321: {2,28}    553: {4,22}
    111: {2,12}    339: {2,30}    559: {6,14}
    129: {2,14}    361: {8,8}     579: {2,44}
    133: {4,8}     371: {4,16}    597: {2,46}
    159: {2,16}    377: {6,10}    623: {4,24}
    169: {6,6}     393: {2,32}    669: {2,48}
    183: {2,18}    417: {2,34}    687: {2,50}
    203: {4,10}    427: {4,18}    689: {6,16}
    213: {2,20}    453: {2,36}    703: {8,12}

A338910 is the odd instead of even version.
A339004 is the squarefree case.
A001221 counts distinct prime indices.
A001222 counts prime indices.
A001358 lists semiprimes, with odd/even terms A046315/A100484.
A006881 lists squarefree semiprimes, with odd/even terms A046388/A100484.
A338899, A270650, A270652 list prime indices of squarefree semiprimes.
A289182/A115392 list the positions of odd/even terms of A001358.
A300912 lists semiprimes with relatively prime indices.
A318990 lists semiprimes with divisible indices.
A338904 groups semiprimes by weight.
A338906/A338907 list semiprimes of even/odd weight.
A338909 lists semiprimes with non-relatively prime indices.
A338912 and A338913 list prime indices of semiprimes, with product A087794, sum A176504, and difference A176506.
Cf. A005117, A037143, A055684, A056239, A065516, A112798, A128301, A195017, A320655, A320732, A320892, A338898, A339002, A339003.

q:= n-> (l-> add(i[2], i=l)=2 and andmap(i->
    numtheory[pi](i[1])::even, l))(ifactors(n)[2]):
select(q, [$1..1000])[];  # Alois P. Heinz, Nov 23 2020

Select[Range[100],PrimeOmega[#]==2&&OddQ[Times@@(1+PrimePi/@First/@FactorInteger[#])]&]

from math import isqrt
from sympy import primerange, primepi
def A338911(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(primepi(x//p)-a>>1 for a,p in enumerate(primerange(isqrt(x)+1),-1) if a&1^1)
    return bisection(f,n,n) # Chai Wah Wu, Apr 03 2025

Numbers m such that A001222(m) = 2 and A195017(m) = -2. - Peter Munn, Jan 17 2021

A337450 Number of relatively prime compositions of n with no 1's.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 7, 5, 17, 17, 54, 51, 143, 168, 358, 482, 986, 1313, 2583, 3663, 6698, 9921, 17710, 26489, 46352, 70928, 121137, 188220, 317810, 497322, 832039, 1313501, 2177282, 3459041, 5702808, 9094377, 14930351, 23895672, 39084070, 62721578

Offset: 0

Gus Wiseman, Aug 31 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(5) = 2 through a(10) = 17 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)    (3,5)    (2,7)      (3,7)
  (3,2)     (3,4)    (5,3)    (4,5)      (7,3)
            (4,3)    (2,3,3)  (5,4)      (2,3,5)
            (5,2)    (3,2,3)  (7,2)      (2,5,3)
            (2,2,3)  (3,3,2)  (2,2,5)    (3,2,5)
            (2,3,2)           (2,3,4)    (3,3,4)
            (3,2,2)           (2,4,3)    (3,4,3)
                              (2,5,2)    (3,5,2)
                              (3,2,4)    (4,3,3)
                              (3,4,2)    (5,2,3)
                              (4,2,3)    (5,3,2)
                              (4,3,2)    (2,2,3,3)
                              (5,2,2)    (2,3,2,3)
                              (2,2,2,3)  (2,3,3,2)
                              (2,2,3,2)  (3,2,2,3)
                              (2,3,2,2)  (3,2,3,2)
                              (3,2,2,2)  (3,3,2,2)

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 171 terms from Fausto A. C. Cariboni)

A000740 is the version allowing 1's.
2*A055684(n) is the case of length 2.
A302697 ranks the unordered case.
A302698 is the unordered version.
A337451 is the strict version.
A337452 is the unordered strict version.
A000837 counts relatively prime partitions.
A002865 counts partitions with no 1's.
A101268 counts singleton or pairwise coprime compositions.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A337462 counts pairwise coprime compositions.
Cf. A000010, A007359, A023023, A101268, A178472, A289509, A302568, A337485.

b:= proc(n, g) option remember; `if`(n=0,
     `if`(g=1, 1, 0), add(b(n-j, igcd(g, j)), j=2..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..42);

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

A128114 Number of uniform polyhedra with n vertices.

Original entry on oeis.org

0, 0, 0, 1, 0, 3, 0, 2, 0, 5, 0, 10, 0, 7, 0, 5, 0, 7, 0, 9, 0, 12, 0, 15, 0, 14, 0, 7, 0, 18, 0, 9, 0, 19, 0, 7, 0, 21, 0, 10, 0, 14, 0, 11, 0, 26, 0, 12, 0, 23, 0, 14, 0, 21, 0, 14, 0, 33, 0, 42, 0, 35, 0, 19, 0, 23, 0, 18, 0, 28, 0, 14, 0, 42, 0, 21, 0, 28, 0, 18, 0, 47, 0, 14, 0, 49, 0, 24, 0

Offset: 1

Paulo de A. Sachs (sachs6(AT)yahoo.de), Feb 15 2007, corrected Feb 15 2007

nonn

			Every other term is zero because there are no uniform polyhedra with an odd number of vertices. a(6)=3 because there are the octahedron, the tetrahemihexahedron and the triangular prism.

Hart, George W., Uniform Polyhedra.
Maeder, Roman E., Uniform Polyhedra.
Eric Weisstein's World of Mathematics, Uniform Polyhedron.

Cf. A128914.

After 120th term, a(n) equals 0 for n odd and 2 * A055684(n/2) + A128115(n/2) + 2 for n even.

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

cp's OEIS Frontend

A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A023023 Number of partitions of n into 3 unordered relatively prime parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A101271 Number of partitions of n into 3 distinct and relatively prime parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A337563 Number of pairwise coprime unordered triples of positive integers > 1 summing to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A338910 Numbers of the form prime(x) * prime(y) where x and y are both odd.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A338911 Numbers of the form prime(x) * prime(y) where x and y are both even.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A337450 Number of relatively prime compositions of n with no 1's.

Views

Author

Keywords

Comments

Examples