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 < Nxy. x ranges over 1,2,...,floor(N/3)1. Since y < Nxy, 2y <= Nx1 and for each x, y then ranges over x+1,x+2,...,floor((Nx1)/2). Hence for each x there are floor((Nx1)/2)x sets that satisfy the conditions. Let N=2I+J where J is 0 or 1. Then floor((Nx1)/2)=I+floor((Jx1)/2)=Iceiling((1+xJ)/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 Ixceiling((1+x)/2) over all x from 1 to floor(N/3)1=K1. 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,...,(K1)/2,(K1)/2,(K+1)/2 if K is odd. Hence ceiling((x+1)/2) sums to (K/2)^2+K/21 when K is even and to ((K1)/2)^2+K1 when K is odd. The total we seek is thus I(K1)K(K1)/2(K/2)^2K/2+1 if K is even and I(K1)K(K1)/2((K1)/2)^2K+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 Ixceiling(x/2) over all x from 1 to floor(N/3)1=K1. Now ceiling(x/2) has values 1,1,2,2,...,(K2)/2,(K2)/2,K/2 if K is even and values 1,1,2,2,...,(K1)/2,(K1)/2 if K is odd. Hence ceiling(x/2) sums to (K/2)^2 when K is even and to (K^21)/4 when K is odd. The total we seek is thus I(K1)K(K1)/2(K^2)/4 if K is even and I(K1)K(K1)/2(K^21)/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(K1)K(K1)/2
P = Q  (K/2)^2K/2+1 if N is even and K is even
P = Q  ((K1)/2)^2K+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^21)/4 if N is odd and K is odd.
If N=6 so that I=3 and K=2 the total is I(K1)K(K1)/2(K/2)^2K/2+1 =3(1)2(1)/2(2/2)^22/2+1=3111+1=1.
If N=24 so that I=12 and K=8 the total is I(K1)K(K1)/2(K/2)^2K/2+1=12(7)8(7)/24^24+1=8428164+1=37.
If N=1000 so that I=500 and K=333 the total is I(K1)K(K1)/2((K1)/2)^2K+1=500(332)333(332)/2(332/2)^2333+1=
1660005527827556332=82834.
If N=25 so that I=12 and K=8 the total is I(K1)K(K1)/2(K^2)/4=12(7)8(7)/264/4=842816=40.
If N=11 so that I=5 and K=3 the total is I(K1)K(K1)/2(K^21)/4=5(2)3(2)/2(3^21)/4=1032=5.
Edited on July 23, 2004, 1:46 am

Posted by Richard
on 20040722 23:07:39 