coax

How many integers without zeros, in base 10, have digits that add up to 17?

Hoempa

For positive integers, the coëfficiënt of x^17 in (x^1 + x^2 + x^3 + ... + x^9)^17. For integers, twice that.

voun

I think the correct answer is the coefficient in front of x^17 in 2*((x^1+x^2+...+x^9)^0+(x^1+x^2+...+x^9)^1+(x^1+x^ 2+...+x^9)^2+...) =
2/(1-x-x^2-...-x^9) which is 129920

coax

I made the answer 64960

https://www.scribd.com/doc/270664442...t-Add-Up-to-17

v8archie

I agree: 64960

First, expand the set of digits to include "10", "11", ..., "17".

Now count how many numbers of length $n$ in this expanded digit set have a digit sum of 17. To do this, lay out 17 stones in a line and add $(n-1)$ dividers between them so that no two dividers are adjacent (as that would represent a "zero" digit). We read off the digits by counting the number of stones between dividers. There are $16 \choose n-1$ ways to create numbers like this, and it works for $n \in \{1,2,\ldots,17\}$.

Now we count how many of those numbers contain "digits" greater than 9. Note that each can contain at most one such "digit", otherwise the digit sum would be at least 20, not 17 as stipulated. To count these, we create numbers with a digit sum of 17-9=8, and then add 9 to each digit in turn. The same process for generating the numbers with a digit sum of 8 works, so our total count is $n{7 \choose n-1}$ numbers. This works for $n \in \{1,2,\ldots,8\}$ since any number with 9 or more non-zero digits and a digit sum of 17 has no more than 8 digits maximum digit value of 9.

Thus our total, $T$, is given by$$T = \sum_{n = 1}^{17} {16 \choose n-1} - \sum_{n = 1}^{8} n{7 \choose n-1}$$ The first term is simply the sum of the entries in the 16th row of Pascal's triangle, and is thus equal to $2^{16}$. The second term is worked out by hand - I got 576, giving the total I gave above.

v8archie

Further to the above, we can write
$$\begin{aligned}
2\sum_{n = 1}^8 n{7 \choose n-1} &= 2\sum_{n = 0}^7 (n+1){7 \choose n} = \sum_{n = 0}^7 (n+1){7 \choose n} + \sum_{n = 0}^7 (n+1){7 \choose n} \\
&= \sum_{n = 0}^7 (n+1){7 \choose n} + \sum_{n = 0}^7 (n+1){7 \choose 7-n} \\
&= \sum_{n = 0}^7 (n+1){7 \choose n} + \sum_{n = 0}^7 (7-n+1){7 \choose n} \\
&= 9\sum_{n = 0}^7 {7 \choose n} \\
&= 9 \cdot 2^7 \\
\sum_{n = 1}^8 n{7 \choose n-1} &= 9 \cdot 2^6
\end{aligned}$$
It is easy to generalise this result for digit sums small enough that the second term doesn't double-count numbers.

coax

How many positive integers have non zero digits that add up to 17 in base 10?

There are many ways to solve the above problem. In the paper below I have used two methods.

1, By using the Fibonacci numbers in base 3 we can see as we go up through the bases to base 10 how these numbers relate to this problem.

2, I have written a program to count the number of digits that add up to 17.

https://www.scribd.com/doc/274558500...t-Add-Up-to-17

v8archie

That document is over a thousand pages long!

How did your program efficiently filter the decimals containing zeros?

Hoempa

In his loops, digits are from 1 to some upperbound, depending on the amount of digits of the number being checked.

One could also look at the partitions of 17; pick those whose highest term is less then ten. Then for all those partitions, get all permutations of the terms (=digits) and sort if you like.