A008289 -id:A008289 - cp's OEIS frontend

A097910 Number of parts in all compositions of n into distinct parts.

1, 1, 5, 5, 9, 27, 31, 49, 71, 185, 207, 339, 457, 685, 1421, 1745, 2577, 3615, 5143, 6877, 13439, 15965, 23823, 31983, 45553, 59425, 83549, 139013, 173769, 244803, 330391, 452257, 597935, 810929, 1052559, 1692723, 2074321, 2890333, 3783821, 5178041, 6658377

Offset: 1

Vladeta Jovovic, Sep 04 2004

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

Cf. A001792, A008289, A015723, A032020, A072574, A336875.

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(n>i*(i+1)/2, [][], zip((x, y)->x+y, [b(n, i-1)],
      `if`(i>n, [], [0, b(n-i, i-1)]), 0)[]))
    end:
a:= n-> (l-> add(i*l[i+1]*i!, i=1..nops(l)-1))([b(n$2)]):
seq(a(n), n=1..50);  # Alois P. Heinz, Nov 20 2012
# second Maple program:
b:= proc(n, i, p) option remember; `if`(i*(i+1)/2 b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 10 2020

Drop[ CoefficientList[ Series[ Sum[ k*k!*x^((k^2 + k)/2)/Product[1 - x^j, {j, 1, k}], {k, 1, 45}], {x, 0, 40}], x], 1] (* Robert G. Wilson v, Sep 08 2004 *)

G.f.: Sum(k >= 0; k*k! x^((k^2+k)/2) / Prod(1<=j<=k; 1-x^j)).

a(n) = Sum_{k=1..floor((sqrt(8*n+1)-1)/2)} k! * k * A008289(n,k). - Alois P. Heinz, Aug 10 2020

More terms from Robert G. Wilson v and John W. Layman, Sep 08 2004

A367394 Number of integer partitions of n whose length is a semi-sum of the parts.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 3, 3, 6, 7, 14, 15, 25, 30, 46, 54, 80, 97, 139, 169, 229, 282, 382, 461, 607, 746, 962, 1173, 1499, 1817, 2302, 2787, 3467, 4201, 5216, 6260, 7702, 9261, 11294, 13524, 16418, 19572, 23658, 28141, 33756, 40081, 47949, 56662, 67493, 79639

Offset: 0

Gus Wiseman, Nov 19 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			For the partition y = (3,3,2,1) we have 4 = 3 + 1, so y is counted under a(9).
The a(2) = 1 through a(10) = 14 partitions:
  (11)  .  (211)  (221)  (321)   (421)   (521)    (621)    (721)
                         (2211)  (2221)  (2222)   (3222)   (3322)
                         (3111)  (3211)  (3221)   (3321)   (3331)
                                         (3311)   (4221)   (4222)
                                         (32111)  (4311)   (4321)
                                         (41111)  (32211)  (5221)
                                                  (42111)  (5311)
                                                           (32221)
                                                           (33211)
                                                           (42211)
                                                           (43111)
                                                           (331111)
                                                           (421111)
                                                           (511111)

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394*  A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A000041 counts partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A236912 counts partitions containing no semi-sum, ranks A364461.
A237113 counts partitions containing a semi-sum, ranks A364462.
A237668 counts sum-full partitions, sum-free A237667.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A008284 counts partitions by length, strict A008289.
A365543 counts partitions with a subset-sum k, strict A365661.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A000700, A088809, A093971, A126796, A238628, A304792, A363225, A364534, A365541, A365924, A367402.

Table[Length[Select[IntegerPartitions[n], MemberQ[Total/@Subsets[#,{2}], Length[#]]&]], {n,0,10}]

A367395 Number of strict integer partitions of n whose length is the sum of two distinct parts.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 7, 8, 11, 13, 17, 19, 25, 28, 35, 41, 49, 57, 68, 78, 92, 107, 124, 143, 166, 192, 220, 254, 291, 335, 382, 439, 499, 572, 649, 741, 840, 956, 1080, 1226, 1383, 1566, 1762, 1988, 2235, 2515, 2822, 3166, 3547

Offset: 0

Gus Wiseman, Nov 19 2023

nonn

			The strict partition (5,3,2,1) has 4 = 3 + 1 so is counted under a(11).
The a(6) = 1 through a(17) = 7 strict partitions (A..E = 10..14):
  321  421  521  621  721   821   921   A21   B21   C21    D21    E21
                      4321  5321  6321  5431  6431  6531   7531   7631
                                        7321  8321  7431   8431   8531
                                                    9321   A321   9431
                                                    54321  64321  B321
                                                                  65321
                                                                  74321

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395*  A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A000041 counts partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A088809/A093971 count twofold sum-full subsets.
A236912 counts partitions containing no semi-sum, ranks A364461.
A237113 counts partitions containing a semi-sum, ranks A364462.
A237668 counts sum-full partitions, sum-free A237667.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A008284 counts partitions by length, strict A008289.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A000700, A238628, A363225, A364272, A364534, A365661, A365925, A367410, A367411.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#,{2}], Length[#]]&]], {n,0,30}]

A367398 Number of integer partitions of n whose length is not a semi-sum of the parts.

Original entry on oeis.org

1, 1, 1, 3, 4, 6, 8, 12, 16, 23, 28, 41, 52, 71, 89, 122, 151, 200, 246, 321, 398, 510, 620, 794, 968, 1212, 1474, 1837, 2219, 2748, 3302, 4055, 4882, 5942, 7094, 8623, 10275, 12376, 14721, 17661, 20920, 25011, 29516, 35120, 41419, 49053, 57609, 68092, 79780

Offset: 0

Gus Wiseman, Nov 19 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			For the partition y = (4,3,1) we have semi-sums {4,5,7}, which do not include 3 (the length of y), so y is counted under a(8).
The a(1) = 1 through a(8) = 16 partitions:
  (1)  (2)  (3)    (4)     (5)      (6)       (7)        (8)
            (21)   (22)    (32)     (33)      (43)       (44)
            (111)  (31)    (41)     (42)      (52)       (53)
                   (1111)  (311)    (51)      (61)       (62)
                           (2111)   (222)     (322)      (71)
                           (11111)  (411)     (331)      (332)
                                    (21111)   (511)      (422)
                                    (111111)  (4111)     (431)
                                              (22111)    (611)
                                              (31111)    (4211)
                                              (211111)   (5111)
                                              (1111111)  (22211)
                                                         (221111)
                                                         (311111)
                                                         (2111111)
                                                         (11111111)

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398*
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A000041 counts partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A236912 counts partitions containing no semi-sum, ranks A364461.
A237113 counts partitions containing a semi-sum, ranks A364462.
A237667 counts sum-free partitions, sum-full A237668.
A366738 counts semi-sums of partitions, strict A366741.
A367402 counts partitions with covering semi-sums, complement A367403.
Triangles:
A008284 counts partitions by length, strict A008289.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A000700, A126796, A304792, A363225, A364272, A365543.

Table[Length[Select[IntegerPartitions[n],FreeQ[Total/@Subsets[#,{2}],Length[#]]&]],{n,0,10}]

A367399 Number of strict integer partitions of n whose length is not the sum of any two distinct parts.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 7, 8, 10, 13, 15, 19, 22, 27, 31, 38, 43, 51, 59, 70, 79, 94, 107, 124, 143, 165, 188, 218, 248, 283, 324, 369, 419, 476, 540, 610, 691, 778, 878, 987, 1111, 1244, 1399, 1563, 1750, 1954, 2184, 2432, 2714, 3016, 3358, 3730, 4143

Offset: 0

Gus Wiseman, Nov 19 2023

nonn

			The strict partition y = (6,4,2,1) has semi-sums {3,5,6,7,8,10}, which do not include 4, so y is counted under a(13).
The a(6) = 3 through a(13) = 15 strict partitions:
  (6)    (7)    (8)      (9)      (10)     (11)     (12)       (13)
  (4,2)  (4,3)  (5,3)    (5,4)    (6,4)    (6,5)    (7,5)      (7,6)
  (5,1)  (5,2)  (6,2)    (6,3)    (7,3)    (7,4)    (8,4)      (8,5)
         (6,1)  (7,1)    (7,2)    (8,2)    (8,3)    (9,3)      (9,4)
                (4,3,1)  (8,1)    (9,1)    (9,2)    (10,2)     (10,3)
                         (4,3,2)  (5,3,2)  (10,1)   (11,1)     (11,2)
                         (5,3,1)  (5,4,1)  (5,4,2)  (5,4,3)    (12,1)
                                  (6,3,1)  (6,3,2)  (6,4,2)    (6,4,3)
                                           (6,4,1)  (6,5,1)    (6,5,2)
                                           (7,3,1)  (7,3,2)    (7,4,2)
                                                    (7,4,1)    (7,5,1)
                                                    (8,3,1)    (8,3,2)
                                                    (5,4,2,1)  (8,4,1)
                                                               (9,3,1)
                                                               (6,4,2,1)

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399*
subsets:     A367216   A367217   A367222   A367223   A367396   A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A000041 counts partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A365924 counts incomplete partitions, strict A365831.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A237667 counts sum-free partitions, sum-full A237668.
A366738 counts semi-sums of partitions, strict A366741.
A367403 counts partitions without covering semi-sums, strict A367411.
Triangles:
A008284 counts partitions by length, strict A008289.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A000700, A126796, A188431, A238628, A237113, A363225, A364272, A365658, A365918, A365925, A367410.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&FreeQ[Total/@Subsets[#,{2}], Length[#]]&]], {n,0,15}]

A373118 Number T(n,k) of compositions of n such that the set of parts is [k]; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 3, 0, 1, 7, 0, 1, 11, 6, 0, 1, 20, 12, 0, 1, 32, 32, 0, 1, 54, 72, 0, 1, 87, 152, 24, 0, 1, 143, 311, 60, 0, 1, 231, 625, 180, 0, 1, 376, 1225, 450, 0, 1, 608, 2378, 1116, 0, 1, 986, 4566, 2544, 120, 0, 1, 1595, 8700, 5752, 360

Offset: 0

Alois P. Heinz, May 25 2024

			T(6,2) = 11: 1122, 1212, 1221, 2112, 2121, 2211, 11112, 11121, 11211, 12111, 21111.
T(7,3) = 12: 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1;
  0, 1,   2;
  0, 1,   3;
  0, 1,   7;
  0, 1,  11,    6;
  0, 1,  20,   12;
  0, 1,  32,   32;
  0, 1,  54,   72;
  0, 1,  87,  152,   24;
  0, 1, 143,  311,   60;
  0, 1, 231,  625,  180;
  0, 1, 376, 1225,  450;
  0, 1, 608, 2378, 1116;
  0, 1, 986, 4566, 2544, 120;
  ...

Alois P. Heinz, Rows n = 0..750, flattened

Columns k=0-3 give: A000007, A057427, A245738, A372702.
Row sums give A107429.
Cf. A000124, A000142, A000217, A000290, A001710, A003056, A008289, A332721, A371417, A373305, A373306.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
     `if`(i<1 or n b(n, k, 0):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..18);

T(A000217(n),n) = n! = A000142(n).
T(A000124(n),n) = A001710(n+1) for n>=1.
T(A000290(n),n) = T(n^2,n) = A332721(n).
G.f. for column k: C({1..k},x) where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/ (1 - Sum_{i in {s}} (x^i)) with C({},x) = 1. - John Tyler Rascoe, May 25 2024

A383092 Number of integer partitions of n having at most one permutation with all equal run-lengths.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 10, 13, 16, 22, 28, 34, 46, 58, 69, 90, 114, 141, 178, 216, 271, 338, 418, 506, 630, 769, 941, 1140, 1399, 1675, 2051, 2454, 2975, 3561, 4289, 5094, 6137, 7274, 8692, 10269, 12249, 14414, 17128, 20110, 23767, 27872, 32849, 38346, 45094, 52552, 61533

Offset: 0

Gus Wiseman, Apr 19 2025

nonn

			The partition (222211) has 1 permutation with all equal run-lengths: (221122), so is counted under a(10).
The partition (33211111) has no permutation with all equal run-lengths, so is counted under a(13).
The a(1) = 1 through a(7) = 10 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (221)    (33)      (322)
                    (211)   (311)    (222)     (331)
                    (1111)  (2111)   (411)     (511)
                            (11111)  (3111)    (2221)
                                     (21111)   (4111)
                                     (111111)  (22111)
                                               (31111)
                                               (211111)
                                               (1111111)

For no choices we have A382915, ranks A382879.
For at least one choice we have A383013, for run-sums A383098, ranks A383110.
The complement is A383090, ranks A383089.
Partitions of this type are ranked by A383091 = positions of terms <= 1 in A382857.
For a unique choice we have A383094, ranks A383112.
For run-sums instead of lengths we have A383095 + A383096, ranks A383099 \/ A383100.
The complement for run-sums is A383097, ranks A383015, positions of terms > 1 in A382877.
Cf. A047966, A072774, A098859, A100471, A100881, A100882, A100883, A304442.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A239455 counts Look-and-Say partitions, ranks A351294, conjugate A381432.
A329738 counts compositions with equal run-lengths, ranks A353744.
A329739 counts compositions with distinct run-lengths, ranks A351596, complement A351291.
A351293 counts non-Look-and-Say partitions, ranks A351295, conjugate A381433.
Cf. A006171, A047993, A362608, A381871, A382076, A382771, A383111.

Table[Length[Select[IntegerPartitions[n],Length[Select[Permutations[#],SameQ@@Length/@Split[#]&]]<=1&]],{n,0,15}]

a(n) = A382915(n) + A383094(n).

More terms from Bert Dobbelaere, Apr 26 2025

A336343 Number of ways to choose a strict partition of each part of a strict composition of n.

Original entry on oeis.org

1, 1, 1, 4, 6, 11, 26, 39, 78, 142, 320, 488, 913, 1558, 2798, 5865, 9482, 16742, 28474, 50814, 82800, 172540, 266093, 472432, 790824, 1361460, 2251665, 3844412, 7205416, 11370048, 19483502, 32416924, 54367066, 88708832, 149179800, 239738369, 445689392

Offset: 0

Gus Wiseman, Jul 19 2020

nonn

A strict composition of n (A032020) is a finite sequence of distinct positive integers summing to n.

Is there a simple generating function?

			The a(1) = 1 through a(5) = 11 ways:
  (1)  (2)  (3)      (4)        (5)
            (2,1)    (3,1)      (3,2)
            (1),(2)  (1),(3)    (4,1)
            (2),(1)  (3),(1)    (1),(4)
                     (1),(2,1)  (2),(3)
                     (2,1),(1)  (3),(2)
                                (4),(1)
                                (1),(3,1)
                                (2,1),(2)
                                (2),(2,1)
                                (3,1),(1)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Multiset partitions of partitions are A001970.
Strict compositions are counted by A032020, A072574, and A072575.
Splittings of strict partitions are A072706.
Set partitions of strict partitions are A294617.
Splittings of partitions with distinct sums are A336131.
Cf. A008289, A011782, A304786, A318683, A318684, A319794, A323583, A336128, A336130, A336132, A336133.
Partitions:
- Partitions of each part of a partition are A063834.
- Compositions of each part of a partition are A075900.
- Strict partitions of each part of a partition are A270995.
- Strict compositions of each part of a partition are A336141.
Strict partitions:
- Partitions of each part of a strict partition are A271619.
- Compositions of each part of a strict partition are A304961.
- Strict partitions of each part of a strict partition are A279785.
- Strict compositions of each part of a strict partition are A336142.
Compositions:
- Partitions of each part of a composition are A055887.
- Compositions of each part of a composition are A133494.
- Strict partitions of each part of a composition are A304969.
- Strict compositions of each part of a composition are A307068.
Strict compositions:
- Partitions of each part of a strict composition are A336342.
- Compositions of each part of a strict composition are A336127.
- Strict partitions of each part of a strict composition are A336343.
- Strict compositions of each part of a strict composition are A336139.

strptn[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&];
Table[Length[Join@@Table[Tuples[strptn/@ctn],{ctn,Join@@Permutations/@strptn[n]}]],{n,0,10}]

\\ here Q(N) gives A000009 as a vector.
Q(n) = {Vec(eta(x^2 + O(x*x^n))/eta(x + O(x*x^n)))}
seq(n)={my(b=Q(n)); [subst(serlaplace(p),y,1) | p<-Vec(prod(k=1, n, 1 + y*x^k*b[1+k] + O(x*x^n)))]} \\ Andrew Howroyd, Apr 16 2021

G.f.: Sum_{k>=0} k! * [y^k](Product_{j>=1} 1 + y*x^j*A000009(j)). - Andrew Howroyd, Apr 16 2021

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

A344063 Expansion of Product_{k>=1} (1 + 4^(k-1)*x^k).

Original entry on oeis.org

1, 1, 4, 20, 80, 384, 1600, 7424, 30720, 143360, 593920, 2703360, 11403264, 51118080, 214958080, 965738496, 4047503360, 17951621120, 76168560640, 334202142720, 1411970498560, 6211596451840, 26203595472896, 114246130073600, 484815908372480, 2101441598586880, 8896148580335616

Offset: 0

Ilya Gutkovskiy, May 08 2021

nonn

Cf. A003056, A008289, A261568, A304961, A338673, A340103, A344062, A344064, A344065, A344066, A344067, A344068.

nmax = 26; CoefficientList[Series[Product[(1 + 4^(k - 1) x^k), {k, 1, nmax}], {x, 0, nmax}], x]
Table[Sum[Length[Select[IntegerPartitions[n, {k}], UnsameQ @@ # &]] 4^(n - k), {k, 0, Floor[(Sqrt[8 n + 1] - 1)/2]}], {n, 0, 26}]

seq(n)={Vec(prod(k=1, n, 1 + 4^(k-1)*x^k + O(x*x^n)))} \\ Andrew Howroyd, May 08 2021

a(n) = Sum_{k=0..A003056(n)} q(n,k) * 4^(n-k), where q(n,k) is the number of partitions of n into k distinct parts.

a(n) ~ (-polylog(2, -1/4))^(1/4) * 4^n * exp(2*sqrt(-polylog(2, -1/4)*n)) / (2*sqrt(5*Pi/4)*n^(3/4)). - Vaclav Kotesovec, May 09 2021

cp's OEIS Frontend

A097910 Number of parts in all compositions of n into distinct parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A367394 Number of integer partitions of n whose length is a semi-sum of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367395 Number of strict integer partitions of n whose length is the sum of two distinct parts.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A367398 Number of integer partitions of n whose length is not a semi-sum of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367399 Number of strict integer partitions of n whose length is not the sum of any two distinct parts.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A373118 Number T(n,k) of compositions of n such that the set of parts is [k]; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A383092 Number of integer partitions of n having at most one permutation with all equal run-lengths.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A336343 Number of ways to choose a strict partition of each part of a strict composition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A338556 Products of three prime numbers of even index.

Views