July 6th, 2015, 02:35 AM  #1 
Newbie Joined: Jul 2009 From: England Posts: 25 Thanks: 0  Adding Digits
How many integers without zeros, in base 10, have digits that add up to 17?

July 6th, 2015, 06:28 AM  #2 
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 361 
For positive integers, the coëfficiënt of x^17 in (x^1 + x^2 + x^3 + ... + x^9)^17. For integers, twice that.

July 6th, 2015, 08:28 AM  #3 
Newbie Joined: Jun 2015 From: Sweden, Kalmar Posts: 7 Thanks: 1 
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/(1xx^2...x^9) which is 129920 
July 6th, 2015, 11:51 AM  #4 
Newbie Joined: Jul 2009 From: England Posts: 25 Thanks: 0  
July 6th, 2015, 04:17 PM  #5 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra 
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 $(n1)$ 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 n1$ 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 179=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 n1}$ numbers. This works for $n \in \{1,2,\ldots,8\}$ since any number with 9 or more nonzero 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 n1}  \sum_{n = 1}^{8} n{7 \choose n1}$$ 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. Last edited by v8archie; July 6th, 2015 at 04:24 PM. 
July 7th, 2015, 06:05 AM  #6 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra 
Further to the above, we can write $$\begin{aligned} 2\sum_{n = 1}^8 n{7 \choose n1} &= 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 7n} \\ &= \sum_{n = 0}^7 (n+1){7 \choose n} + \sum_{n = 0}^7 (7n+1){7 \choose n} \\ &= 9\sum_{n = 0}^7 {7 \choose n} \\ &= 9 \cdot 2^7 \\ \sum_{n = 1}^8 n{7 \choose n1} &= 9 \cdot 2^6 \end{aligned}$$ It is easy to generalise this result for digit sums small enough that the second term doesn't doublecount numbers. 
August 27th, 2015, 10:39 PM  #7 
Newbie Joined: Jul 2009 From: England Posts: 25 Thanks: 0 
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...tAddUpto17 
August 28th, 2015, 05:57 AM  #8 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra 
That document is over a thousand pages long! How did your program efficiently filter the decimals containing zeros? 
August 29th, 2015, 05:55 AM  #9 
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 361 
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. 

Tags 
adding, digits 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Adding Sin waves  DaveJames  Algebra  5  March 26th, 2014 07:34 PM 
Adding Vectors  bilano99  Calculus  4  January 9th, 2013 04:57 PM 
Multiplying 4 digits with 3 digits and vice versa  CarpeDiem  Elementary Math  7  July 13th, 2012 08:35 PM 
Adding Vectors  bilano99  Calculus  3  January 11th, 2012 06:21 PM 
adding exponents  andi7  Algebra  2  March 12th, 2009 09:59 PM 