Displaying 1-10 of 17 results found.
Number of distinct subset-sums of the integer partition with Heinz number n.
+10
69
1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 5, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 6, 3, 4, 4, 6, 2, 7, 2, 6, 4, 4, 4, 7, 2, 4, 4, 7, 2, 8, 2, 6, 6, 4, 2, 7, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 8, 2, 4, 5, 7, 4, 8, 2, 6, 4, 7, 2, 8, 2, 4, 6, 6, 4, 8, 2, 8, 5, 4, 2, 9, 4, 4, 4
COMMENTS
An integer n is a subset-sum of an integer partition y if there exists a submultiset of y with sum n. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).
Position of first appearance of n appears to be A259941(n-1) = least Heinz number of a complete partition of n-1. - Gus Wiseman, Nov 16 2023
EXAMPLE
The subset-sums of (5,1,1,1) are {0, 1, 2, 3, 5, 6, 7, 8} so a(88) = 8.
The subset-sums of (4,3,1) are {0, 1, 3, 4, 5, 7, 8} so a(70) = 7.
MATHEMATICA
Table[Length[Union[Total/@Subsets[Join@@Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]]], {n, 100}]
CROSSREFS
Cf. A000005, A000041, A000720, A001222, A056239, A108917, A112798, A122111, A122768, A215366, A276024, A284640, A296150, A299702. Positions of first appearances are A259941. The triangle for this rank statistic is A365658.
Number of semi-sums of integer partitions of n.
+10
21
0, 0, 1, 2, 5, 9, 17, 28, 46, 72, 111, 166, 243, 352, 500, 704, 973, 1341, 1819, 2459, 3277, 4363, 5735, 7529, 9779, 12685, 16301, 20929, 26638, 33878, 42778, 53942, 67583, 84600, 105270, 130853, 161835, 199896, 245788, 301890, 369208, 451046, 549002, 667370
COMMENTS
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.
EXAMPLE
The partitions of 6 and their a(6) = 17 semi-sums:
(6) ->
(51) -> 6
(42) -> 6
(411) -> 2,5
(33) -> 6
(321) -> 3,4,5
(3111) -> 2,4
(222) -> 4
(2211) -> 2,3,4
(21111) -> 2,3
(111111) -> 2
MATHEMATICA
Table[Total[Length[Union[Total/@Subsets[#, {2}]]]&/@IntegerPartitions[n]], {n, 0, 15}]
CROSSREFS
The strict non-binary version is A365925. For prime indices instead of partitions we have A366739.
Positive integers whose semiprime divisors do not all have different Heinz weights (sum of prime indices, A056239).
+10
14
90, 180, 210, 270, 360, 420, 450, 462, 525, 540, 550, 630, 720, 810, 840, 858, 900, 910, 924, 990, 1050, 1080, 1100, 1155, 1170, 1260, 1326, 1350, 1386, 1440, 1470, 1530, 1575, 1620, 1650, 1666, 1680, 1710, 1716, 1800, 1820, 1848, 1870, 1890, 1911, 1938, 1980
COMMENTS
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. Positive integers divisible by the product of four primes, prime(i)*prime(j)*prime(k)*prime(l), i < j <= k < l, with i + l = j + k.
All positive multiples of terms are terms. (End)
EXAMPLE
The semiprime divisors of 90 are (6,9,10,15), with prime indices ({1,2},{2,2},{1,3},{2,3}) with sums (3,4,4,5), which are not all different, so 90 is in the sequence.
The terms together with their prime indices begin:
90: {1,2,2,3}
180: {1,1,2,2,3}
210: {1,2,3,4}
270: {1,2,2,2,3}
360: {1,1,1,2,2,3}
420: {1,1,2,3,4}
450: {1,2,2,3,3}
462: {1,2,4,5}
525: {2,3,3,4}
540: {1,1,2,2,2,3}
550: {1,3,3,5}
630: {1,2,2,3,4}
720: {1,1,1,1,2,2,3}
MAPLE
N:= 10^4: # for terms <= N
P:= select(isprime, [$1..N]): nP:= nops(P):
R:= {}:
for i from 1 while P[i]*P[i+1]^2*P[i+2] < N do
for j from i+1 while P[i]*P[j]^2 * P[j+1] < N do
for k from j do
l:= j+k-i;
if l <= k or l > nP then break fi;
v:= P[i]*P[j]*P[k]*P[l];
if v <= N then
R:= R union {seq(t, t=v..N, v)};
fi
od od od:
MATHEMATICA
prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[1000], !UnsameQ@@Total/@Union[Subsets[prix[#], {2}]]&]
CROSSREFS
The complement is too dense.
For all divisors instead of just semiprimes we have A299729, strict A316402. Distinct semi-sums of prime indices are counted by A366739. A299701 counts distinct subset-sums of prime indices, positive A304793.
Semiprime divisors are listed by A367096 and have: Cf. A000720, A001248, A008967, A365541, A365920, A366737, A366738, A366741, A367093, A367095, A367097.
Number of non-knapsack integer partitions of n.
+10
14
0, 0, 0, 0, 1, 1, 4, 4, 10, 13, 23, 27, 52, 60, 94, 118, 175, 213, 310, 373, 528, 643, 862, 1044, 1403, 1699, 2199, 2676, 3426, 4131, 5256, 6295, 7884, 9479, 11722, 14047, 17296, 20623, 25142, 29942, 36299, 43081, 51950, 61439, 73668, 87040, 103748, 122149, 145155, 170487
COMMENTS
A multiset is non-knapsack if there exist two different submultisets with the same sum.
EXAMPLE
The a(4) = 1 through a(9) = 13 partitions:
(211) (2111) (321) (3211) (422) (3321)
(2211) (22111) (431) (4221)
(3111) (31111) (3221) (4311)
(21111) (211111) (4211) (5211)
(22211) (32211)
(32111) (33111)
(41111) (42111)
(221111) (222111)
(311111) (321111)
(2111111) (411111)
(2211111)
(3111111)
(21111111)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], !UnsameQ@@Total/@Union[Subsets[#]]&]], {n, 0, 15}]
CROSSREFS
These partitions have ranks A299729. A365661 counts strict partitions with subset-sum k, complement A365663.
Number of distinct semi-sums of the multiset of prime indices of n. Number of distinct sums of prime indices of semiprime divisors of n (counted by A086971).
+10
11
0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 2, 1, 1, 0, 2, 1, 1, 1, 2, 0, 3, 0, 1, 1, 1, 1, 3, 0, 1, 1, 2, 0, 3, 0, 2, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 1, 1, 0, 4, 0, 1, 2, 1, 1, 3, 0, 2, 1, 3, 0, 3, 0, 1, 2, 2, 1, 3, 0, 2, 1, 1, 0, 4, 1, 1, 1, 2, 0, 3
COMMENTS
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. 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.
EXAMPLE
The prime indices of 90 are {1,2,2,3}, with semi-sums
3 = 1+2
4 = 1+3 (or 2+2)
5 = 2+3
so a(90) = 3.
Alternatively, the semiprime divisors of 90 are (6,9,10,15), with prime indices ({1,2},{2,2},{1,3},{2,3}) with sums (3,4,4,5) so a(90) = 3.
MATHEMATICA
prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Table[Length[Union[Total/@Subsets[prix[n], {2}]]], {n, 100}]
CROSSREFS
For all sums of pairs of elements we have A367095. Positions of first appearances are A367097. Semiprime divisors are listed by A367096 and have: Cf. A000005, A000720, A001248, A008967, A117855, A304792, A304793, A365541, A365920, A366740, A366753, A367093.
Triangle read by rows where T(n,k) is the number of strict integer partitions of n with two distinct parts summing to k.
+10
9
1, 0, 1, 0, 0, 2, 1, 1, 1, 2, 1, 0, 1, 1, 3, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 4, 2, 2, 3, 2, 3, 2, 3, 4, 2, 2, 3, 2, 3, 3, 3, 3, 5, 3, 2, 4, 3, 4, 4, 5, 3, 4, 5, 3, 3, 5, 4, 4, 5, 5, 5, 4, 4, 6, 4, 3, 6, 5, 6, 5, 7, 5, 7, 4, 5, 6, 5, 5, 7, 7, 8, 7, 8, 8, 7, 7, 5, 5, 7
EXAMPLE
Triangle begins:
1
0 1
0 0 2
1 1 1 2
1 0 1 1 3
1 1 1 1 2 3
1 1 1 2 2 2 4
2 2 3 2 3 2 3 4
2 2 3 2 3 3 3 3 5
3 2 4 3 4 4 5 3 4 5
3 3 5 4 4 5 5 5 4 4 6
4 3 6 5 6 5 7 5 7 4 5 6
5 5 7 7 8 7 8 8 7 7 5 5 7
6 5 9 8 10 7 10 9 10 7 9 5 6 7
7 7 10 10 12 11 11 11 12 10 9 9 6 6 8
9 7 13 11 15 12 13 13 15 13 13 9 11 6 7 8
Row n = 9 counts the following strict partitions:
(6,2,1) (5,3,1) (4,3,2) (5,3,1) (6,2,1) (6,2,1) (8,1)
(4,3,2) (4,3,2) (5,3,1) (7,2)
(6,3)
(5,4)
Row n = 13 counts the following strict partitions (A=10, B=11, C=12):
A21 931 841 751 652 751 841 931 A21 A21 C1
7321 7321 832 742 643 7321 742 832 832 931 B2
6421 5431 7321 6421 6421 652 7321 7321 742 841 A3
6421 5431 5431 6421 643 643 652 751 94
5431 5431 5431 6421 85
76
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#, {2}], k]&]], {n, 3, 10}, {k, 3, n}]
CROSSREFS
For subsets instead of partitions we have A365541, non-binary A365381.
Number of integer partitions of n without all different sums of two-element submultisets.
+10
8
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 4, 9, 11, 22, 27, 48, 61, 98, 123, 188, 237, 345, 435, 611, 765, 1046, 1305, 1741, 2165, 2840, 3502, 4527, 5562, 7083, 8650, 10908, 13255, 16545, 20016, 24763, 29834, 36587, 43911, 53514, 63964, 77445, 92239, 111015, 131753
EXAMPLE
The two-element submultisets of y = {1,1,1,2,2,3} are {1,1}, {1,2}, {1,3}, {2,2}, {2,3}, with sums 2, 3, 4, 4, 5, which are not all different, so y is counted under a(10).
The a(8) = 1 through a(13) = 11 partitions:
(3221) (32211) (4321) (33221) (4332) (43321)
(32221) (43211) (5331) (53221)
(322111) (322211) (5421) (53311)
(3221111) (43221) (54211)
(322221) (332221)
(332211) (432211)
(432111) (3222211)
(3222111) (3322111)
(32211111) (4321111)
(32221111)
(322111111)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], !UnsameQ@@Total/@Union[Subsets[#, {2}]]&]], {n, 0, 30}]
CROSSREFS
These partitions have ranks A366740. A365661 counts strict partitions with a subset-sum k, complement A365663.
Number of integer partitions of n whose length is a semi-sum of the parts.
+10
8
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
COMMENTS
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.
EXAMPLE
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)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], MemberQ[Total/@Subsets[#, {2}], Length[#]]&]], {n, 0, 10}]
CROSSREFS
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
-----------------------------------------------------------
Triangles:
Cf. A000700, A088809, A093971, A126796, A238628, A304792, A363225, A364534, A365541, A365924, A367402.
Number of strict integer partitions of n whose length is the sum of two distinct parts.
+10
8
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
EXAMPLE
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
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#, {2}], Length[#]]&]], {n, 0, 30}]
CROSSREFS
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
-----------------------------------------------------------
Triangles:
A365541 counts subsets with a semi-sum k.
Number of subsets of {1..n} whose cardinality is the sum of two distinct elements.
+10
8
0, 0, 0, 1, 3, 7, 17, 40, 90, 199, 435, 939, 2007, 4258, 8976, 18817, 39263, 81595, 168969, 348820, 718134, 1474863, 3022407, 6181687, 12621135, 25727686, 52369508, 106460521, 216162987, 438431215, 888359841, 1798371648, 3637518354, 7351824439, 14848255803
FORMULA
a(n) = 4*a(n-1) - 5*a(n-2) + 4*a(n-3) - 5*a(n-4) + 2*a(n-5) for n > 4.
G.f.: x^3*(x - 1)/((2*x - 1)*(x^4 - 2*x^3 + x^2 - 2*x + 1)). (End)
EXAMPLE
The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is not counted under a(8).
The a(0) = 0 through a(6) = 17 subsets:
. . . {1,2,3} {1,2,3} {1,2,3} {1,2,3}
{1,2,4} {1,2,4} {1,2,4}
{1,2,3,4} {1,2,5} {1,2,5}
{1,2,3,4} {1,2,6}
{1,2,3,5} {1,2,3,4}
{1,3,4,5} {1,2,3,5}
{1,2,3,4,5} {1,2,3,6}
{1,3,4,5}
{1,3,4,6}
{1,3,5,6}
{1,2,3,4,5}
{1,2,3,4,6}
{1,2,3,5,6}
{1,2,4,5,6}
{1,3,4,5,6}
{2,3,4,5,6}
{1,2,3,4,5,6}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#, {2}], Length[#]]&]], {n, 0, 10}]
PROG
(Python)
from itertools import combinations
def A367396(n): return sum(1 for k in range(3, n+1) for w in (set(d) for d in combinations(range(1, n+1), k)) if any({a, k-a}<=w for a in range(1, k+1>>1))) # Chai Wah Wu, Nov 21 2023
CROSSREFS
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
-----------------------------------------------------------
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
Search completed in 0.020 seconds
| 