determin the nunber of positive integers x <=9999999 and the sum of the digits in x equals 31?

Answer 1

512365

counted them (with a help of a program, of course).

Probably could be done analytically, too, but that way it seemed to be easier

Answer 2

x <=9999999 means that x is at most a 7 digit number.

Now, x cannot have 3 digits or less for if it did, then, say
x = 'abc' = 100a + 10 b + c,in base 10 and with a,b,c<=9.

So a+b+c <= 9 + 9 + 9 = 27 < 31 ( a contradiction! )

Hence, x must have between 4 to 7 digits. We thus compute each case seperately.

Euler considered the infinite product

(1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)...

If we expand this product we see that the coefficient of x^n is
precisely A(n), because it's the number of ways in which n can be
expressed as a sum of one number from each of the sets {0,1,2,...},
{0,2,4,...}, {0,3,6,...}, and so on. He remembered that, as Euclid
showed, the geometric series can be expressed formally as

1+ x + x^2 + x^3 + x^4 + ... = 1/(1-x)


and likewise the infinite sum 1 + x^2 + x^4 + ... can be expressed as
1/(1 - x^2), and so on. Thus we have

/ 1 \ / 1 \ / 1 \
( ----- )( ------- )( ------- )... = A(0) + A(1)x + A(2)x^2 + ...
\1 - x/ \1 - x^2/ \1 - x^3/

It's also worth noting that if we include just the first k factors
on the left hand side, then the coefficient of n is the number of
partitions of n into k or fewer parts. We will call this A_k(n).

Euler's generating function for the partitions of n is certainly
clever, and leads to many powerful techniques in combinatorics, but
it isn't the easiest way to compute A(n) or A_k(n). Some other ways
are discussed in Computing the Partitions of n, but here we will
just mention one very elementary methods. A table of A_k(n) can be
constructed quite simply based on the following two observations:

(1) The number of partitions into k or fewer parts is equal
to the number of partitions into exactly k parts plus the
number of partitions into k-1 or fewer parts.

(2) Given a partition of n into exactly k parts, we can
subtract 1 from each part, leaving a partition of n-k
in k or fewer parts. Thus there is a one-to-one
correspondence between the partitions of n into
exactly k parts and the partitions of n-k into k
or fewer parts.

Putting these two facts together, we have the simple recurrence
relation
A_k(n) = A_{k-1}(n) + A_k(n-k)

with which we can easily generate a table such as shown below.

k
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 2 2 2 2 2 2 2 2 2 2 2 2
3 1 2 3 3 3 3 3 3 3 3 3 3 3 3
4 1 3 4 5 5 5 5 5 5 5 5 5 5 5
5 1 3 5 6 7 7 7 7 7 7 7 7 7 7
6 1 4 7 9 10 11 11 11 11 11 11 11 11 11
7 1 4 8 11 13 14 15 15 15 15 15 15 15 15
8 1 5 10 15 18 20 21 22 22 22 22 22 22 22
9 1 5 12 18 23 26 28 29 30 30 30 30 30 30
10 1 6 14 23 30 35 38 40 41 42 42 42 42 42
11 1 6 16 27 37 44 49 52 54 55 56 56 56 56
12 1 7 19 34 47 58 65 70 73 75 76 77 77 77
13 1 7 21 39 57 71 82 89 94 97 99 100 101 101
14 1 8 24 47 70 90 105 116 123 128 131 133 134 135

The total number of partitions A(n) is obviously just A_n(n) from
this table, so we have the sequence of values for A(n) for n=1,2,...

n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
A(n) = 1 2 3 5 7 11 15 22 30 42 56 77 101 135 ...
complete it and you will find A(31)... after that have to do some permutations and excluding the cases where 'first digit = 0 ' which is included in computation of A(31)... etc.

Hope this helps...