A299701 -id:A299701 - cp's OEIS frontend

A237194 Triangular array: T(n,k) = number of strict partitions P of n into positive parts such that P includes a partition of k.

1, 0, 1, 1, 1, 2, 1, 0, 1, 2, 1, 1, 1, 1, 3, 2, 2, 1, 2, 2, 4, 2, 2, 2, 2, 2, 2, 5, 3, 2, 3, 1, 3, 2, 3, 6, 3, 3, 4, 3, 3, 4, 3, 3, 8, 5, 4, 5, 4, 3, 4, 5, 4, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 12, 7, 6, 7, 7, 7, 4, 7, 7, 7, 6, 7, 15, 8, 7, 8, 8, 8, 8, 8

Offset: 1

Clark Kimberling, Feb 05 2014

			First 13 rows:
1
0 1
1 1 2
1 0 1 2
1 1 1 1 3
2 2 1 2 2 4
2 2 2 2 2 2 5
3 2 3 1 3 2 3 6
3 3 4 3 3 4 3 3 8
5 4 5 4 3 4 5 4 5 10
5 5 5 5 5 5 5 5 5 5 12
7 6 7 7 7 4 7 7 7 6 7 15
8 7 8 8 8 8 8 8 8 8 7 8 18
T(12,4) = 7 counts these partitions:  [8,4], [8,3,1], [7,4,1], [6,4,2], [6,3,2,1], [5,4,3], [5,4,2,1].

Clark Kimberling, Table of n, a(n) for n = 1..1000

Column k = n is A000009.
Column k = 2 is A015744.
Column k = 1 is A025147.
The non-strict complement is obtained by adding zeros after A046663.
Diagonal n = 2k is A237258.
Row sums are A284640.
For subsets instead of partitions we have A365381.
The non-strict version is obtained by removing column k = 0 from A365543.
Including column k = 0 gives A365661.
The complement is obtained by adding zeros after A365663.
Cf. A002219, A006827, A108796, A108917, A122768, A275972, A299701, A304792, A364272.

Table[theTotals = Map[{#, Map[Total, Subsets[#]]} &, Select[IntegerPartitions[nn], # == DeleteDuplicates[#] &]]; Table[Length[Map[#[[1]] &, Select[theTotals, Length[Position[#[[2]], sumTo]] >= 1 &]]], {sumTo, nn}], {nn, 45}] // TableForm
u = Flatten[%]  (* Peter J. C. Moses, Feb 04 2014 *)
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#], k]&]], {n,6}, {k,n}] (* Gus Wiseman, Nov 16 2023 *)

T(n,k) = T(n,n-k) for k=1..n-1, n >= 2.

A301829 Number of ways to choose a nonempty submultiset of a factorization of n into factors greater than one.

Original entry on oeis.org

0, 1, 1, 3, 1, 4, 1, 7, 3, 4, 1, 12, 1, 4, 4, 15, 1, 12, 1, 12, 4, 4, 1, 29, 3, 4, 7, 12, 1, 17, 1, 29, 4, 4, 4, 37, 1, 4, 4, 29, 1, 17, 1, 12, 12, 4, 1, 64, 3, 12, 4, 12, 1, 29, 4, 29, 4, 4, 1, 53, 1, 4, 12, 54, 4, 17, 1, 12, 4, 17, 1, 92, 1, 4, 12, 12, 4, 17

Offset: 1

Gus Wiseman, Mar 27 2018

nonn

			The a(12) = 12 submultisets ("<" means subset or equal):
(2)<(2*2*3), (3)<(2*2*3), (2*2)<(2*2*3), (2*3)<(2*2*3), (2*2*3)<(2*2*3),
(2)<(2*6), (6)<(2*6), (2*6)<(2*6),
(3)<(3*4), (4)<(3*4), (3*4)<(3*4),
(12)<(12).

Cf. A000712, A001055, A001222, A001405, A122768, A276024, A281113, A284640, A295632, A299701, A299702, A299729, A301830.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[Length[facs[d]]*Length[facs[n/d]],{d,Rest[Divisors[n]]}],{n,100}]

a(n) = Sum_{d|n, d>1} f(d) * f(n/d) where f(n) = A001055(n) is the number of factorizations of n into factors greater than 1.

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

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 10, 2, 3, 1, 21, 1, 3, 3, 58, 1, 21, 1, 21, 3, 3, 1, 164, 2, 3, 10, 21, 1, 34, 1, 373, 3, 3, 3, 218, 1, 3, 3, 161, 1, 7, 1, 5, 5, 3, 1, 1320, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 7, 1, 3, 4, 2558, 3, 7, 1, 5, 3, 6, 1, 7

Offset: 1

Gus Wiseman, Mar 28 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The composite of a positive subset-sum tree is the positive subset-sum x <= g where x is the root sum and g is the multiset of leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

Gus Wiseman, The a(12) = 21 positive subset-sum trees.

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301934.

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 4, 1, 6, 1, 13, 4, 6, 1, 25, 1, 6, 6, 38, 1, 26, 1, 26, 6, 6

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r. The composite of a triangle is (r, g_1 + ... + g_k) where + is multiset union.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(8) = 13 triangles:
  1(1(1,1,1))
  2(2(1,1,1))
  3(3(1,1,1))
  1(1(1),1(1,1))
  2(1(1),1(1,1))
  1(1(1),2(1,1))
  2(1(1),2(1,1))
  3(1(1),2(1,1))
  1(1(1,1),1(1))
  2(1(1,1),1(1))
  1(1(1),1(1),1(1))
  2(1(1),1(1),1(1))
  3(1(1),1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A299701, A301934, A301935, A316219, A316220, A316222.

A325801 Number of divisors of n minus the number of distinct positive subset-sums of the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, May 23 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, with sum A056239(n). A positive subset-sum of an integer partition is any sum of a nonempty submultiset of it.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Positions of 0's are A299702.
Positions of 1's are A325802.
Positions of positive integers are A299729.
Cf. A000005, A002033, A056239, A108917, A112798, A276024, A304793.
Cf. A325694, A325780, A325781, A325792, A325793, A325799.

hwt[n_]:=Total[Cases[FactorInteger[n],{p_,k_}:>PrimePi[p] k]];
Table[DivisorSigma[0,n]-Length[Union[hwt/@Divisors[n]]],{n,100}]

A325801(n) = (numdiv(n) - A299701(n));
A299701(n) = { my(f = factor(n), pids = List([])); for(i=1,#f~, while(f[i,2], f[i,2]--; listput(pids,primepi(f[i,1])))); pids = Vec(pids); my(sv=vector(vecsum(pids))); for(b=1,(2^length(pids))-1,sv[sumbybits(pids,b)] = 1); 1+vecsum(sv); }; \\ Not really an optimal way to count these.
sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); }; \\ Antti Karttunen, May 26 2019

a(n) = A000005(n) - A299701(n).

A334967 Numbers k such that the every subsequence (not necessarily contiguous) of the k-th composition in standard order (A066099) has a different sum.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 19, 20, 21, 24, 26, 28, 31, 32, 33, 34, 35, 36, 40, 42, 48, 56, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 80, 81, 84, 85, 88, 96, 98, 100, 104, 106, 112, 120, 127, 128, 129, 130, 131, 132, 133, 134

Offset: 1

Gus Wiseman, Jun 02 2020

nonn

First differs from A333223 in lacking 41.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
   0: ()           18: (3,2)          48: (1,5)
   1: (1)          19: (3,1,1)        56: (1,1,4)
   2: (2)          20: (2,3)          63: (1,1,1,1,1,1)
   3: (1,1)        21: (2,2,1)        64: (7)
   4: (3)          24: (1,4)          65: (6,1)
   5: (2,1)        26: (1,2,2)        66: (5,2)
   6: (1,2)        28: (1,1,3)        67: (5,1,1)
   7: (1,1,1)      31: (1,1,1,1,1)    68: (4,3)
   8: (4)          32: (6)            69: (4,2,1)
   9: (3,1)        33: (5,1)          70: (4,1,2)
  10: (2,2)        34: (4,2)          71: (4,1,1,1)
  12: (1,3)        35: (4,1,1)        72: (3,4)
  15: (1,1,1,1)    36: (3,3)          73: (3,3,1)
  16: (5)          40: (2,4)          74: (3,2,2)
  17: (4,1)        42: (2,2,2)        80: (2,5)

These compositions are counted by A334268.
Golomb rulers are counted by A169942 and ranked by A333222.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and ranked by A299702
Knapsack compositions are counted by A325676 and ranked by A333223.
The case of partitions is counted by A325769 and ranked by A325778.
Contiguous subsequence-sums are counted by A333224 and ranked by A333257.
Number of (not necessarily contiguous) subsequences is A334299.
Cf. A000120, A029931, A048793, A066099, A070939, A108917, A124771, A325770, A334300, A334967.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],UnsameQ@@Total/@Union[Subsets[stc[#]]]&]

A365919 Heinz numbers of integer partitions with the same number of distinct positive subset-sums as distinct non-subset-sums.

Original entry on oeis.org

1, 3, 9, 21, 22, 27, 63, 76, 81, 117, 147, 175, 186, 189, 243, 248, 273, 286, 290, 322, 345, 351, 399, 418, 441, 513, 516, 567, 688, 715, 729, 819, 1029, 1053, 1062, 1156, 1180, 1197, 1323, 1375, 1416, 1484, 1521, 1539, 1701, 1827, 1888, 1911, 2068, 2115, 2130

Offset: 1

Gus Wiseman, Sep 25 2023

nonn

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The terms together with their prime indices begin:
     1: {}
     3: {2}
     9: {2,2}
    21: {2,4}
    22: {1,5}
    27: {2,2,2}
    63: {2,2,4}
    76: {1,1,8}
    81: {2,2,2,2}
   117: {2,2,6}
   147: {2,4,4}
   175: {3,3,4}
   186: {1,2,11}
   189: {2,2,2,4}
   243: {2,2,2,2,2}

The LHS is A304793, counted by A365658, with empty sets A299701.
The RHS is A325799, counted by A365923 (strict A365545).
A046663 counts partitions without a subset summing to k, strict A365663.
A056239 adds up prime indices, row sums of A112798.
A276024 counts positive subset-sums of partitions, strict A284640.
A325781 ranks complete partitions, counted by A126796.
A365830 ranks incomplete partitions, counted by A365924.
A365918 counts non-subset-sums of partitions, strict A365922.
Cf. A001223, A005117, A006827, A073491, A188431, A304792, A365831.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
smu[y_]:=Union[Total/@Rest[Subsets[y]]];
nmz[y_]:=Complement[Range[Total[y]],Total/@Subsets[y]];
Select[Range[100],Length[smu[prix[#]]]==Length[nmz[prix[#]]]&]

Positive integers k such that A304793(k) = A325799(k).

A301979 Number of subset-sums minus number of subset-products of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 0, 2, 0, 2, 0, 3, 0, 2, 0, 3, 0, 2, 0, 4, 0, 3, 0, 4, 0, 2, 0, 4, 0, 2, 0, 4, 0, 3, 0, 5, 0, 2, 0, 4, 0, 2, 0, 5, 0, 4, 0, 4, 0, 2, 0, 5, 0, 3, 0, 4, 0, 4, 0, 6, 0, 2, 0, 4, 0, 2, 0, 6, 0, 4, 0, 4, 0, 3, 0, 5, 0, 2, 0, 4, 0, 4, 0, 6, 0, 2, 0, 5, 0, 2, 0

Offset: 1

Gus Wiseman, Mar 30 2018

sign

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A subset-sum (or subset-product) of a multiset y is any number equal to the sum (or product) of some submultiset of y.
First negative entry is a(165) = -1.
This sequence is unbounded above and below.

			The distinct subset-sums of (4,2,1,1) are 0, 1, 2, 3, 4, 5, 6, 7, 8, while the distinct subset-products are 1, 2, 4, 8, so a(84) = 9 - 4 = 5.
The distinct subset-sums of (5,3,2) are 0, 2, 3, 5, 7, 8, 10, while the distinct subset-products are 1, 2, 3, 5, 6, 10, 15, 30, so a(165) = 7 - 8 = -1.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A000712, A003963, A056239, A108917, A276024, A284640, A296150, A299701, A301854, A301855, A301856, A301957, A301970.

Table[With[{ptn=If[n===1,{},Join@@Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]},Length[Union[Plus@@@Subsets[ptn]]]-Length[Union[Times@@@Subsets[ptn]]]],{n,100}]

A003963(n) = {n=factor(n); n[, 1]=apply(primepi, n[, 1]); factorback(n)};
A301957(n) = {my(ds = divisors(n)); for(i=1,#ds,ds[i] = A003963(ds[i])); #Set(ds)};
A056239(n) = if(1==n,0,my(f=factor(n)); sum(i=1, #f~, f[i,2] * primepi(f[i,1])));
A299701(n) = {my(ds = divisors(n)); for(i=1,#ds,ds[i] = A056239(ds[i])); #Set(ds)};
A301979(n) = (A299701(n) - A301957(n)); \\ Antti Karttunen, Oct 07 2018

a(n) = A299701(n) - A301957(n).

A325802 Numbers with one more divisor than distinct subset-sums of their prime indices.

Original entry on oeis.org

12, 30, 40, 63, 70, 112, 154, 165, 198, 220, 273, 286, 325, 351, 352, 364, 442, 525, 550, 561, 595, 646, 675, 714, 741, 748, 765, 832, 850, 874, 918, 931, 952, 988, 1045, 1173, 1254, 1334, 1425, 1495, 1539, 1564, 1653, 1666, 1672, 1771, 1794, 1798, 1870, 1900

Offset: 1

Gus Wiseman, May 23 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. A subset-sum of an integer partition is any sum of a submultiset of it.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of the partitions counted by A325835.

			The sequence of terms together with their prime indices begins:
   12: {1,1,2}
   30: {1,2,3}
   40: {1,1,1,3}
   63: {2,2,4}
   70: {1,3,4}
  112: {1,1,1,1,4}
  154: {1,4,5}
  165: {2,3,5}
  198: {1,2,2,5}
  220: {1,1,3,5}
  273: {2,4,6}
  286: {1,5,6}
  325: {3,3,6}
  351: {2,2,2,6}
  352: {1,1,1,1,1,5}
  364: {1,1,4,6}
  442: {1,6,7}
  525: {2,3,3,4}
  550: {1,3,3,5}
  561: {2,5,7}

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

Positions of 1's in A325801.
Cf. A000005, A056239, A108917, A112798, A276024, A299701, A299702.
Cf. A325694, A325780, A325781, A325799, A325800, A325835.

filter:= proc(n) local F,t,S,i;
  F:= map(t -> [numtheory:-pi(t[1]),t[2]], ifactors(n)[2]);
  S:= {0}:
  for t in F do
   S:= map(s -> seq(s + i*t[1],i=0..t[2]),S);
  od;
  nops(S) = mul(t[2]+1,t=F)-1
end proc:
select(filter, [$1..2000]); # Robert Israel, Oct 30 2024

Select[Range[100],DivisorSigma[0,#]==1+Length[Union[hwt/@Divisors[#]]]&]

A000005(a(n)) = 1 + A299701(a(n)).

cp's OEIS Frontend

A237194 Triangular array: T(n,k) = number of strict partitions P of n into positive parts such that P includes a partition of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A301829 Number of ways to choose a nonempty submultiset of a factorization of n into factors greater than one.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Links

Crossrefs

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A325801 Number of divisors of n minus the number of distinct positive subset-sums of the prime indices of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334967 Numbers k such that the every subsequence (not necessarily contiguous) of the k-th composition in standard order (A066099) has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A365919 Heinz numbers of integer partitions with the same number of distinct positive subset-sums as distinct non-subset-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A301979 Number of subset-sums minus number of subset-products of the integer partition with Heinz number n.

Views

Author

Keywords