Number Theory Number Theory Math Forum

 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/(1-x-x^2-...-x^9) which is 129920
 July 6th, 2015, 11:51 AM #4 Newbie   Joined: Jul 2009 From: England Posts: 25 Thanks: 0 I made the answer 64960 https://www.scribd.com/doc/270664442...t-Add-Up-to-17
 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 $(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. 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 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.
 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...t-Add-Up-to-17
 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.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post DaveJames Algebra 5 March 26th, 2014 07:34 PM bilano99 Calculus 4 January 9th, 2013 04:57 PM CarpeDiem Elementary Math 7 July 13th, 2012 08:35 PM bilano99 Calculus 3 January 11th, 2012 06:21 PM andi7 Algebra 2 March 12th, 2009 09:59 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top