Problem 4

4. Find the sum of the 4536 numbers from 1,000 to 10,000 which have all their digits distinct. This is really two problems: (a) Find a solution by using brute force on the computer; (b) find a solution by doing it analytically by hand.

Commentary: The solution was easy to compute using code, and there were no surprises in trying to derive it by hand.

Proof: (a) The following code in Python produces the desired result: 24,917,760.

def distinct_digits(x):
    x = str(x)
    for k in range(len(x)):
        if x.index(x[k]) != k:
            return(False)
    return(True)

sum(filter(distinct_digits,[x for x in range(1000,10000)]))

(b) We may decompose each number with distinct digits into its base-ten form $d_0d_1d_2d_3=d_0·10^3+d_1·10^2+d_2·10^1+d_3·10^0$, and thus obtain the sum of numbers with distinct digits as the sum of sums of their digits multiplied by their proper powers of ten. To find the sum of the thousands-place digits, we may observe that combinatorially there are $9·8·7=504$ numbers with any given thousands-place digit, and for nonzero digits (the only ones that would affect the sum) in the hundreds, tens, or ones place there are $8·8·7=448$ numbers accommodating them each. Hence the sum is $$(1000+2000+...+9000)(504)+(100+200+...+900)(448)+$$ $$(10+20+...+90)(448)+(1+2+...+9)(448)=24,917,760$$