![]() |
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 | |
![]() |
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. |
![]() |
![]() |
|
Tags |
adding, digits |
Thread Tools | |
Display Modes | |
|
![]() | ||||
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 |