9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Should I add no-computer tag? $\endgroup$ – Omega Krypton Oct 27 '18 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$ – Glorfindel Oct 28 '18 at 18:56
  • $\begingroup$ @Glorfindel thanks for informing me. I am slowing learning how this all works $\endgroup$ – DeNel Oct 28 '18 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.. Oct 28 '18 at 21:27
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I have 1385679240 & 7165932840 neither divisible by 7 $\endgroup$ – DeNel Oct 27 '18 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$ – DeNel Oct 27 '18 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$ – elias Oct 27 '18 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$ – phuclv Oct 27 '18 at 6:24
21
$\begingroup$

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 0123456789 divisible 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]

$\endgroup$
  • 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$ – DeNel Oct 27 '18 at 0:38
  • 2
    $\begingroup$ @DeNel I used Python 3, I'll attach some code that I used in a few moments. $\endgroup$ – boboquack Oct 27 '18 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$ – prl Oct 28 '18 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$ – prl Oct 28 '18 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$ – boboquack Oct 28 '18 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.