Mixing
Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
TASK: Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
MY WORK: Let the number be $A=overline{x_n x_{n-1} x_{n-2} cdots x_1 x_0}$. Since $63|(x_n+x_{n-1}+cdots+x_1+x_0)$, we have that $x_n+x_{n-1}+cdots+x_0ge63cdots(*)$ and since $x_0,x_1,cdots,x_n$ are n+1 digits, we have that
$x_n+x_{n-1}+cdots+x_0le9+9+cdots+9=9(n+1)$ which then means that
$9(n+1)ge63Leftrightarrow n+1ge7$ i.e that the number $A$ has at least seven digits. If it has $7$ digits, all of them would have to be $9$ to satisfy the inequality $(*)$ which would mean that $A=9999999$. But then the condition $63|A$ would not be satisfied. So the number A doesn't have seven digits - it has at least eight digits.
However, I do not know where to go from here.
elementary-number-theory divisibility
asked Nov 20 '18 at 8:10
fic19292
1329
add a comment |
TASK: Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
MY WORK: Let the number be $A=overline{x_n x_{n-1} x_{n-2} cdots x_1 x_0}$. Since $63|(x_n+x_{n-1}+cdots+x_1+x_0)$, we have that $x_n+x_{n-1}+cdots+x_0ge63cdots(*)$ and since $x_0,x_1,cdots,x_n$ are n+1 digits, we have that
$x_n+x_{n-1}+cdots+x_0le9+9+cdots+9=9(n+1)$ which then means that
$9(n+1)ge63Leftrightarrow n+1ge7$ i.e that the number $A$ has at least seven digits. If it has $7$ digits, all of them would have to be $9$ to satisfy the inequality $(*)$ which would mean that $A=9999999$. But then the condition $63|A$ would not be satisfied. So the number A doesn't have seven digits - it has at least eight digits.
However, I do not know where to go from here.
elementary-number-theory divisibility
asked Nov 20 '18 at 8:10
fic19292
1329
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
3
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44
add a comment |
TASK: Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
MY WORK: Let the number be $A=overline{x_n x_{n-1} x_{n-2} cdots x_1 x_0}$. Since $63|(x_n+x_{n-1}+cdots+x_1+x_0)$, we have that $x_n+x_{n-1}+cdots+x_0ge63cdots(*)$ and since $x_0,x_1,cdots,x_n$ are n+1 digits, we have that
$x_n+x_{n-1}+cdots+x_0le9+9+cdots+9=9(n+1)$ which then means that
$9(n+1)ge63Leftrightarrow n+1ge7$ i.e that the number $A$ has at least seven digits. If it has $7$ digits, all of them would have to be $9$ to satisfy the inequality $(*)$ which would mean that $A=9999999$. But then the condition $63|A$ would not be satisfied. So the number A doesn't have seven digits - it has at least eight digits.
However, I do not know where to go from here.
elementary-number-theory divisibility
asked Nov 20 '18 at 8:10
fic19292
1329
TASK: Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
MY WORK: Let the number be $A=overline{x_n x_{n-1} x_{n-2} cdots x_1 x_0}$. Since $63|(x_n+x_{n-1}+cdots+x_1+x_0)$, we have that $x_n+x_{n-1}+cdots+x_0ge63cdots(*)$ and since $x_0,x_1,cdots,x_n$ are n+1 digits, we have that
$x_n+x_{n-1}+cdots+x_0le9+9+cdots+9=9(n+1)$ which then means that
$9(n+1)ge63Leftrightarrow n+1ge7$ i.e that the number $A$ has at least seven digits. If it has $7$ digits, all of them would have to be $9$ to satisfy the inequality $(*)$ which would mean that $A=9999999$. But then the condition $63|A$ would not be satisfied. So the number A doesn't have seven digits - it has at least eight digits.
However, I do not know where to go from here.
elementary-number-theory divisibility
elementary-number-theory divisibility
asked Nov 20 '18 at 8:10
fic19292
1329
asked Nov 20 '18 at 8:10
fic19292
1329
asked Nov 20 '18 at 8:10
fic19292
1329
asked Nov 20 '18 at 8:10
fic19292
1329
asked Nov 20 '18 at 8:10
fic19292
1329
1329
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
3
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44
add a comment |
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
3
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44
3
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
3
3
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44
add a comment |
4 Answers
4
active
oldest
votes
Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999equiv 5pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^kequiv 5mod 7$.
$10equiv 3$
$100equiv 30equiv 2$
$1000equiv 20equiv 6$
$10,000equiv 60equiv 4$
$100,000 equiv 40equiv 5$
So $19,999,999-100,000=19,899,999equiv 0pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0le k le 7$. For such a number to be divisible by $63$ we must have $10^k equiv 5 pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
add a comment |
(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)
Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19,999,999=5$ mod $7$; therefore we need to find a $kin[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19,899,999$ is the smallest number with the required properties.
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
add a comment |
The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).
Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
add a comment |
I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63.
Here a program I wrote in Python 3. To find this out by brute forcing :
for i in range(9999990, 19900000, 63):
sum_is = sum(int(d) for d in str(i))
if sum_is%63==0:
print(i)
Prints :
19899999
Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.
This can also be used to do the same with any number.
Just change the range and 63 as you want.
Hope this Helps!
[EDIT SUMMARY]
For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.
answered Nov 20 '18 at 12:41
FightWithCode
292
2
Instead of the mysterioussum_digits(i)you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 '18 at 16:01
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3006069%2ffind-the-smallest-positive-integer-divisible-by-63-such-that-the-sum-of-its-digi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999equiv 5pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^kequiv 5mod 7$.
$10equiv 3$
$100equiv 30equiv 2$
$1000equiv 20equiv 6$
$10,000equiv 60equiv 4$
$100,000 equiv 40equiv 5$
So $19,999,999-100,000=19,899,999equiv 0pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0le k le 7$. For such a number to be divisible by $63$ we must have $10^k equiv 5 pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
add a comment |
Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999equiv 5pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^kequiv 5mod 7$.
$10equiv 3$
$100equiv 30equiv 2$
$1000equiv 20equiv 6$
$10,000equiv 60equiv 4$
$100,000 equiv 40equiv 5$
So $19,999,999-100,000=19,899,999equiv 0pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0le k le 7$. For such a number to be divisible by $63$ we must have $10^k equiv 5 pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
add a comment |
Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999equiv 5pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^kequiv 5mod 7$.
$10equiv 3$
$100equiv 30equiv 2$
$1000equiv 20equiv 6$
$10,000equiv 60equiv 4$
$100,000 equiv 40equiv 5$
So $19,999,999-100,000=19,899,999equiv 0pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0le k le 7$. For such a number to be divisible by $63$ we must have $10^k equiv 5 pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999equiv 5pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^kequiv 5mod 7$.
$10equiv 3$
$100equiv 30equiv 2$
$1000equiv 20equiv 6$
$10,000equiv 60equiv 4$
$100,000 equiv 40equiv 5$
So $19,999,999-100,000=19,899,999equiv 0pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0le k le 7$. For such a number to be divisible by $63$ we must have $10^k equiv 5 pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
edited Nov 20 '18 at 22:48
Barry Cipra
59k653123
59k653123
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
answered Nov 20 '18 at 8:56
fleablood
68.2k22685
68.2k22685
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
add a comment |
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
1
1
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.)
– coffeemath
Nov 20 '18 at 9:01
1
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 '18 at 10:18
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^kequiv 5 mod 7$. The only such option for $0le k le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution.
– fleablood
Nov 20 '18 at 17:05
add a comment |
(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)
Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19,999,999=5$ mod $7$; therefore we need to find a $kin[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19,899,999$ is the smallest number with the required properties.
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
add a comment |
(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)
Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19,999,999=5$ mod $7$; therefore we need to find a $kin[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19,899,999$ is the smallest number with the required properties.
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
add a comment |
(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)
Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19,999,999=5$ mod $7$; therefore we need to find a $kin[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19,899,999$ is the smallest number with the required properties.
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)
Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19,999,999=5$ mod $7$; therefore we need to find a $kin[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19,899,999$ is the smallest number with the required properties.
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
edited Nov 20 '18 at 10:14
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
answered Nov 20 '18 at 9:34
Christian Blatter
172k7112326
172k7112326
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
add a comment |
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
2
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 '18 at 10:15
add a comment |
The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).
Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
add a comment |
The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).
Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
add a comment |
The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).
Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).
Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
answered Nov 20 '18 at 13:16
Barry Cipra
59k653123
59k653123
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
add a comment |
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k equiv 0 mod 7$ or $10^k equiv 5 mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works.
– fleablood
Nov 20 '18 at 17:28
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
@fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0le klt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$.
– Barry Cipra
Nov 20 '18 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 '18 at 23:08
add a comment |
I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63.
Here a program I wrote in Python 3. To find this out by brute forcing :
for i in range(9999990, 19900000, 63):
sum_is = sum(int(d) for d in str(i))
if sum_is%63==0:
print(i)
Prints :
19899999
Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.
This can also be used to do the same with any number.
Just change the range and 63 as you want.
Hope this Helps!
[EDIT SUMMARY]
For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.
answered Nov 20 '18 at 12:41
FightWithCode
292
2
Instead of the mysterioussum_digits(i)you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 '18 at 16:01
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
add a comment |
I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63.
Here a program I wrote in Python 3. To find this out by brute forcing :
for i in range(9999990, 19900000, 63):
sum_is = sum(int(d) for d in str(i))
if sum_is%63==0:
print(i)
Prints :
19899999
Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.
This can also be used to do the same with any number.
Just change the range and 63 as you want.
Hope this Helps!
[EDIT SUMMARY]
For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.
answered Nov 20 '18 at 12:41
FightWithCode
292
2
Instead of the mysterioussum_digits(i)you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 '18 at 16:01
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
add a comment |
I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63.
Here a program I wrote in Python 3. To find this out by brute forcing :
for i in range(9999990, 19900000, 63):
sum_is = sum(int(d) for d in str(i))
if sum_is%63==0:
print(i)
Prints :
19899999
Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.
This can also be used to do the same with any number.
Just change the range and 63 as you want.
Hope this Helps!
[EDIT SUMMARY]
For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.
answered Nov 20 '18 at 12:41
FightWithCode
292
I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63.
Here a program I wrote in Python 3. To find this out by brute forcing :
for i in range(9999990, 19900000, 63):
sum_is = sum(int(d) for d in str(i))
if sum_is%63==0:
print(i)
Prints :
19899999
Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.
This can also be used to do the same with any number.
Just change the range and 63 as you want.
Hope this Helps!
[EDIT SUMMARY]
For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.
answered Nov 20 '18 at 12:41
FightWithCode
292
edited Nov 21 '18 at 13:35
answered Nov 20 '18 at 12:41
FightWithCode
292
answered Nov 20 '18 at 12:41
FightWithCode
292
answered Nov 20 '18 at 12:41
FightWithCode
292
292
2
Instead of the mysterioussum_digits(i)you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 '18 at 16:01
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
add a comment |
2
Instead of the mysterioussum_digits(i)you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 '18 at 16:01
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
2
2
Instead of the mysterious
sum_digits(i) you could write python code: sum(int(d) for d in str(i))– Paul Evans
Nov 20 '18 at 16:01
Instead of the mysterious
sum_digits(i) you could write python code: sum(int(d) for d in str(i))– Paul Evans
Nov 20 '18 at 16:01
1
1
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0.
– Kyle Kanos
Nov 20 '18 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 '18 at 13:20
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%2f3006069%2ffind-the-smallest-positive-integer-divisible-by-63-such-that-the-sum-of-its-digi%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
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 '18 at 8:15
3
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 '18 at 8:44