Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.
up vote
4
down vote
favorite
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
add a comment |
up vote
4
down vote
favorite
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
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 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 at 8:44
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
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
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 at 8:10
fic19292
1329
1329
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 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 at 8:44
add a comment |
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 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 at 8:44
3
3
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 at 8:15
So check numbers like 18999999 and 19899999 and 19989999 and so on.
– Gerry Myerson
Nov 20 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 at 8:44
You get divisibility by $9$ for free so you only need be concerned about checking for $7$
– Mark Bennet
Nov 20 at 8:44
add a comment |
4 Answers
4
active
oldest
votes
up vote
8
down vote
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.
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 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 at 17:05
add a comment |
up vote
4
down vote
(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.
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
add a comment |
up vote
3
down vote
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$.
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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 at 23:08
add a comment |
up vote
2
down vote
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.
2
Instead of the mysterioussum_digits(i)
you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 at 13:20
add a comment |
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
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.
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 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 at 17:05
add a comment |
up vote
8
down vote
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.
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 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 at 17:05
add a comment |
up vote
8
down vote
up vote
8
down vote
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.
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 at 22:48
Barry Cipra
58.5k652122
58.5k652122
answered Nov 20 at 8:56
fleablood
66.9k22684
66.9k22684
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 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 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 at 9:01
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 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 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 at 9:01
1
1
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 at 10:18
Sorry @coffeemath , I had a typo.
– Akash Roy
Nov 20 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 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 at 17:05
add a comment |
up vote
4
down vote
(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.
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
add a comment |
up vote
4
down vote
(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.
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
add a comment |
up vote
4
down vote
up vote
4
down vote
(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.
(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.
edited Nov 20 at 10:14
answered Nov 20 at 9:34
Christian Blatter
171k7111325
171k7111325
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
add a comment |
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
2
2
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
@coffeemath: Sorry for the typo. Thank you for reporting it.
– Christian Blatter
Nov 20 at 10:15
add a comment |
up vote
3
down vote
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$.
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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 at 23:08
add a comment |
up vote
3
down vote
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$.
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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 at 23:08
add a comment |
up vote
3
down vote
up vote
3
down vote
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$.
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 at 13:16
Barry Cipra
58.5k652122
58.5k652122
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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 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 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 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 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 at 22:46
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 at 23:08
Yeah, I guess I worded it incorrectly. $10equiv 3$ is a primitive root is what I meant.
– fleablood
Nov 20 at 23:08
add a comment |
up vote
2
down vote
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.
2
Instead of the mysterioussum_digits(i)
you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 at 13:20
add a comment |
up vote
2
down vote
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.
2
Instead of the mysterioussum_digits(i)
you could write python code:sum(int(d) for d in str(i))
– Paul Evans
Nov 20 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 at 13:20
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
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.
edited Nov 21 at 13:35
answered Nov 20 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 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 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 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 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 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 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 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 at 19:47
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 at 13:20
Yes! That's more optimized. Thanx for advice.
– FightWithCode
Nov 21 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 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 at 8:44