A331541 a(n) is the maximum number of equal-sum subsets into which the first n primes can be partitioned.

1, 1, 2, 1, 2, 1, 2, 1, 2, 3, 4, 1, 2, 1, 4, 3, 5, 3, 4, 3, 4, 7, 2, 3, 5, 3, 4, 3, 8, 9, 8, 3, 7, 3, 4, 3, 8, 1, 2, 9, 2, 9, 2, 3, 4, 3, 14, 1, 13, 7, 10, 9, 11, 3, 2, 7, 10, 1, 2, 1, 13, 5, 14, 1, 2, 1, 13, 3, 11, 19, 10, 7, 2, 9, 2, 11, 19, 9, 19, 23, 4, 3

Offset

1,3

Comments

A331479 is a table, read by rows, in which the n-th row lists all the numbers m such that the first n primes can be partitioned into m subsets having the same sum. a(n) is the largest term of row n of A331479.

Links

Table of n, a(n) for n=1..82.

Example

a(19)=14; see Example section at A331479.
For n=47, prime(n) = 211, and the sum of the first n primes is 4438. The sum of each subset cannot be less than 211, so the number of subsets m cannot exceed 4438/211 = 21.03..., and since m must be a divisor of 4438, the possible values of m are 1, 2, 7, and 14. The largest is 14, and partitions of the first 47 primes into 14 subsets with equal sum 4438/14 = 317 do exist (e.g., (211,103,3), (199,79,19,13,7), (197,61,59), (193,101,23), (191,109,17), (181,89,47), (179,127,11), (173,139,5), (167,107,43), (163,83,71), (157,131,29), (151,113,53), (149,137,31), (97,73,67,41,37,2)), so a(47)=14.
For n=69, prime(n)=347, and the sum of the first n primes is 10538, whose divisors <= 10538/347 = 30.36... are 1, 2, 11, and 22. The largest is 22, but it is not possible to partition the first 69 primes into 22 subsets with equal sums. Proof: the equal sums would be 10538/22 = 479, so no subset could consist of a single prime (347 < 479) nor of exactly two primes (one of the primes would have to be 2, the other 479 - 2 = 477, which is not one of the first 69 primes), so each subset would consist of at least 3 primes. Assigning 69 primes to 22 subsets would require that at least 22*4 - 69 = 19 of the subsets receive exactly 3 primes each. Of the 69 primes, there are 1 (the prime 3) with size == 0 (mod 3), 32 with size == 1 (mod 3), and 36 with size == 2 (mod 3). Since only one prime has size == 0 (mod 3), at most one subset can contain a prime with size == 0 (mod 3), so at least 18 of the subsets must contain exactly 3 primes, none with size == 0 (mod 3), and since 479 mod 3 = 2, each of those 18 subsets must contain one prime with size == 1 (mod 3) and two with size == 2 (mod 3), but this is impossible since there are not 36 primes of size == 2 (mod 3) available for inclusion in 3-prime subsets: although there are exactly 36 primes of size == 2 (mod 3) among the first 69 primes, one of those 36 primes is 2, which (being even) cannot be included in a subset with two other primes and give a subset sum of 479 (an odd number). So no 22-subset solution exists (and since the next-largest divisor of 10538 is 11, and solutions with 11 subsets do exist, a(69)=11).

Crossrefs

Cf. A331479.

Sequence in context: A161273 A160977 A366931 * A030738 A341541 A359953

Adjacent sequences: A331538 A331539 A331540 * A331542 A331543 A331544

Keyword

nonn

Author

Jon E. Schoenfield, Jan 19 2020

Status

approved