A331479 Table read by rows: row n lists the numbers m such that the first n primes can be partitioned into m subsets all of which have the same sum.

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 1, 3, 1, 2, 4, 5, 1, 3, 1, 2, 4, 1, 3, 1, 2, 4, 1, 7, 1, 2, 1, 3, 1, 2, 4, 5, 1, 3, 1, 2, 4, 1, 3, 1, 2, 4, 5, 8, 1, 3, 9, 1, 2, 4, 5, 8, 1, 3, 1, 2, 4, 7, 1, 3, 1, 2, 4, 1, 3, 1, 2, 4, 8

Offset: 1

Author

Jon E. Schoenfield, Jan 17 2020

Keywords

• nonn
• tabf

Comments

Consider the following one-dimensional bin packing problem: given n items whose sizes are the first n primes, list the numbers m such that all the items can be packed into m bins of identical capacity, with each bin packed completely full. The resulting list is row n.

If a row contains a number m, it necessarily contains all divisors of m.

Examples

			In bin-packing terms, for n=19, the sum of the 19 item sizes, i.e., the sum of the first n primes, is 2 + 3 + ... + 67 = 568, whose divisors begin 1, 2, 4, 8, ...; the bin capacity must be at least 67 (the size of the largest item), and 568/67 < 9, so the number of bins m cannot exceed 8. However, the 19 items cannot be packed into 8 bins: the bin capacity would be 568/8 = 71 (which, as an odd sum, would require that each bin containing only odd-sized items -- i.e., every bin other than the one containing the item of size 2 -- contain an odd number of items, hence at least 3 items, but there are only 19 items in total). So the remaining values of m are 1 (i.e., packing all 19 items in a single bin), 2 (e.g., 568/2 = 284 = 67 + 61 + 59 + 53 + 41 + 3 = 47 + 43 + 37 + 31 + 29 + 23 + 19 + 17 + 13 + 11 + 7 + 5 + 2), and 4 (e.g., 568/4 = 142 = 67 + 61 + 11 + 3 = 59 + 53 + 23 + 7 = 47 + 43 + 37 + 13 + 2 = 41 + 31 + 29 + 19 + 17 + 5), so row 19 consists of the numbers 1, 2, and 4.
.                                       Numbers m such that
             Sum of  Divisors m of sum  1st n primes can be
      n-th   1st n       such that      partitioned into m
   n  prime  primes  m <= sum/prime(n)  subsets w/same sum
  --  -----  ------  -----------------  -------------------
   1     2       2   1                  1;
   2     3       5   1                  1;
   3     5      10   1, 2               1, 2;
   4     7      17   1                  1;
   5    11      28   1, 2               1, 2;
   6    13      41   1                  1;
   7    17      58   1, 2               1, 2;
   8    19      77   1                  1;
   9    23     100   1, 2, 4            1, 2;
  10    29     129   1, 3               1, 3;
  11    31     160   1, 2, 4, 5         1, 2, 4;
  12    37     197   1                  1;
  13    41     238   1, 2               1, 2;
  14    43     281   1                  1;
  15    47     328   1, 2, 4            1, 2, 4;
  16    53     381   1, 3               1, 3;
  17    59     440   1, 2, 4, 5         1, 2, 4, 5;
  18    61     501   1, 3               1, 3;
  19    67     568   1, 2, 4, 8         1, 2, 4;
  20    71     639   1, 3, 9            1, 3;
  21    73     712   1, 2, 4, 8         1, 2, 4;
  22    79     791   1, 7               1, 7;
  23    83     874   1, 2               1, 2;
  24    89     963   1, 3, 9            1, 3;
  25    97    1060   1, 2, 4, 5, 10     1, 2, 4, 5;
  26   101    1161   1, 3, 9            1, 3;
  27   103    1264   1, 2, 4, 8         1, 2, 4;
  28   107    1371   1, 3               1, 3;
  29   109    1480   1, 2, 4, 5, 8, 10  1, 2, 4, 5, 8;
  30   113    1593   1, 3, 9            1, 3, 9;
  31   127    1720   1, 2, 4, 5, 8, 10  1, 2, 4, 5, 8;
  32   131    1851   1, 3               1, 3;
  33   137    1988   1, 2, 4, 7, 14     1, 2, 4, 7;
  34   139    2127   1, 3               1, 3;
  35   149    2276   1, 2, 4            1, 2, 4;
  36   151    2427   1, 3               1, 3;
  37   157    2584   1, 2, 4, 8         1, 2, 4, 8;
		

Crossrefs

Cf. A000040, A007504, A053050, A306443, A327449.