My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
July 6th, 2015, 01: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?
coax is offline  
 
July 6th, 2015, 05: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.
Hoempa is offline  
July 6th, 2015, 07: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
voun is offline  
July 6th, 2015, 10: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
coax is offline  
July 6th, 2015, 03:17 PM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,637
Thanks: 2621

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 03:24 PM.
v8archie is online now  
July 7th, 2015, 05:05 AM   #6
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,637
Thanks: 2621

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.
v8archie is online now  
August 27th, 2015, 09: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
coax is offline  
August 28th, 2015, 04:57 AM   #8
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,637
Thanks: 2621

Math Focus: Mainly analysis and algebra
That document is over a thousand pages long!

How did your program efficiently filter the decimals containing zeros?
v8archie is online now  
August 29th, 2015, 04: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.
Hoempa is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 06:34 PM
Adding Vectors bilano99 Calculus 4 January 9th, 2013 03:57 PM
Multiplying 4 digits with 3 digits and vice versa CarpeDiem Elementary Math 7 July 13th, 2012 07:35 PM
Adding Vectors bilano99 Calculus 3 January 11th, 2012 05:21 PM
adding exponents andi7 Algebra 2 March 12th, 2009 08:59 PM





Copyright © 2019 My Math Forum. All rights reserved.