login
A331541
a(n) is the maximum number of equal-sum subsets into which the first n primes can be partitioned.
0
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.
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
KEYWORD
nonn
AUTHOR
Jon E. Schoenfield, Jan 19 2020
STATUS
approved