3
$\begingroup$

This question already has an answer here:

I have a number.

Each digit doesn't appear more than once and 0 not at all.

It is 9 digits long and can be divided by 9.
If I remove the last digit it can be divided by 8.
If I remove the last digit of the 8 digit number, it can be divided by 7.
This can be repeated all the way down to 1.

What is the highest number this works for?

(Note when I say 'can be divided' I mean into a whole number)

$\endgroup$

marked as duplicate by f'', Reti43, ffao, AJL, bleh Apr 23 '16 at 18:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Can a number be more than once in the big digit number? How do we treat leading 0s? Would you say that 0 is divided by 9, for example? $\endgroup$ – Reti43 Apr 23 '16 at 10:53
  • $\begingroup$ @Reti43 there are no 0s $\endgroup$ – Beastly Gerbil Apr 23 '16 at 10:55
  • $\begingroup$ Oh, I didn't see those, this wasn't a purposeful duplicate $\endgroup$ – Beastly Gerbil Apr 25 '16 at 17:24
3
$\begingroup$

The answer is

381654729

Some analysis.

Since there are no 0s and each number appears once, the big number is some permutation of 123456789 and thus divisible by 9.

We require numbers in the even positions to be even, so that ab is divided by 2, abcd is divided by 4, etc. Similarly, the fifth number must be 5, since it can't be 0.

So we can simply permute the numbers (1, 3, 7, 9) for the first, third, seventh and ninth positions and fill in the even numbers appropriately. We require the 3rd and 4th numbers to be divisible by 4 and the 7th and 8th by 8 (typical times 8 table since the 6th digit is also even). Finally, we require the first three and the first six numbers to be divisible by 3, so that they can be divisible by 3 and 6 respectively.

The process is as follows:
- Generate a (1, 3, 7, 9) permutation (24 in total).
- Find the only even number for the 8th position that makes the number divisible by 8.
- This leaves only one number for the divisible by 4 case.*
- Check whether the first two odd numbers, plus all the evens except from the one at the eight position, plus 5 all add up to a number divisible by 3.
- The remaining two even numbers have a difference of 4, so at most only one of them can fill in the second position to make the first three digits divisible by 3.**
- If we have reached this far, check for divisibility by 7.

(1, 3, 7, 9)
72 is divisible by 8 and 36 divisible by 4. The first 6 numbers are divisible by 3. From 4 and 8 remaining only 183 is divisible by 3. However, 1836587 = 4 (mod 7).

(1, 3, 9, 7)
96 is divisible by 8 and 32 divisible by 4. However, the first 6 numbers add up to 23. Next! And so on...

*The trailing digit for divisibility by 4 has a periodicity of 20. For a two-digit number, cd, for each c there are two digits for d that make it divisible by 4. However, since the number for divisible by 8, gh, g0 - c0 = some multiple of 20 since both c and g are odd. Therefore, from the two even digits in 0-9 for d that make cd divisible by 4, one of them is required for h in gh.

**From [*] it's obvious that d and h differ by 4. No matter which two numbers we take out of (2, 4, 6, 8) which differ by 4, the remaining two will also differ by 4.

$\endgroup$
  • $\begingroup$ Thats the answer I have. Well done! Guess I should have worded question better $\endgroup$ – Beastly Gerbil Apr 23 '16 at 10:59

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