There are 40 ways to make sums of three distinct positive integers total 25. (1+2+22 is such a sum, but 1+12+12 and 1+2+3+19 are not.)

How many different ways can three distinct positive integers sum to 1000?

The various sets {x,y,z} of positive integers that add up to a given value N may be enumerated as follows. We may suppose that 0 < x < y < N-x-y. x ranges over 1,2,...,floor(N/3)-1. Since y < N-x-y, 2y <= N-x-1 and for each x, y then ranges over x+1,x+2,...,floor((N-x-1)/2). Hence for each x there are floor((N-x-1)/2)-x sets that satisfy the conditions. Let N=2I+J where J is 0 or 1. Then floor((N-x-1)/2)=I+floor((J-x-1)/2)=I-ceiling((1+x-J)/2). Consider now the two cases J=0 and J=1.

J=0 (i.e. N is even). To obtain the total number of sets that satisfy the conditions we must sum the quantities I-x-ceiling((1+x)/2) over all x from 1 to floor(N/3)-1=K-1. Now ceiling((1+x)/2) has values 1,2,2,3,3,...,K/2,K/2 if K is even and values 1,2,2,...,(K-1)/2,(K-1)/2,(K+1)/2 if K is odd. Hence ceiling((x+1)/2) sums to (K/2)^2+K/2-1 when K is even and to ((K-1)/2)^2+K-1 when K is odd. The total we seek is thus I(K-1)-K(K-1)/2-(K/2)^2-K/2+1 if K is even and I(K-1)-K(K-1)/2-((K-1)/2)^2-K+1 if K is odd.

J=1 (i.e. N is odd). To obtain the total number of sets that satisfy the conditions we must sum the quantities I-x-ceiling(x/2) over all x from 1 to floor(N/3)-1=K-1. Now ceiling(x/2) has values 1,1,2,2,...,(K-2)/2,(K-2)/2,K/2 if K is even and values 1,1,2,2,...,(K-1)/2,(K-1)/2 if K is odd. Hence ceiling(x/2) sums to (K/2)^2 when K is even and to (K^2-1)/4 when K is odd. The total we seek is thus I(K-1)-K(K-1)/2-(K^2)/4 if K is even and I(K-1)-K(K-1)/2-(K^2-1)/4 if K is odd.

SUMMARY OF FORMULAS:

N=given number I=floor(N/2) K=floor(N/3)

P=number of partitions of N into 3 distinct positive integral parts

Q = I(K-1)-K(K-1)/2

P = Q - (K/2)^2-K/2+1      if N is even and K is even
P = Q - ((K-1)/2)^2-K+1    if N is even and K is odd
P = Q - (K^2)/4                 if N is odd  and K is even
P = Q - (K^2-1)/4              if N is odd  and K is odd.

If N=6 so that I=3 and K=2 the total is I(K-1)-K(K-1)/2-(K/2)^2-K/2+1 =3(1)-2(1)/2-(2/2)^2-2/2+1=3-1-1-1+1=1.
If N=24 so that I=12 and K=8 the total is I(K-1)-K(K-1)/2-(K/2)^2-K/2+1=12(7)-8(7)/2-4^2-4+1=84-28-16-4+1=37.

If N=1000 so that I=500 and K=333 the total is I(K-1)-K(K-1)/2-((K-1)/2)^2-K+1=500(332)-333(332)/2-(332/2)^2-333+1=
166000-55278-27556-332=82834.

If N=25 so that I=12 and K=8 the total is I(K-1)-K(K-1)/2-(K^2)/4=12(7)-8(7)/2-64/4=84-28-16=40.

If N=11 so that I=5 and K=3 the total is I(K-1)-K(K-1)/2-(K^2-1)/4=5(2)-3(2)/2-(3^2-1)/4=10-3-2=5.

Edited on July 23, 2004, 1:46 am

Posted by Richard on 2004-07-22 23:07:39