A367095 -id:A367095 - cp's OEIS frontend

A299701 Number of distinct subset-sums of the integer partition with Heinz number n.

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

Offset: 1

Gus Wiseman, Feb 17 2018

nonn

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

			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.

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

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.
The semi version is A366739, sum A366738, strict A366741.
Cf. A032302, A070933, A304792, A304793, A365543, A365920, A367095.

Table[Length[Union[Total/@Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]],{n,100}]

a(n) <= A000005(n) and a(n) = A000005(n) iff n is the Heinz number of a knapsack partition (A299702).

Comment corrected by Gus Wiseman, Aug 09 2024

A366738 Number of semi-sums of integer partitions of n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 06 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.

			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

The non-binary version is A304792.
The strict non-binary version is A365925.
For prime indices instead of partitions we have A366739.
The strict case is A366741.
A000041 counts integer partitions, strict A000009.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A126796 counts complete partitions, ranks A325781, strict A188431.
A276024 counts positive subset-sums of partitions, strict A284640.
A365924 counts incomplete partitions, ranks A365830, strict A365831.
Cf. A008967, A046663, A117855, A122768, A238628, A299701, A365543, A365544, A366753, A367095.

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

More terms from Alois P. Heinz, Nov 06 2023

A366740 Positive integers whose semiprime divisors do not all have different Heinz weights (sum of prime indices, A056239).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 05 2023

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.
From Robert Israel, Nov 06 2023: (Start)
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)

			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}

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.
Partitions of this type are counted by A366753, non-binary A366754.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A056239 adds up prime indices, row sums of A112798.
A299701 counts distinct subset-sums of prime indices, positive A304793.
A299702 ranks knapsack partitions, counted by A108917, strict A275972.
Semiprime divisors are listed by A367096 and have:
- square count: A056170
- sum: A076290
- squarefree count: A079275
- count: A086971
- firsts: A220264
Cf. A000720, A001248, A008967, A365541, A365920, A366737, A366738, A366741, A367093, A367095, A367097.

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:
sort(convert(R,list)); # Robert Israel, Nov 06 2023

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],!UnsameQ@@Total/@Union[Subsets[prix[#],{2}]]&]

These are numbers k such that A086971(k) > A366739(k).

A366754 Number of non-knapsack integer partitions of n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 08 2023

nonn

A multiset is non-knapsack if there exist two different submultisets with the same sum.

			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)

The complement is counted by A108917, strict A275972, ranks A299702.
These partitions have ranks A299729.
The strict case is A316402.
The binary version is A366753, ranks A366740.
A000041 counts integer partitions, strict A000009.
A276024 counts positive subset-sums of partitions, strict A284640.
A304792 counts subset-sum of partitions, strict A365925.
A365543 counts partitions with subset-sum k, complement A046663.
A365661 counts strict partitions with subset-sum k, complement A365663.
A366738 counts semi-sums of partitions, strict A366741.
Cf. A002033, A006827, A122768, A126796, A238628, A365923, A365924, A367095.

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

a(n) = A000041(n) - A108917(n).

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

Original entry on oeis.org

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, 1, 2, 1, 1, 1, 2, 0, 2, 2, 3, 0, 3, 0, 2, 3

Offset: 1

Gus Wiseman, Nov 04 2023

nonn

First differs from A086971 at a(90) = 3, A086971(90) = 4.
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.

			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.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to prime indices in the factorization of n.

The non-binary version is A299701.
Summing over partitions gives A366738, strict A366741.
For all sums of pairs of elements we have A367095.
Positions of first appearances are A367097.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A056239 adds up prime indices, row sums of A112798.
A299702 ranks knapsack partitions, counted by A108917.
Semiprime divisors are listed by A367096 and have:
- square count: A056170
- sum: A076290
- squarefree count: A079275
- count: A086971
- firsts: A220264
Cf. A000005, A000720, A001248, A008967, A117855, A304792, A304793, A365541, A365920, A366740, A366753, A367093.

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}]

A366739(n) = #Set(apply(d->((f)->sum(i=1,#f~,f[i,2]*primepi(f[i,1])))(factor(d)), select(d->2==bigomega(d), divisors(n)))); \\ Antti Karttunen, Jan 20 2025

a(n) <= A086971(n). - Antti Karttunen, Jan 20 2025

Data section extended to a(105) by Antti Karttunen, Jan 20 2025

A367093 Least positive integer with n more semiprime divisors than semi-sums of prime indices.

Original entry on oeis.org

1, 90, 630, 2310, 6930, 34650, 30030, 90090, 450450, 570570, 510510, 1531530, 7657650, 14804790, 11741730, 9699690, 29099070, 145495350

Offset: 0

Gus Wiseman, Nov 05 2023

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.
Are all primorials after 210 included?

			The terms together with their prime indices begin:
       1: {}
      90: {1,2,2,3}
     630: {1,2,2,3,4}
    2310: {1,2,3,4,5}
    6930: {1,2,2,3,4,5}
   34650: {1,2,2,3,3,4,5}
   30030: {1,2,3,4,5,6}
   90090: {1,2,2,3,4,5,6}
  450450: {1,2,2,3,3,4,5,6}
  570570: {1,2,3,4,5,6,8}
  510510: {1,2,3,4,5,6,7}

The first part (semiprime divisors) is A086971, firsts A220264.
The second part (semi-sums of prime indices) is A366739, firsts A367097.
All sums of pairs of prime indices are counted by A367095.
The non-binary version is A367105.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A056239 adds up prime indices, row sums of A112798.
A299701 counts subset-sums of prime indices, positive A304793.
Semiprime divisors are listed by A367096 and have:
- square count: A056170
- sum: A076290
- squarefree count: A079275
- count: A086971
- firsts: A220264
Cf. A000720, A001248, A008967, A117855, A304792, A365541, A365920, A366738, A366740, A366753.

nn=10000;
w=Table[Length[Union[Subsets[prix[n],{2}]]]-Length[Union[Total/@Subsets[prix[n],{2}]]],{n,nn}];
spnm[y_]:=Max@@NestWhile[Most,y,Union[#]!=Range[0,Max@@#]&];
Table[Position[w,k][[1,1]],{k,0,spnm[w]}]

from itertools import count
from sympy import factorint, primepi
from sympy.utilities.iterables import multiset_combinations
def A367093(n):
    for k in count(1):
        c, a = 0, set()
        for s in (sum(p) for p in multiset_combinations({primepi(i):j for i,j in factorint(k).items()},2)):
            if s not in a:
                a.add(s)
            else:
                c += 1
            if c > n:
                break
        if c == n:
            return k # Chai Wah Wu, Nov 13 2023

a(n) is the least positive integer such that A086971(a(n)) - A366739(a(n)) = n.

a(12)-a(16) from Chai Wah Wu, Nov 13 2023

a(17) from Chai Wah Wu, Nov 18 2023

A366753 Number of integer partitions of n without all different sums of two-element submultisets.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 07 2023

nonn

			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)

Semiprime divisors are counted by A086971, distinct sums A366739.
The non-binary complement is A108917, strict A275972, ranks A299702.
These partitions have ranks A366740.
The non-binary version is A366754, strict A316402, ranks A299729.
A276024 counts positive subset-sums of partitions, strict A284640.
A304792 counts subset-sum of partitions, strict A365925.
A365543 counts partitions with a subset-sum k, complement A046663.
A365661 counts strict partitions with a subset-sum k, complement A365663.
A366738 counts semi-sums of partitions, strict A366741.
A367096 lists semiprime divisors, row sums A076290.
Cf. A002033, A001358, A006827, A008967, A122768, A126796, A365923, A365924, A367093, A367095.

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

A367097 Least positive integer whose multiset of prime indices has exactly n distinct semi-sums.

Original entry on oeis.org

1, 4, 12, 30, 60, 210, 330, 660, 2730, 3570, 6270, 12540, 53130, 79170, 110670, 221340, 514140, 1799490, 2284590, 4196010, 6750870, 13501740, 37532220, 97350330, 131362770, 189620970, 379241940, 735844830, 1471689660

Offset: 0

Gus Wiseman, Nov 09 2023

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.
From David A. Corneth, Nov 15 2023: (Start)
Terms are cubefree.
bigomega(a(n)) = A001222(a(n)) >= A002024(n) + 1 = floor(sqrt(2n) + 1/2) + 1 for n > 0. (End)

			The prime indices of 60 are {1,1,2,3}, with four semi-sums {2,3,4,5}, and 60 is the first number whose prime indices have four semi-sums, so a(4) = 60.
The terms together with their prime indices begin:
       1: {}
       4: {1,1}
      12: {1,1,2}
      30: {1,2,3}
      60: {1,1,2,3}
     210: {1,2,3,4}
     330: {1,2,3,5}
     660: {1,1,2,3,5}
    2730: {1,2,3,4,6}
    3570: {1,2,3,4,7}
    6270: {1,2,3,5,8}
   12540: {1,1,2,3,5,8}
   53130: {1,2,3,4,5,9}
   79170: {1,2,3,4,6,10}
  110670: {1,2,3,4,7,11}
  221340: {1,1,2,3,4,7,11}
  514140: {1,1,2,3,5,8,13}

The non-binary version is A259941, firsts of A299701.
These are the positions of first appearances in A366739.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, complement A100959.
A056239 adds up prime indices, row sums of A112798.
A299702 ranks knapsack partitions, counted by A108917.
A366738 counts semi-sums of partitions, strict A366741.
Semiprime divisors are listed by A367096 and have:
- square count: A056170
- sum: A076290
- squarefree count: A079275
- count: A086971
- firsts: A220264
Cf. A000720, A001248, A002024, A004709, A304793, A365920, A366740, A366753, A367093, A367095.

nn=1000;
w=Table[Length[Union[Total/@Subsets[prix[n],{2}]]],{n,nn}];
spnm[y_]:=Max@@NestWhile[Most,y,Union[#]!=Range[0,Max@@#]&];
v=Table[Position[w,k][[1,1]],{k,0,spnm[w]}]

from itertools import count
from sympy import factorint, primepi
from sympy.utilities.iterables import multiset_combinations
def A367097(n): return next(k for k in count(1) if len({sum(s) for s in multiset_combinations({primepi(i):j for i,j in factorint(k).items()},2)}) == n) # Chai Wah Wu, Nov 13 2023

2 | a(n) for n > 0. - David A. Corneth, Nov 13 2023

a(17)-a(22) from Chai Wah Wu, Nov 13 2023

a(23)-a(28) from David A. Corneth, Nov 13 2023

A367412 Triangle read by rows with all zeros removed where T(n,k) is the number of integer partitions of n with k different semi-sums.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 3, 3, 1, 5, 3, 2, 1, 4, 7, 2, 1, 1, 6, 7, 6, 2, 1, 6, 10, 6, 7, 1, 7, 12, 11, 8, 3, 1, 6, 16, 11, 17, 3, 2, 1, 10, 14, 20, 19, 10, 2, 1, 1, 7, 22, 17, 31, 14, 7, 2, 1, 9, 22, 27, 37, 22, 11, 6, 1, 10, 24, 27, 51, 32, 16, 15

Offset: 0

Gus Wiseman, Nov 19 2023

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.

			Triangle begins:
  1
  1  1
  1  2
  1  3  1
  1  3  3
  1  5  3  2
  1  4  7  2  1
  1  6  7  6  2
  1  6 10  6  7
  1  7 12 11  8  3
  1  6 16 11 17  3  2
  1 10 14 20 19 10  2  1
  1  7 22 17 31 14  7  2
  1  9 22 27 37 22 11  6
  1 10 24 27 51 32 16 15
  1 11 27 39 57 43 27 22  4
  1  9 33 34 79 57 36 39  7  2
  1 13 31 51 86 77 45 62 14  4  1
Row n = 9 counts the following partitions:
  (9)  (81)         (711)       (621)      (5211)
       (72)         (6111)      (531)      (4311)
       (63)         (522)       (432)      (4221)
       (54)         (51111)     (33111)    (42111)
       (333)        (441)       (222111)   (3321)
       (111111111)  (411111)    (2211111)  (32211)
                    (3222)                 (321111)
                    (3111111)
                    (22221)
                    (21111111)

Row sums are A000041.
Column k = 1 is A088922.
The non-binary version (with zeros) is A365658.
The strict non-binary version (with zeros) is A365832.
The corresponding rank statistic is A366739.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A126796 counts complete partitions, ranks A325781, strict A188431.
A276024 counts positive subset-sums of partitions, strict A284640.
A365924 counts incomplete partitions, ranks A365830, strict A365831.
A366738 counts semi-sums of partitions, non-binary A304792.
A366741 counts semi-sums of strict partitions, non-binary A365925.
Cf. A046663, A117855, A122768, A238628, A299701, A365543, A366753, A367095.

DeleteCases[Table[Length[Select[IntegerPartitions[n], Length[Union[Total/@Subsets[#, {2}]]]==k&]], {n,10},{k,0,n}],0,2]

cp's OEIS Frontend

A299701 Number of distinct subset-sums of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A366738 Number of semi-sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A366740 Positive integers whose semiprime divisors do not all have different Heinz weights (sum of prime indices, A056239).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A366754 Number of non-knapsack integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A367093 Least positive integer with n more semiprime divisors than semi-sums of prime indices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A366753 Number of integer partitions of n without all different sums of two-element submultisets.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A367097 Least positive integer whose multiset of prime indices has exactly n distinct semi-sums.

Views

Author