A339272 a(n) is the smallest number k that can be partitioned into a set of n positive integers {e(1), e(2), ..., e(n)} where Sum_{i=1..n} e(i)*(e(i)-1) = k*(k-1)/2.

4, 13, 17, 40, 24, 21, 44, 41, 41, 57, 48, 48, 68, 65, 65, 81, 85, 72, 72, 85, 89, 89, 105, 109, 109, 96, 116, 133, 113, 113, 133, 133, 140, 140, 120, 157, 153, 137, 157, 164, 164, 164, 181, 181, 181, 181, 188, 188, 201, 188, 205, 205, 225, 212, 205, 212, 212, 229, 229, 229, 229, 249, 249, 256, 236, 236, 253, 253, 253

Offset: 2

Author

Dean D. Ballard, Nov 29 2020

Keywords

• nonn

Comments

These numbers solve the problem of what is the required minimum number of socks of n colors such that a random drawing of two socks has a 50% chance of matching. In this version there may be a color with only one sock, and the number of socks of each color need not be distinct.

If the set solving a(n)=k has three 2's, then a(n+1)<=k, replacing them with one 3 and three 1's; this leads to many repeats in the data. Similar substitutions include {4, 5} for {1, 2, 6}, {3, 3, 4} for {1, 2, 2, 5}, and {3, 3} for {1, 1, 4}. - Dean D. Ballard and Michael S. Branicky, Nov 30 2020

Examples

			For n = 4, {1, 2, 2, 12} is the set with the smallest sum that has this property. With 1 sock of one color, 2 socks of a second color, 2 socks of a third color, and 12 socks of a fourth color, there is exactly a 50% chance that a random draw of two socks will produce a matching pair. (1*0 + 2*1 + 2*1 + 12*11) = (17*16) / 2.
n = 2, sum = 4, set = {1, 3}
n = 3, sum = 13, set = {1, 3, 9}
n = 4, sum = 17, set = {1, 2, 2, 12}
n = 5, sum = 40, set = {3, 3, 3, 3, 28}
n = 6, sum = 24, set = {1, 1, 1, 2, 2, 17}
		

Crossrefs

A246750, A332105, A339271 are other variations of the problem.

Programs

PARI

\\ See 'Faster PARI Program' link in A246750 for PartsByWeight.
a(n)={local(FC=Map()); for(k=1, oo, if(PartsByWeight(n, k, k*(k-1)/2, (i,v)->v*(v-1)), return(k))); oo} \\ Andrew Howroyd, Nov 30 2020

Extensions

a(26)-a(70) from Andrew Howroyd, Nov 30 2020