Question: Arrange the digits 1,2,3,4,5,6,7,8,9,0 to make a ten-digit Number that satisfies all of the divisibility rules for 2,3,4,5,6,8,9,10,&11. BONUS: make the number also divisible by 7
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Should I add no-computer tag? $\endgroup$– Omega KryptonOct 27, 2018 at 2:33
-
$\begingroup$ Why did you have to take down the post? By posting on the Stack Exchange network, you've granted a non-revocable right for SE to distribute that content (under the CC BY-SA 3.0 license). By SE policy, deletions like this will be reverted. $\endgroup$– GlorfindelOct 28, 2018 at 18:56
-
$\begingroup$ @Glorfindel thanks for informing me. I am slowing learning how this all works $\endgroup$– DeNelOct 28, 2018 at 20:17
-
2$\begingroup$ What does "satisfies all of the divisibility rules" mean? That the number needs to actually be divisible by all those divisors? Or just that it needs to follow some well-known necessary (but not necessarily sufficient) rules to be divisible by them? $\endgroup$– R.. GitHub STOP HELPING ICEOct 28, 2018 at 21:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Alright. First of all,
3 and 9 are automatically okay. The sum of the digits from 0 to 9 is 45, which is divisible by 3 and 9, so any number made out of these ten will be divisible by 3 and 9.
Now,
the last digit MUST be 0, to satisfy 2 and 5 and 10. This also satisfies 6 as well, because it's now divisible by 2 and 3.
Now, let's look at the second-last and third-last digits.
The second-last digit must be divisible by 4, because the number must be divisible by 4 and 8. The third to last digit must also be even, to make it divisible by 8.
Now
all we have is 11 (and 7 for extra credit). To satisfy this, we have to make it so that when placing alternating signs between the digits so the result is a multiple of 11. After a bit of trial and error, I came up with 4123975680, which works for everything. It's not divisible by 7, though. I'll keep looking.
As Martin Schulz pointed out in the comments (now deleted),
9165784320 is divisible by 7
answered Oct 26, 2018 at 23:56
-
$\begingroup$ I have 1385679240 & 7165932840 neither divisible by 7 $\endgroup$– DeNelOct 27, 2018 at 0:10
-
$\begingroup$ My theory is that the number has to end in 240 or 640 or 840 but your answer totally disproved that. $\endgroup$– DeNelOct 27, 2018 at 0:11
-
8$\begingroup$ "The second-last digit must be divisible by 4, because the number must be divisible by 4 and 8." This is not true. For a counterexample, 120 is divisible by 4 and 8, but its second-last digit is not divisible by 4. $\endgroup$– eliasOct 27, 2018 at 2:08
-
2$\begingroup$ the correct wording would be the last 2 digits must be divisible by 4 and the last 3 digits must be divisible by 8. In fact we just need to check for divisibility by 8, since that implies divisibility by 4 as well $\endgroup$– phuclvOct 27, 2018 at 6:24
$\begingroup$
$\endgroup$
5
This is a good problem to attack by computer:
It turns out that there are 7344 solutions, including 1056 to the bonus.
So I thought, how far can we go?
And it just happens that 2438195760, 3785942160, 4753869120 and 4876391520 are exactly those permutations of
0123456789divisible by each of 1 through 18, and none of them are divisible by 19.
Code used (Python 3 IDLE):
>>> import itertools
>>> normal=[]
>>> bonus=[]
>>> extra=[]
>>> for i in itertools.permutations('123456789'):
... n=int(''.join(i+('0',)))
... if 0==n%8==n%9==n%11:
... normal.append(n)
... if 0==n%7:
... bonus.append(n)
... if 0==n%13==n%16==n%17:
... extra.append(n)
...
>>> len(normal)
7344
>>> len(bonus)
1056
>>> extra
[2438195760, 3785942160, 4753869120, 4876391520]
>>> [i%19 for i in extra]
[12, 13, 17, 5]
-
1$\begingroup$ Oh my goodness, that is amazing. I’m totally Computer illiterate. you have to totally teach me how to do this problem on a computer. $\endgroup$– DeNelOct 27, 2018 at 0:38
-
2$\begingroup$ @DeNel I used Python 3, I'll attach some code that I used in a few moments. $\endgroup$ Oct 27, 2018 at 2:04
-
$\begingroup$ @DeNel, the general idea is to construct every permutation of the ten digits and then check the divisors of each of those numbers. It’s a pretty simple program to write (for one who knows how, of course), and a computer can check all of the combinations very quickly, even though there are a lot of them. $\endgroup$– prlOct 28, 2018 at 10:02
-
$\begingroup$ boboquack, As @ExcitedRaichu pointed out, there’s no need to check divisibility by 9, since it is guaranteed by the choice of digits. $\endgroup$– prlOct 28, 2018 at 10:04
-
$\begingroup$ @prl Lucky this isn’t code-golf then! It’s not much of a time cost for me anyway, the program runs in about 0.3 seconds for me. $\endgroup$ Oct 28, 2018 at 20:39