A078374 -id:A078374 - cp's OEIS frontend

A303138 Regular triangle where T(n,k) is the number of strict integer partitions of n with greatest common divisor k.

1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 4, 0, 0, 0, 0, 0, 1, 4, 1, 0, 0, 0, 0, 0, 1, 6, 0, 1, 0, 0, 0, 0, 0, 1, 7, 2, 0, 0, 0, 0, 0, 0, 0, 1, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 17, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 23, 0, 2, 0, 1

Offset: 1

Gus Wiseman, Apr 19 2018

			Triangle begins:
01:   1
02:   0  1
03:   1  0  1
04:   1  0  0  1
05:   2  0  0  0  1
06:   2  1  0  0  0  1
07:   4  0  0  0  0  0  1
08:   4  1  0  0  0  0  0  1
09:   6  0  1  0  0  0  0  0  1
10:   7  2  0  0  0  0  0  0  0  1
11:  11  0  0  0  0  0  0  0  0  0  1
12:  10  2  1  1  0  0  0  0  0  0  0  1
13:  17  0  0  0  0  0  0  0  0  0  0  0  1
14:  17  4  0  0  0  0  0  0  0  0  0  0  0  1
15:  23  0  2  0  1  0  0  0  0  0  0  0  0  0  1
The strict partitions counted in row 12 are the following.
T(12,1) = 10: (11,1) (9,2,1) (8,3,1) (7,5) (7,4,1) (7,3,2) (6,5,1) (6,3,2,1) (5,4,3) (5,4,2,1)
T(12,2) = 2:  (10,2) (6,4,2)
T(12,3) = 1:  (9,3)
T(12,4) = 1:  (8,4)
T(12,12) = 1: (12)

First column is A078374. Second column at even indices is same as first column. Row sums are A000009. Row sums with first column removed are A303280.

Cf. A000009, A000837, A018783, A051424, A117408, A168532, A289508, A289509, A298748, A300486, A302698, A302796, A303139, A303140, A303280.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&GCD@@#===k&]],{n,15},{k,n}]

If k divides n, T(n,k) = A078374(n/k); otherwise T(n,k) = 0.

A328672 Number of integer partitions of n with relatively prime parts in which no two distinct parts are relatively prime.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 1, 4, 1, 1, 2, 7, 1, 6, 1, 3, 3, 10, 1, 9, 3, 5, 4, 17, 1, 23, 6, 7, 6, 20, 3, 36, 9, 15, 7, 45, 5, 56, 14, 17, 20, 65, 7, 83, 18, 40

Offset: 0

Gus Wiseman, Oct 29 2019

nonn

Positions of terms greater than 1 are {31, 37, 41, 43, 46, 47, 49, ...}.

A partition with no two distinct parts relatively prime is said to be intersecting.

			Examples:
  a(31) = 2:         a(46) = 2:
    (15,10,6)          (15,15,10,6)
    (1^31)             (1^46)
  a(37) = 3:         a(47) = 7:
    (15,12,10)         (20,15,12)
    (15,10,6,6)        (21,14,12)
    (1^37)             (20,15,6,6)
  a(41) = 4:           (21,14,6,6)
    (20,15,6)          (15,12,10,10)
    (21,14,6)          (15,10,10,6,6)
    (15,10,10,6)       (1^47)
    (1^41)           a(49) = 6:
  a(43) = 4:           (24,15,10)
    (18,15,10)         (18,15,10,6)
    (15,12,10,6)       (15,12,12,10)
    (15,10,6,6,6)      (15,12,10,6,6)
    (1^43)             (15,10,6,6,6,6)
                       (1^39)

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

The Heinz numbers of these partitions are A328679.
The strict case is A318715.
The version for non-isomorphic multiset partitions is A319759.
Relatively prime partitions are A000837.
Intersecting partitions are A328673.
Cf. A078374, A285573, A289509, A291166, A303140, A305148, A316476, A326910, A326912.

Table[Length[Select[IntegerPartitions[n],GCD@@#==1&&And[And@@(GCD[##]>1&)@@@Subsets[Union[#],{2}]]&]],{n,0,32}]

a(n > 0) = A202425(n) + 1.

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

A366850 Number of integer partitions of n whose odd parts are relatively prime.

Original entry on oeis.org

0, 1, 1, 2, 3, 5, 7, 11, 16, 22, 32, 43, 60, 80, 110, 140, 194, 244, 327, 410, 544, 670, 883, 1081, 1401, 1708, 2195, 2651, 3382, 4069, 5129, 6157, 7708, 9194, 11438, 13599, 16788, 19911, 24432, 28858, 35229, 41507, 50359, 59201, 71489, 83776, 100731, 117784

Offset: 0

Gus Wiseman, Oct 28 2023

nonn

			The a(1) = 1 through a(8) = 16 partitions:
  (1)  (11)  (21)   (31)    (41)     (51)      (61)       (53)
             (111)  (211)   (221)    (321)     (331)      (71)
                    (1111)  (311)    (411)     (421)      (431)
                            (2111)   (2211)    (511)      (521)
                            (11111)  (3111)    (2221)     (611)
                                     (21111)   (3211)     (3221)
                                     (111111)  (4111)     (3311)
                                               (22111)    (4211)
                                               (31111)    (5111)
                                               (211111)   (22211)
                                               (1111111)  (32111)
                                                          (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)

For all parts (not just odd) we have A000837, complement A018783.
The complement is counted by A366842.
These partitions have ranks A366846.
A000041 counts integer partitions, strict A000009 (also into odds).
A000740 counts relatively prime compositions.
A078374 counts relatively prime strict partitions.
A113685 counts partitions by sum of odd parts, rank statistic A366528.
A168532 counts partitions by gcd.
A239261 counts partitions with (sum of odd parts) = (sum of even parts).
Cf. A007359, A047967, A051424, A066208, A116598, A365067, A366843, A366844, A366845, A366848.

Table[Length[Select[IntegerPartitions[n],GCD@@Select[#,OddQ]==1&]],{n,0,30}]

A300277 G.f.: 1 + Sum_{n>=1} a(n)x^n/(1 - x^n) = Product_{n>=1} 1/(1 - nx^n).

Original entry on oeis.org

1, 2, 5, 11, 24, 48, 96, 184, 348, 645, 1169, 2140, 3761, 6687, 11645, 20326, 34635, 59854, 100579, 171211, 285718, 479325, 791315, 1318955, 2156805, 3553589, 5783306, 9445861, 15250215, 24759156, 39713787, 63991400, 102197851, 163548416, 259744930, 413761633, 653715967

Offset: 1

Ilya Gutkovskiy, Mar 01 2018

nonn

Moebius transform of A006906.

Vaclav Kotesovec, Table of n, a(n) for n = 1..6000
N. J. A. Sloane, Transforms

Cf. A000837, A006906, A078374, A085410, A300274, A300275, A300276, A300278.

nn = 37; f[x_] := 1 + Sum[a[n] x^n/(1 - x^n), {n, 1, nn}]; sol = SolveAlways[0 == Series[f[x] - Product[1/(1 - n x^n), {n, 1, nn}], {x, 0, nn}], x]; Table[a[n], {n, 1, nn}] /. sol // Flatten
s[n_] := SeriesCoefficient[Product[1/(1 - k x^k), {k, 1, n}], {x, 0, n}]; a[n_] := Sum[MoebiusMu[n/d] s[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 37}]

a(n) = Sum_{d|n} mu(n/d)*A006906(d).

A316500 Number of unlabeled rooted identity trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 46, 96, 205, 442, 976, 2146, 4789, 10719, 24202, 54841, 124967, 285724, 656011, 1510929, 3491151, 8088692, 18790084

Offset: 1

Gus Wiseman, Jul 05 2018

			The a(7) = 11 rooted identity trees:
  ((((((o))))))
  ((((o(o)))))
  (((o((o)))))
  ((o(((o)))))
  ((o(o(o))))
  (((o)((o))))
  (o((((o)))))
  (o((o(o))))
  (o(o((o))))
  ((o)(((o))))
  (o(o)((o)))

Cf. A000081, A004111, A007562, A078374, A289509, A316469, A316471, A316474, A316501, A316503.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],UnsameQ@@#&&Or[Length[#]==1,Intersection@@#=={}]&]];
Table[Length[strut[n]],{n,20}]

A324749 Number of strict integer partitions of n containing no part > 1 whose prime indices all belong to the partition.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 4, 3, 4, 6, 6, 8, 11, 10, 14, 14, 19, 21, 26, 28, 35, 38, 44, 50, 60, 65, 79, 88, 98, 113, 131, 144, 165, 185, 211, 234, 268, 297, 334, 374, 420, 470, 525, 584, 649, 727, 801, 902, 998, 1100, 1220, 1357, 1500, 1657, 1833, 2029, 2220, 2462

Offset: 0

Gus Wiseman, Mar 15 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(0) = 1 through a(10) = 6 strict integer partitions:
  ()  (1)  (2)  (3)  (4)    (5)  (6)    (7)    (8)    (9)    (10)
                     (3,1)       (4,2)  (4,3)  (6,2)  (5,4)  (6,4)
                                 (5,1)  (5,2)  (7,1)  (6,3)  (7,3)
                                        (6,1)         (7,2)  (8,2)
                                                             (9,1)
                                                             (6,3,1)

The subset version is A324738. The non-strict version is A324754. The Heinz number version is A324759. An infinite version is A324694.
Cf. A000720, A001462, A007097, A074971, A078374, A112798, A276625, A290822, A305713.
Cf. A324744, A324750, A324755, A324760.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,30}]

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

A338557 Products of three distinct prime numbers of even index.

Original entry on oeis.org

273, 399, 609, 741, 777, 903, 1113, 1131, 1281, 1443, 1491, 1653, 1659, 1677, 1729, 1869, 2067, 2109, 2121, 2247, 2373, 2379, 2451, 2639, 2751, 2769, 2919, 3021, 3081, 3171, 3219, 3367, 3423, 3471, 3477, 3633, 3741, 3801, 3857, 3913, 3939, 4047, 4053, 4173

Offset: 1

Gus Wiseman, Nov 08 2020

nonn

All terms are odd.
Also sphenic numbers (A007304) with all even prime indices (A031215).
Also Heinz numbers of strict 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:
     273: {2,4,6}     1869: {2,4,24}    3219: {2,10,12}
     399: {2,4,8}     2067: {2,6,16}    3367: {4,6,12}
     609: {2,4,10}    2109: {2,8,12}    3423: {2,4,38}
     741: {2,6,8}     2121: {2,4,26}    3471: {2,6,24}
     777: {2,4,12}    2247: {2,4,28}    3477: {2,8,18}
     903: {2,4,14}    2373: {2,4,30}    3633: {2,4,40}
    1113: {2,4,16}    2379: {2,6,18}    3741: {2,10,14}
    1131: {2,6,10}    2451: {2,8,14}    3801: {2,4,42}
    1281: {2,4,18}    2639: {4,6,10}    3857: {4,8,10}
    1443: {2,6,12}    2751: {2,4,32}    3913: {4,6,14}
    1491: {2,4,20}    2769: {2,6,20}    3939: {2,6,26}
    1653: {2,8,10}    2919: {2,4,34}    4047: {2,8,20}
    1659: {2,4,22}    3021: {2,8,16}    4053: {2,4,44}
    1677: {2,6,14}    3081: {2,6,22}    4173: {2,6,28}
    1729: {4,6,8}     3171: {2,4,36}    4179: {2,4,46}

For the following, NNS means "not necessarily strict".
A007304 allows all prime indices (not just even) (NNS: A014612).
A046389 allows all odd primes (NNS: A046316).
A258117 allows products of any length (NNS: A066207).
A307534 is the version for odds instead of evens (NNS: A338471).
A337453 is a different ranking of ordered triples (NNS: A014311).
A338556 is the NNS version.
A001399(n-6) counts strict 3-part partitions (NNS: A001399(n-3)).
A005117 lists squarefree numbers, with even case A039956.
A078374 counts 3-part relatively prime strict partitions (NNS: A023023).
A075819 lists even Heinz numbers of strict triples (NNS: A075818).
A220377 counts 3-part pairwise coprime strict partitions (NNS: A307719).
A258116 lists squarefree numbers with all odd prime indices (NNS: A066208).
A285508 lists Heinz numbers of non-strict triples.
Cf. A000217, A001221, A001222, A037144, A056239, A112798, A337605.

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

isok(m) = my(f=factor(m)); (bigomega(f)==3) && (omega(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, nextprime, integer_nthroot
def A338557(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) 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(nextprime(k)+1,isqrt(x//k)+1),a+2))))
    return bisection(f,n,n) # Chai Wah Wu, Oct 18 2024

A339672 Number of partitions of n into 7 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 21, 28, 38, 49, 65, 82, 105, 131, 164, 201, 248, 300, 364, 436, 522, 618, 733, 860, 1009, 1175, 1366, 1579, 1823, 2093, 2398, 2738, 3117, 3539, 4006, 4526, 5095, 5731, 6419, 7190, 8018, 8946, 9932, 11044, 12213, 13534, 14912, 16475, 18089, 19928, 21808

Offset: 28

Ilya Gutkovskiy, Feb 23 2021

nonn

Cf. A023022, A023027, A023032, A078374, A101271, A340719, A341868, A341870, A341912, A341913, A341914.

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

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

cp's OEIS Frontend

A303138 Regular triangle where T(n,k) is the number of strict integer partitions of n with greatest common divisor k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A328672 Number of integer partitions of n with relatively prime parts in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A366850 Number of integer partitions of n whose odd parts are relatively prime.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A300277 G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = Product_{n>=1} 1/(1 - n*x^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A316500 Number of unlabeled rooted identity trees with n nodes in which the branches of any node with more than one branch have empty intersection.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A324749 Number of strict integer partitions of n containing no part > 1 whose prime indices all belong to the partition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A338471 Products of three prime numbers of odd index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

A338557 Products of three distinct prime numbers of even index.

A300277 G.f.: 1 + Sum_{n>=1} a(n)x^n/(1 - x^n) = Product_{n>=1} 1/(1 - nx^n).