smallest number for given sum of digits
up vote
2
down vote
favorite
I am trying to find the smallest number if we are given the sum of its digits. Suppose that sum of digits is 9 then it should be 9 instead of 18,36,63 and similarly if sum of digits is 11 then desired answer is 29 not 92 or any other number bigger than 29.I tried to write sum of all numbers upto 53 and got this but i am not able to come up with a general formula.
from 1 to 9 it is just 9.FROM 10 to 18 it is 19,29,39,...... and for 19(1+9) it is 199 that is increase by 100.
from 19 to 27 it is 199,299,399,499.... and for 28 it is 1999 that is increase by 1000.
from 29 to 36 it is 29999,39999,49999,..... for 37 it is 19999 (increse by 10000).
for 38 to 45 it is it is 29999,39999,49999,........999999 and for 46 it is 199999 (increased by 100000)
number-theory
add a comment |
up vote
2
down vote
favorite
I am trying to find the smallest number if we are given the sum of its digits. Suppose that sum of digits is 9 then it should be 9 instead of 18,36,63 and similarly if sum of digits is 11 then desired answer is 29 not 92 or any other number bigger than 29.I tried to write sum of all numbers upto 53 and got this but i am not able to come up with a general formula.
from 1 to 9 it is just 9.FROM 10 to 18 it is 19,29,39,...... and for 19(1+9) it is 199 that is increase by 100.
from 19 to 27 it is 199,299,399,499.... and for 28 it is 1999 that is increase by 1000.
from 29 to 36 it is 29999,39999,49999,..... for 37 it is 19999 (increse by 10000).
for 38 to 45 it is it is 29999,39999,49999,........999999 and for 46 it is 199999 (increased by 100000)
number-theory
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am trying to find the smallest number if we are given the sum of its digits. Suppose that sum of digits is 9 then it should be 9 instead of 18,36,63 and similarly if sum of digits is 11 then desired answer is 29 not 92 or any other number bigger than 29.I tried to write sum of all numbers upto 53 and got this but i am not able to come up with a general formula.
from 1 to 9 it is just 9.FROM 10 to 18 it is 19,29,39,...... and for 19(1+9) it is 199 that is increase by 100.
from 19 to 27 it is 199,299,399,499.... and for 28 it is 1999 that is increase by 1000.
from 29 to 36 it is 29999,39999,49999,..... for 37 it is 19999 (increse by 10000).
for 38 to 45 it is it is 29999,39999,49999,........999999 and for 46 it is 199999 (increased by 100000)
number-theory
I am trying to find the smallest number if we are given the sum of its digits. Suppose that sum of digits is 9 then it should be 9 instead of 18,36,63 and similarly if sum of digits is 11 then desired answer is 29 not 92 or any other number bigger than 29.I tried to write sum of all numbers upto 53 and got this but i am not able to come up with a general formula.
from 1 to 9 it is just 9.FROM 10 to 18 it is 19,29,39,...... and for 19(1+9) it is 199 that is increase by 100.
from 19 to 27 it is 199,299,399,499.... and for 28 it is 1999 that is increase by 1000.
from 29 to 36 it is 29999,39999,49999,..... for 37 it is 19999 (increse by 10000).
for 38 to 45 it is it is 29999,39999,49999,........999999 and for 46 it is 199999 (increased by 100000)
number-theory
number-theory
edited Feb 17 '16 at 21:39
asked Feb 17 '16 at 21:35
satyajeet jha
331214
331214
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38
add a comment |
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38
add a comment |
3 Answers
3
active
oldest
votes
up vote
2
down vote
In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).
So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.
This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number
$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$
If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.
$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then
$$10^{btext{ div }9}-1.$$
add a comment |
up vote
0
down vote
Let's build the output number starting from the last (i.e. the lowest) digit.
As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.
If the input number is smaller than 9, just add it to the front of the output number.
i = 0
while(input > 9) {
// Set i-th digit of output to 9
output.set(i, 9)
input = input - 9
i = i+1
}
// Finally set the front digit of output to the rest of input
output.set(i, input)
In your example with 29, there would be one while-loop. The last digit of output
would be set to 9. Then, the front digit of output
would be set to 2.
Mathematically:
$$
text{output} = x99dots9
$$
where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.
add a comment |
up vote
-1
down vote
I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:
def bla(M,S):
n=(S+7)//9
sl=9*n -7
c=10**(n-1)
b=10**(M-1)
p=int((2+S-sl)*c -1)
return p+b
If you have any doubts please comment below.
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).
So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.
This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number
$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$
If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.
$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then
$$10^{btext{ div }9}-1.$$
add a comment |
up vote
2
down vote
In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).
So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.
This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number
$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$
If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.
$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then
$$10^{btext{ div }9}-1.$$
add a comment |
up vote
2
down vote
up vote
2
down vote
In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).
So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.
This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number
$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$
If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.
$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then
$$10^{btext{ div }9}-1.$$
In our so-called positional numeration system, the digits get a weight that increases from right to left, following the powers of ten (units, tens, hundreds, thousands...).
So to minimize the number you will allocate the budget in priority to the positions with the smallest weight.
This is why the solution is by putting as many $9$s to the right as you can, preceded by the remainder of the budget. There will be $btext{ div }9$ nines and the digit $bbmod9$, forming the number
$$(bbmod 9)10^{btext{ div }9}+10^{btext{ div }9}-1=(bbmod 9+1)10^{btext{ div }9}-1.$$
If on the opposite you want to maximize the sum, then you must forbid the digit $0$ (because you could insert them "for free"), and the solution is formed by a maximum of $9$s followed by the remainder, i.e.
$$10,(10^{btext{ div }9}-1)+bbmod9$$ unless $bbmod9=0$, then
$$10^{btext{ div }9}-1.$$
edited Aug 9 '16 at 10:06
answered Aug 9 '16 at 9:40
Yves Daoust
123k668219
123k668219
add a comment |
add a comment |
up vote
0
down vote
Let's build the output number starting from the last (i.e. the lowest) digit.
As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.
If the input number is smaller than 9, just add it to the front of the output number.
i = 0
while(input > 9) {
// Set i-th digit of output to 9
output.set(i, 9)
input = input - 9
i = i+1
}
// Finally set the front digit of output to the rest of input
output.set(i, input)
In your example with 29, there would be one while-loop. The last digit of output
would be set to 9. Then, the front digit of output
would be set to 2.
Mathematically:
$$
text{output} = x99dots9
$$
where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.
add a comment |
up vote
0
down vote
Let's build the output number starting from the last (i.e. the lowest) digit.
As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.
If the input number is smaller than 9, just add it to the front of the output number.
i = 0
while(input > 9) {
// Set i-th digit of output to 9
output.set(i, 9)
input = input - 9
i = i+1
}
// Finally set the front digit of output to the rest of input
output.set(i, input)
In your example with 29, there would be one while-loop. The last digit of output
would be set to 9. Then, the front digit of output
would be set to 2.
Mathematically:
$$
text{output} = x99dots9
$$
where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.
add a comment |
up vote
0
down vote
up vote
0
down vote
Let's build the output number starting from the last (i.e. the lowest) digit.
As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.
If the input number is smaller than 9, just add it to the front of the output number.
i = 0
while(input > 9) {
// Set i-th digit of output to 9
output.set(i, 9)
input = input - 9
i = i+1
}
// Finally set the front digit of output to the rest of input
output.set(i, input)
In your example with 29, there would be one while-loop. The last digit of output
would be set to 9. Then, the front digit of output
would be set to 2.
Mathematically:
$$
text{output} = x99dots9
$$
where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.
Let's build the output number starting from the last (i.e. the lowest) digit.
As long as the input number is bigger than 9, it is the best way to set the current digit of the output number to 9 than to any other value.
If you, hypothetically, set it to a value lower than 9, you would have to set another digit in the front to a higher value. So, your whole number would be higher.
If the input number is smaller than 9, just add it to the front of the output number.
i = 0
while(input > 9) {
// Set i-th digit of output to 9
output.set(i, 9)
input = input - 9
i = i+1
}
// Finally set the front digit of output to the rest of input
output.set(i, input)
In your example with 29, there would be one while-loop. The last digit of output
would be set to 9. Then, the front digit of output
would be set to 2.
Mathematically:
$$
text{output} = x99dots9
$$
where you have $log_9(text{input})$ $9$'s behind the $x$ and $x = text{input} - log_9(text{output})$.
answered Aug 9 '16 at 9:25
JavAlex
1
1
add a comment |
add a comment |
up vote
-1
down vote
I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:
def bla(M,S):
n=(S+7)//9
sl=9*n -7
c=10**(n-1)
b=10**(M-1)
p=int((2+S-sl)*c -1)
return p+b
If you have any doubts please comment below.
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
add a comment |
up vote
-1
down vote
I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:
def bla(M,S):
n=(S+7)//9
sl=9*n -7
c=10**(n-1)
b=10**(M-1)
p=int((2+S-sl)*c -1)
return p+b
If you have any doubts please comment below.
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
add a comment |
up vote
-1
down vote
up vote
-1
down vote
I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:
def bla(M,S):
n=(S+7)//9
sl=9*n -7
c=10**(n-1)
b=10**(M-1)
p=int((2+S-sl)*c -1)
return p+b
If you have any doubts please comment below.
I have found a general formula to find the smallest number whose digits sum up to S and has M digits. Here is a python implementation of it:
def bla(M,S):
n=(S+7)//9
sl=9*n -7
c=10**(n-1)
b=10**(M-1)
p=int((2+S-sl)*c -1)
return p+b
If you have any doubts please comment below.
edited Nov 19 at 15:01
answered Nov 19 at 14:55
Albharath
12
12
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
add a comment |
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
If you feel it is wrong then do comment with your reason.
– Albharath
Nov 19 at 15:03
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1660540%2fsmallest-number-for-given-sum-of-digits%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Your title says "sum of sum of digits" and your question says "sum of digits". They are not the same thing!
– TonyK
Feb 17 '16 at 21:38
@Tonyk i corrected the title but don't downvote it.
– satyajeet jha
Feb 17 '16 at 21:40
Write $n=9q+r$ where $0leq r<9$. Then the number you seek is $(r+1)10^{q}-1$.
– Thomas Andrews
Feb 17 '16 at 21:40
Isn't the solution merely filling as many of the least-significant digits as possible with $9$s and then putting the remaining number in the most-significant digit? In short: pack the least-significant digits with values as high as possible.
– David G. Stork
Feb 17 '16 at 21:52
@satya: Isn't this the same question as math.stackexchange.com/q/1661620/117283? (Not to mention stackoverflow.com/q/35487923/270986 .)
– Mark Dickinson
Feb 19 '16 at 20:38