A331541 - OEIS

%I #7 Jul 03 2024 20:06:08

%S 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,

%T 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,

%U 1,13,3,11,19,10,7,2,9,2,11,19,9,19,23,4,3

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

%C 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.

%e a(19)=14; see Example section at A331479.

%e 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.

%e 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).

%Y Cf. A331479.

%K nonn

%O 1,3

%A _Jon E. Schoenfield_, Jan 19 2020