A101271 -id:A101271 - cp's OEIS frontend

A007304 Sphenic numbers: products of 3 distinct primes.

30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, 230, 231, 238, 246, 255, 258, 266, 273, 282, 285, 286, 290, 310, 318, 322, 345, 354, 357, 366, 370, 374, 385, 399, 402, 406, 410, 418, 426, 429, 430, 434, 435, 438

Offset: 1

Simon Plouffe

Note the distinctions between this and "n has exactly three prime factors" (A014612) or "n has exactly three distinct prime factors." (A033992). The word "sphenic" also means "shaped like a wedge" [American Heritage Dictionary] as in dentation with "sphenic molars." - Jonathan Vos Post, Sep 11 2005
Also the volume of a sphenic brick. A sphenic brick is a rectangular parallelepiped whose sides are components of a sphenic number, namely whose sides are three distinct primes. Example: The distinct prime triple (3,5,7) produces a 3x5x7 unit brick which has volume 105 cubic units. 3-D analog of 2-D A037074 Product of twin primes, per Cino Hilliard's comment. Compare with 3-D A107768 Golden 3-almost primes = Volumes of bricks (rectangular parallelepipeds) each of whose faces has golden semiprime area. - Jonathan Vos Post, Jan 08 2007
Sum(n>=1,  1/a(n)^s) = (1/6)*(P(s)^3 - P(3*s) - 3*(P(s)*P(2*s)-P(3*s))), where P is prime zeta function. - Enrique Pérez Herrero, Jun 28 2012
Also numbers n with A001222(n)=3 and A001221(n)=3. - Enrique Pérez Herrero, Jun 28 2012
n = 265550 is the smallest n with a(n) (=1279789) < A006881(n) (=1279793). - Peter Dolland, Apr 11 2020

			From _Gus Wiseman_, Nov 05 2020: (Start)
Also Heinz numbers of strict integer partitions into three parts, where the Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). These partitions are counted by A001399(n-6) = A069905(n-3), with ordered version A001399(n-6)*6. The sequence of terms together with their prime indices begins:
     30: {1,2,3}     182: {1,4,6}     286: {1,5,6}
     42: {1,2,4}     186: {1,2,11}    290: {1,3,10}
     66: {1,2,5}     190: {1,3,8}     310: {1,3,11}
     70: {1,3,4}     195: {2,3,6}     318: {1,2,16}
     78: {1,2,6}     222: {1,2,12}    322: {1,4,9}
    102: {1,2,7}     230: {1,3,9}     345: {2,3,9}
    105: {2,3,4}     231: {2,4,5}     354: {1,2,17}
    110: {1,3,5}     238: {1,4,7}     357: {2,4,7}
    114: {1,2,8}     246: {1,2,13}    366: {1,2,18}
    130: {1,3,6}     255: {2,3,7}     370: {1,3,12}
    138: {1,2,9}     258: {1,2,14}    374: {1,5,7}
    154: {1,4,5}     266: {1,4,8}     385: {3,4,5}
    165: {2,3,5}     273: {2,4,6}     399: {2,4,8}
    170: {1,3,7}     282: {1,2,15}    402: {1,2,19}
    174: {1,2,10}    285: {2,3,8}     406: {1,4,10}
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
"Sphenic", The American Heritage Dictionary of the English Language, Fourth Edition, Houghton Mifflin Company, 2000.

Products of exactly k distinct primes, for k = 1 to 6: A000040, A006881. A007304, A046386, A046387, A067885.
Cf. A002033, A010051, A020639, A037074, A046393, A061299, A067467, A071140, A096917, A096918, A096919, A100765, A103653, A107464, A107768, A179643, A179695.
Cf. A162143 (a(n)^2).
For the following, NNS means "not necessarily strict".
A014612 is the NNS version.
A046389 is the restriction to odds (NNS: A046316).
A075819 is the restriction to evens (NNS: A075818).
A239656 gives first differences.
A285508 lists terms of A014612 that are not squarefree.
A307534 is the case where all prime indices are odd (NNS: A338471).
A337453 is a different ranking of ordered triples (NNS: A014311).
A338557 is the case where all prime indices are even (NNS: A338556).
A001399(n-6) counts strict 3-part partitions (NNS: A001399(n-3)).
A005117 lists squarefree numbers.
A008289 counts strict partitions by sum and length.
A220377 counts 3-part pairwise coprime strict partitions (NNS: A307719).
Cf. A000212, A000217, A001840, A101271, A284825, A321773, A337599, A337605.

a007304 n = a007304_list !! (n-1)
a007304_list = filter f [1..] where
f u = p < q && q < w && a010051 w == 1 where
p = a020639 u; v = div u p; q = a020639 v; w = div v q
-- Reinhard Zumkeller, Mar 23 2014

with(numtheory): a:=proc(n) if bigomega(n)=3 and nops(factorset(n))=3 then n else fi end: seq(a(n),n=1..450); # Emeric Deutsch
A007304 := proc(n)
    option remember;
    local a;
    if n =1 then
        30;
    else
        for a from procname(n-1)+1 do
            if bigomega(a)=3 and nops(factorset(a))=3 then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Dec 06 2016
is_a := proc(n) local P; P := NumberTheory:-PrimeFactors(n); nops(P) = 3 and n = mul(P) end:
A007304List := upto -> select(is_a, [seq(1..upto)]):  # Peter Luschny, Apr 14 2025

Union[Flatten[Table[Prime[n]*Prime[m]*Prime[k], {k, 20}, {n, k+1, 20}, {m, n+1, 20}]]]
Take[ Sort@ Flatten@ Table[ Prime@i Prime@j Prime@k, {i, 3, 21}, {j, 2, i - 1}, {k, j - 1}], 53] (* Robert G. Wilson v *)
With[{upto=500},Sort[Select[Times@@@Subsets[Prime[Range[Ceiling[upto/6]]],{3}],#<=upto&]]] (* Harvey P. Dale, Jan 08 2015 *)
Select[Range[100],SquareFreeQ[#]&&PrimeOmega[#]==3&] (* Gus Wiseman, Nov 05 2020 *)

for(n=1,1e4,if(bigomega(n)==3 && omega(n)==3,print1(n", "))) \\ Charles R Greathouse IV, Jun 10 2011

list(lim)=my(v=List(),t);forprime(p=2,(lim)^(1/3),forprime(q=p+1,sqrt(lim\p),t=p*q;forprime(r=q+1,lim\t,listput(v,t*r))));vecsort(Vec(v)) \\ Charles R Greathouse IV, Jul 20 2011

list(lim)=my(v=List(), t); forprime(p=2, sqrtnint(lim\=1,3), forprime(q=p+1, sqrtint(lim\p), t=p*q; forprime(r=q+1, lim\t, listput(v, t*r)))); Set(v) \\ Charles R Greathouse IV, Jan 21 2025

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A007304(n):
    def f(x): return int(n+x-sum(primepi(x//(k*m))-b for a,k in enumerate(primerange(integer_nthroot(x,3)[0]+1),1) for b,m in enumerate(primerange(k+1,isqrt(x//k)+1),a+1)))
    kmin, kmax = 0,1
    while f(kmax) > kmax:
        kmax <<= 1
    while kmax-kmin > 1:
        kmid = kmax+kmin>>1
        if f(kmid) <= kmid:
            kmax = kmid
        else:
            kmin = kmid
    return kmax # Chai Wah Wu, Aug 29 2024

def is_a(n):
    P = prime_divisors(n)
    return len(P) == 3 and prod(P) == n
print([n for n in range(1, 439) if is_a(n)]) # Peter Luschny, Apr 14 2025

A008683(a(n)) = -1.
A000005(a(n)) = 8. - R. J. Mathar, Aug 14 2009
A002033(a(n)-1) = 13. - Juri-Stepan Gerasimov, Oct 07 2009, R. J. Mathar, Oct 14 2009
A178254(a(n)) = 36. - Reinhard Zumkeller, May 24 2010
A050326(a(n)) = 5, subsequence of A225228. - Reinhard Zumkeller, May 03 2013
a(n) ~ 2n log n/(log log n)^2. - Charles R Greathouse IV, Sep 14 2015

More terms from Robert G. Wilson v, Jan 04 2006

Comment concerning number of divisors corrected by R. J. Mathar, Aug 14 2009

A220377 Number of partitions of n into three distinct and mutually relatively prime parts.

Original entry on oeis.org

1, 0, 2, 1, 3, 1, 6, 1, 7, 3, 7, 3, 14, 3, 15, 6, 14, 6, 25, 6, 22, 10, 25, 9, 42, 8, 34, 15, 37, 15, 53, 13, 48, 22, 53, 17, 78, 17, 65, 30, 63, 24, 99, 24, 88, 35, 84, 30, 126, 34, 103, 45, 103, 38, 166, 35, 124, 57, 128, 51, 184, 44, 150, 67, 172, 52, 218

Offset: 6

Carl Najafi, Dec 13 2012

nonn

The Heinz numbers of these partitions are the intersection of A005117 (strict), A014612 (triples), and A302696 (coprime). - Gus Wiseman, Oct 14 2020

			For n=10 we have three such partitions: 1+2+7, 1+4+5 and 2+3+5.
From _Gus Wiseman_, Oct 14 2020: (Start)
The a(6) = 1 through a(20) = 15 triples (empty column indicated by dot, A..H = 10..17):
321  .  431  531  532  731  543  751  743  753  754  971  765  B53  875
        521       541       651       752  951  853  B51  873  B71  974
                  721       732       761  B31  871  D31  954  D51  A73
                            741       851       952       972       A91
                            831       941       B32       981       B54
                            921       A31       B41       A71       B72
                                      B21       D21       B43       B81
                                                          B52       C71
                                                          B61       D43
                                                          C51       D52
                                                          D32       D61
                                                          D41       E51
                                                          E31       F41
                                                          F21       G31
                                                                    H21
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 6..10000 (terms 6..1000 from Seiichi Manyama)

Cf. A015617, A300815.
A023022 is the 2-part version.
A101271 is the relative prime instead of pairwise coprime version.
A220377*6 is the ordered version.
A305713 counts these partitions of any length, with Heinz numbers A302797.
A307719 is the non-strict version.
A337461 is the non-strict ordered version.
A337563 is the case with no 1's.
A337605 is the pairwise non-coprime instead of pairwise coprime version.
A001399(n-6) counts strict 3-part partitions, with Heinz numbers A007304.
A008284 counts partitions by sum and length, with strict case A008289.
A318717 counts pairwise non-coprime strict partitions.
A326675 ranks pairwise coprime sets.
A327516 counts pairwise coprime partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000217, A007360, A023023, A051424, A078374, A087087, A302696, A333227, A337485, A337561.

Table[Length@Select[ IntegerPartitions[ n, {3}], #[[1]] != #[[2]] != #[[3]] && GCD[#[[1]], #[[2]]] == 1 && GCD[#[[1]], #[[3]]] == 1 && GCD[#[[2]], #[[3]]] == 1 &], {n, 6, 100}]
Table[Count[IntegerPartitions[n,{3}],?(CoprimeQ@@#&&Length[ Union[#]] == 3&)],{n,6,100}] (* _Harvey P. Dale, May 22 2020 *)

a(n)=my(P=partitions(n));sum(i=1,#P,#P[i]==3&&P[i][1]Charles R Greathouse IV, Dec 14 2012

a(n > 2) = A307719(n) - 1. - Gus Wiseman, Oct 15 2020

A211540 Number of ordered triples (w,x,y) with all terms in {1..n} and 2w = 3x + 4y.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44, 48, 52, 56, 61, 65, 70, 75, 80, 85, 91, 96, 102, 108, 114, 120, 127, 133, 140, 147, 154, 161, 169, 176, 184, 192, 200, 208, 217, 225, 234, 243, 252, 261, 271, 280, 290

Offset: 0

Clark Kimberling, Apr 15 2012

For a guide to related sequences, see A211422.
Also the number of partitions of n+1 into three parts, where each part > 1. - Peter Woodward, May 25 2015
a(n) is also equal to the number of partitions of n+4 into three distinct parts, where each part > 1. - Giovanni Resta, May 26 2015
Number of different distributions of n+1 identical balls in 3 boxes as x,y,z where 0 < x < y < z. - Ece Uslu and Esin Becenen, Dec 31 2015
After the first three terms, partial sums of A008615. - Robert Israel, Dec 31 2015
For n >= 2, also the number of partitions of n - 2 into 3 parts. The Heinz numbers of these partitions are given by A014612. - Gus Wiseman, Oct 11 2020

			a(5) = a(6) = 1 with only one ordered triple (5,2,1). - _Michael Somos_, Feb 02 2015
a(11) = 5 Number of different distributions of 11 identical balls in 3 boxes as x,y and z where 0 < x < y < z. - _Ece Uslu_, Esin Becenen, Dec 31 2015
a(1) = a(2) = a(3) = a(4) = a(5) = 0, since with fewer than 6 identical balls there is no such distribution with 3 boxes that holds for 0 < x < y < z. - _Ece Uslu_, Esin Becenen, Dec 31 2015
G.f.: x^5 + x^6 + 2*x^7 + 3*x^8 + 4*x^9 + 5*x^10 + 7*x^11 + 8*x^12 + ...
From _Gus Wiseman_, Oct 11 2020: (Start)
The a(5) = 1 through a(15) = 14 partitions of n + 1 into three parts > 1 [Woodward] are the following (A = 10, B = 11, C = 12). The ordered version is A000217(n - 4) and the Heinz numbers are A046316.
  222  322  332  333  433  443  444  544  554  555  655
            422  432  442  533  543  553  644  654  664
                 522  532  542  552  643  653  663  754
                      622  632  633  652  662  744  763
                           722  642  733  743  753  772
                                732  742  752  762  844
                                822  832  833  843  853
                                     922  842  852  862
                                          932  933  943
                                          A22  942  952
                                               A32  A33
                                               B22  A42
                                                    B32
                                                    C22
The a(5) = 1 through a(15) = 14 partitions of n + 4 into three distinct parts > 1 [Resta] are the following (A = 10, B = 11, C = 12, D = 13, E = 14). The ordered version is A211540*6 and the Heinz numbers are A046389.
  432  532  542  543  643  653  654  754  764  765  865
            632  642  652  743  753  763  854  864  874
                 732  742  752  762  853  863  873  964
                      832  842  843  862  872  954  973
                           932  852  943  953  963  982
                                942  952  962  972  A54
                                A32  A42  A43  A53  A63
                                     B32  A52  A62  A72
                                          B42  B43  B53
                                          C32  B52  B62
                                               C42  C43
                                               D32  C52
                                                    D42
                                                    E32
The a(5) = 1 through a(15) = 14 partitions of n + 1 into three distinct parts [Uslu and Becenen] are the following (A = 10, B = 11, C = 12, D = 13). The ordered version is A211540(n)*6 and the Heinz numbers are A007304.
  321  421  431  432  532  542  543  643  653  654  754
            521  531  541  632  642  652  743  753  763
                 621  631  641  651  742  752  762  853
                      721  731  732  751  761  843  862
                           821  741  832  842  852  871
                                831  841  851  861  943
                                921  931  932  942  952
                                     A21  941  951  961
                                          A31  A32  A42
                                          B21  A41  A51
                                               B31  B32
                                               C21  B41
                                                    C31
                                                    D21
(End)

Robert Israel, Table of n, a(n) for n = 0..10000
Clark Kimberling, A Combinatorial Classification of Triangle Centers on the Line at Infinity, J. Int. Seq., Vol. 22 (2019), Article 19.5.4.
Ece Uslu and Esin Becenen, Identical Object Distributions.
Index entries for linear recurrences with constant coefficients, signature (1,1,0,-1,-1,1).

Cf. A001399, A069905, A211422.
All of the following pertain to 3-part strict partitions.
- A000009 counts these partitions of any length, with non-strict version A000041.
- A007304 gives the Heinz numbers, with non-strict version A014612.
- A101271 counts the relatively prime case, with non-strict version A023023.
- A220377 counts the pairwise coprime case, with non-strict version A307719.
- A337605 counts the pairwise non-coprime case, with non-strict version A337599.
Cf. A000217, A001840, A156040, A284825, A337453, A337483, A337484, A337563.

I:=[0,0,0,0,0,1]; [n le 6 select I[n] else Self(n-1)+Self(n-2)-Self(n-4)-Self(n-5)+Self(n-6): n in [1..70]]; // Vincenzo Librandi, Dec 31 2015

f:= gfun:-rectoproc({a(n) = a(n-1)+a(n-2)-a(n-4)-a(n-5)+a(n-6),seq(a(i)=0,i=0..4),a(5)=1},a(n),remember):
seq(f(i),i=0..100); # Robert Israel, Dec 31 2015

t[n_] := t[n] = Flatten[Table[-2 w + 3 x + 4 y, {w, n}, {x, n}, {y, n}]]
c[n_] := Count[t[n], 0]
t = Table[c[n], {n, 0, 80}]  (* A211540 *)
FindLinearRecurrence[t]
LinearRecurrence[{1, 1, 0, -1, -1, 1}, {0, 0, 0, 0, 0, 1}, 70] (* Vincenzo Librandi, Dec 31 2015 *)
Table[Length[Select[IntegerPartitions[n+1,{3}],UnsameQ@@#&]],{n,0,30}] (* Gus Wiseman, Oct 05 2020 *)

{a(n) = round( (n-2)^2 / 12 )}; / * Michael Somos, Feb 02 2015 */

concat(vector(5), Vec(x^5/(1-x-x^2+x^4+x^5-x^6) + O(x^100))) \\ Altug Alkan, Jan 10 2016

a(n) = a(n-1) + a(n-2) - a(n-4) - a(n-5) + a(n-6).
a(n) = A069905(n-2) = A001399(n-5) for n >= 5. - Alois P. Heinz, Nov 03 2012
a(n) = 3*k^2-6*k+3 (for n = 6*k-3), 3*k^2-5*k+2 (for n = 6*k-2), 3*k^2-4*k+1 (for n = 6*k-1), 3*k^2-3*k+1 (for n = 6*k), 3*k^2-2*k (for n = 6*k+1), 3*k^2-k (for n = 6*k+2). - Ece Uslu, Esin Becenen, Dec 31 2015
a(n) = A004526(n-2) + a(n-2) for n > 2. - Ece Uslu, Esin Becenen, Dec 31 2015
G.f.: x^5/(1 - x - x^2 + x^4 + x^5 - x^6). - Robert Israel, Dec 31 2015
a(n) = Sum_{k=1..floor(n/3)} floor((n-k)/2)-k. - Wesley Ivan Hurt, Apr 27 2019
From Gus Wiseman, Oct 11 2020: (Start)
a(n+2) = A069905(n) = A001399(n-3) counts 3-part partitions.
a(n-1) = A069905(n-3) = A001399(n-6) counts 3-part strict partitions.
a(n-1) = A069905(n-3) = A001399(n-6) counts 3-part partitions with no 1's.
a(n-4) = A069905(n-6) = A001399(n-9) counts 3-part strict partitions with no 1's.
A000217(n-2) counts 3-part compositions.
a(n-1)*6 = A069905(n-3)*6 = A001399(n-6)*6 counts 3-part strict compositions.
A000217(n-5) counts 3-part compositions with no 1's.
a(n-4)*6 = A069905(n-6)*6 = A001399(n-9)*6 counts 3-part strict compositions with no 1's.
(End)

A284825 Number of partitions of n into 3 parts without common divisors such that every pair of them has common divisors.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 3, 0, 5, 0, 0, 0, 1, 0, 5, 0, 1, 0, 6, 0, 6, 0, 0, 0, 4, 0, 6, 0, 0, 0, 9, 0, 2, 1, 2, 0, 9, 0, 8, 1, 1, 0, 5, 0, 14, 0, 1, 0, 15, 0, 14, 0, 0, 1, 14, 0, 14, 0, 2, 0, 15, 0, 6, 1, 2, 1, 11, 0, 18, 1, 1, 0, 10, 0, 23

Offset: 31

Alois P. Heinz, Apr 03 2017

The Heinz numbers of these partitions are the intersection of A014612 (triples), A289509 (relatively prime), and A337694 (pairwise non-coprime). - Gus Wiseman, Oct 16 2020

			a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(41) = 2: [6,14,21], [6,15,20].
From _Gus Wiseman_, Oct 14 2020: (Start)
Selected terms and the corresponding triples:
  a(31)=1: a(41)=2: a(59)=3:  a(77)=4:  a(61)=5:  a(71)=6:
-------------------------------------------------------------
  15,10,6  20,15,6  24,20,15  39,26,12  33,22,6   39,26,6
           21,14,6  24,21,14  42,20,15  40,15,6   45,20,6
                    35,14,10  45,20,12  45,10,6   50,15,6
                              50,15,12  28,21,12  35,21,15
                                        36,15,10  36,20,15
                                                  36,21,14
(End)

Alois P. Heinz, Table of n, a(n) for n = 31..10000

Cf. A082024, A230034, A230035.
A023023 does not require pairwise non-coprimality, with strict case A101271.
A202425 and A328672 count these partitions of any length, ranked by A328868.
A284825*6 is the ordered version.
A307719 is the pairwise coprime instead of non-coprime version.
A337599 does not require relatively primality, with strict case A337605.
A200976 and A328673 count pairwise non-coprime partitions.
A289509 gives Heinz numbers of relatively prime partitions.
A327516 counts pairwise coprime partitions, ranked by A333227.
A337694 gives Heinz numbers of pairwise non-coprime partitions.
Cf. A000217, A000741, A001399, A007304, A014612, A220377, A318716, A328679, A337604, A337666.

a:= proc(n) option remember; add(add(`if`(igcd(i, j)>1
      and igcd(i, j, n-i-j)=1 and igcd(i, n-i-j)>1 and
      igcd(j, n-i-j)>1, 1, 0), j=i..(n-i)/2), i=2..n/3)
    end:
seq(a(n), n=31..137);

a[n_] := a[n] = Sum[Sum[If[GCD[i, j] > 1 && GCD[i, j, n - i - j] == 1 && GCD[i, n - i - j] > 1 && GCD[j, n - i - j] > 1, 1, 0], {j, i, (n - i)/2} ], {i, 2, n/3}];
Table[a[n], {n, 31, 137}] (* Jean-François Alcover, Jun 13 2018, from Maple *)
stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Table[Length[Select[IntegerPartitions[n,{3}],GCD@@#==1&&stabQ[#,CoprimeQ]&]],{n,31,100}] (* Gus Wiseman, Oct 14 2020 *)

a(n) > 0 iff n in { A230035 }.

a(n) = 0 iff n in { A230034 }.

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

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

A332004 Number of compositions (ordered partitions) of n into distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 0, 2, 2, 4, 8, 12, 16, 24, 52, 64, 88, 132, 180, 344, 416, 616, 816, 1176, 1496, 2736, 3232, 4756, 6176, 8756, 11172, 15576, 24120, 30460, 41456, 55740, 74440, 97976, 130192, 168408, 256464, 315972, 429888, 558192, 749920, 958264, 1274928, 1621272, 2120288, 3020256

Offset: 0

Ilya Gutkovskiy, Feb 04 2020

nonn

Moebius transform of A032020.

Ranking these compositions using standard compositions (A066099) gives the intersection of A233564 (strict) with A291166 (relatively prime). - Gus Wiseman, Oct 18 2020

			a(6) = 8 because we have [5, 1], [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 5], [1, 3, 2] and [1, 2, 3].
From _Gus Wiseman_, Oct 18 2020: (Start)
The a(1) = 1 through a(8) = 16 compositions (empty column indicated by dot):
  (1)  .  (1,2)  (1,3)  (1,4)  (1,5)    (1,6)    (1,7)
          (2,1)  (3,1)  (2,3)  (5,1)    (2,5)    (3,5)
                        (3,2)  (1,2,3)  (3,4)    (5,3)
                        (4,1)  (1,3,2)  (4,3)    (7,1)
                               (2,1,3)  (5,2)    (1,2,5)
                               (2,3,1)  (6,1)    (1,3,4)
                               (3,1,2)  (1,2,4)  (1,4,3)
                               (3,2,1)  (1,4,2)  (1,5,2)
                                        (2,1,4)  (2,1,5)
                                        (2,4,1)  (2,5,1)
                                        (4,1,2)  (3,1,4)
                                        (4,2,1)  (3,4,1)
                                                 (4,1,3)
                                                 (4,3,1)
                                                 (5,1,2)
                                                 (5,2,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Index entries for sequences related to compositions

Cf. A007360, A032020, A108700, A302698.
A000740 is the non-strict version.
A078374 is the unordered version (non-strict: A000837).
A101271*6 counts these compositions of length 3 (non-strict: A000741).
A337561/A337562 is the pairwise coprime instead of relatively prime version (non-strict: A337462/A101268).
A289509 gives the Heinz numbers of relatively prime partitions.
A333227/A335235 ranks pairwise coprime compositions.
Cf. A001523, A178472, A216652, A289508, A291166, A333228.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@#&&GCD@@#<=1&]],{n,0,15}] (* Gus Wiseman, Oct 18 2020 *)

A338556 Products of three prime numbers of even index.

Original entry on oeis.org

27, 63, 117, 147, 171, 261, 273, 333, 343, 387, 399, 477, 507, 549, 609, 637, 639, 711, 741, 777, 801, 903, 909, 931, 963, 1017, 1083, 1113, 1131, 1179, 1183, 1251, 1281, 1359, 1421, 1443, 1467, 1491, 1557, 1629, 1653, 1659, 1677, 1729, 1737, 1791, 1813, 1869

Offset: 1

Gus Wiseman, Nov 08 2020

nonn

All terms are odd.

Also Heinz numbers of integer partitions with 3 parts, all of which are even. These partitions are counted by A001399.

			The sequence of terms together with their prime indices begins:
      27: {2,2,2}      637: {4,4,6}     1183: {4,6,6}
      63: {2,2,4}      639: {2,2,20}    1251: {2,2,34}
     117: {2,2,6}      711: {2,2,22}    1281: {2,4,18}
     147: {2,4,4}      741: {2,6,8}     1359: {2,2,36}
     171: {2,2,8}      777: {2,4,12}    1421: {4,4,10}
     261: {2,2,10}     801: {2,2,24}    1443: {2,6,12}
     273: {2,4,6}      903: {2,4,14}    1467: {2,2,38}
     333: {2,2,12}     909: {2,2,26}    1491: {2,4,20}
     343: {4,4,4}      931: {4,4,8}     1557: {2,2,40}
     387: {2,2,14}     963: {2,2,28}    1629: {2,2,42}
     399: {2,4,8}     1017: {2,2,30}    1653: {2,8,10}
     477: {2,2,16}    1083: {2,8,8}     1659: {2,4,22}
     507: {2,6,6}     1113: {2,4,16}    1677: {2,6,14}
     549: {2,2,18}    1131: {2,6,10}    1729: {4,6,8}
     609: {2,4,10}    1179: {2,2,32}    1737: {2,2,44}

A014612 allows all prime indices (not just even) (strict: A007304).
A066207 allows products of any length (strict: A258117).
A338471 is the version for odds instead of evens (strict: A307534).
A338557 is the strict case.
A014311 is a ranking of ordered triples (strict: A337453).
A001399(n-3) counts 3-part partitions (strict: A001399(n-6)).
A005117 lists squarefree numbers, with even case A039956.
A008284 counts partitions by sum and length (strict: A008289).
A023023 counts 3-part relatively prime partitions (strict: A101271).
A046316 lists products of exactly three odd primes (strict: A046389).
A066208 lists numbers with all odd prime indices (strict: A258116).
A075818 lists even Heinz numbers of 3-part partitions (strict: A075819).
A307719 counts 3-part pairwise coprime partitions (strict: A220377).
A285508 lists Heinz numbers of non-strict triples.
Cf. A000217, A001221, A001222, A037144, A056239, A112798, A337599, A337600.
Subsequence of A332820.

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

isok(m) = my(f=factor(m)); (bigomega(f)==3) && (#select(x->(x%2), apply(primepi, f[,1]~)) == 0); \\ Michel Marcus, Nov 10 2020

from itertools import filterfalse
from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A338556(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: 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 int(n+x-sum((primepi(x//(k*m))>>1)-(b>>1)+1 for a,k in filterfalse(lambda x:x[0]&1,enumerate(primerange(3,integer_nthroot(x,3)[0]+1),2)) for b,m in filterfalse(lambda x:x[0]&1,enumerate(primerange(k,isqrt(x//k)+1),a))))
    return bisection(f,n,n) # Chai Wah Wu, Oct 18 2024

A341914 Number of partitions of n into 10 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 55, 75, 97, 128, 164, 212, 267, 340, 423, 530, 653, 807, 984, 1204, 1455, 1761, 2112, 2534, 3015, 3590, 4242, 5013, 5888, 6912, 8070, 9418, 10936, 12690, 14663, 16928, 19466, 22367, 25608, 29292, 33401, 38047, 43214, 49037, 55494, 62740, 70760, 79725, 89623

Offset: 55

Ilya Gutkovskiy, Feb 23 2021

nonn

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

Cf. A023022, A023030, A023035, A078374, A101271, A339672, A340719, A341868, A341870, A341912, A341913.

nmax = 108; CoefficientList[Series[Sum[MoebiusMu[k] x^(55 k)/Product[1 - x^(j k), {j, 1, 10}], {k, 1, nmax}], {x, 0, nmax}], x] // Drop[#, 55] &

G.f.: Sum_{k>=1} mu(k)* x^(55*k) / Product_{j=1..10} (1 - x^(j*k)).

a(n) <= A008639(n-55), equality for n<110. - R. J. Mathar, Feb 28 2021

A338471 Products of three prime numbers of odd index.

Original entry on oeis.org

8, 20, 44, 50, 68, 92, 110, 124, 125, 164, 170, 188, 230, 236, 242, 268, 275, 292, 310, 332, 374, 388, 410, 412, 425, 436, 470, 506, 508, 548, 575, 578, 590, 596, 605, 628, 668, 670, 682, 716, 730, 764, 775, 782, 788, 830, 844, 902, 908, 932, 935, 964, 970

Offset: 1

Gus Wiseman, Nov 08 2020

nonn

Also Heinz numbers of integer partitions with 3 parts, all of which are odd. These partitions are counted by A001399.

			The sequence of terms together with their prime indices begins:
       8: {1,1,1}      268: {1,1,19}     575: {3,3,9}
      20: {1,1,3}      275: {3,3,5}      578: {1,7,7}
      44: {1,1,5}      292: {1,1,21}     590: {1,3,17}
      50: {1,3,3}      310: {1,3,11}     596: {1,1,35}
      68: {1,1,7}      332: {1,1,23}     605: {3,5,5}
      92: {1,1,9}      374: {1,5,7}      628: {1,1,37}
     110: {1,3,5}      388: {1,1,25}     668: {1,1,39}
     124: {1,1,11}     410: {1,3,13}     670: {1,3,19}
     125: {3,3,3}      412: {1,1,27}     682: {1,5,11}
     164: {1,1,13}     425: {3,3,7}      716: {1,1,41}
     170: {1,3,7}      436: {1,1,29}     730: {1,3,21}
     188: {1,1,15}     470: {1,3,15}     764: {1,1,43}
     230: {1,3,9}      506: {1,5,9}      775: {3,3,11}
     236: {1,1,17}     508: {1,1,31}     782: {1,7,9}
     242: {1,5,5}      548: {1,1,33}     788: {1,1,45}

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

A066208 allows products of any length (strict: A258116).
A307534 is the squarefree case.
A338469 is the restriction to odds.
A338556 is the version for evens (strict: A338557).
A000009 counts partitions into odd parts (strict: A000700).
A001399(n-3) counts 3-part partitions (strict: A001399(n-6)).
A008284 counts partitions by sum and length.
A014311 is a ranking of ordered triples (strict: A337453).
A014612 lists Heinz numbers of all triples (strict: A007304).
A023023 counts 3-part relatively prime partitions (strict: A101271).
A023023 counts 3-part relatively prime partitions (strict: A078374).
A046316 lists products of exactly three odd primes (strict: A046389).
A066207 lists numbers with all even prime indices (strict: A258117).
A075818 lists even Heinz numbers of 3-part partitions (strict: A075819).
A285508 lists Heinz numbers of non-strict triples.
A307719 counts 3-part pairwise coprime partitions (strict: A220377).
Cf. A000217, A001221, A001222, A005117, A037144, A056239, A112798.
Subsequence of A332820.

N:= 1000: # for terms <= N
R:= NULL:
for i from 1 by 2 do
  p:= ithprime(i);
  if p^3 >= N then break fi;
  for j from i by 2 do
    q:= ithprime(j);
    if p*q^2 >= N then break fi;
    for k from j by 2 do
      x:= p*q*ithprime(k);
      if x > N then break fi;
      R:= R,x;
od od od:
sort([R]); # Robert Israel, Jun 11 2025

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

isok(m) = my(f=factor(m)); (bigomega(f)==3) && (#select(x->!(x%2), apply(primepi, f[,1]~)) == 0); \\ Michel Marcus, Nov 10 2020

from sympy import primerange
from itertools import combinations_with_replacement as mc
def aupto(limit):
    pois = [p for i, p in enumerate(primerange(2, limit//4+1)) if i%2 == 0]
    return sorted(set(a*b*c for a, b, c in mc(pois, 3) if a*b*c <= limit))
print(aupto(971)) # Michael S. Branicky, Aug 20 2021

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A338471(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: 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 int(n+x-sum((primepi(x//(k*m))+1>>1)-(b+1>>1)+1 for a,k in filter(lambda x:x[0]&1,enumerate(primerange(integer_nthroot(x,3)[0]+1),1)) for b,m in filter(lambda x:x[0]&1,enumerate(primerange(k,isqrt(x//k)+1),a))))
    return bisection(f,n,n) # Chai Wah Wu, Oct 18 2024

cp's OEIS Frontend

A007304 Sphenic numbers: products of 3 distinct primes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A220377 Number of partitions of n into three distinct and mutually relatively prime parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A211540 Number of ordered triples (w,x,y) with all terms in {1..n} and 2w = 3x + 4y.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A284825 Number of partitions of n into 3 parts without common divisors such that every pair of them has common divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple