Nice++.

These are these methods I was taught by dear ol' "Spud" Murphy (otherwise known as Dr.T.N Murphy--we never did find out what the T.N. stood for:). I remember him ruing the day when he had to tell us that we could use calculators in our exams provided that they didn't have memories.

I borrowed my brother-in-law's Sinclair Scientific (which he wore on his belt to meetings like people did with mobile phones in the late '80s:). I took it into the exam and placed it on the desk in front of me, but then used log tables because I had never got to grips with the reverse polish notation!

Spud was right about calculators.

there is a rule for division by seven, but it's no use here ...

Alternatively, convert to base 8 and add the digits. :)

More useful can be to take advantage of the fact that 1001 is 7 * 11 * 13 - you can check for divisibility of all three of those in one step by adding/subtracting alternating groups of 3 digits (counting from the right).

Eg:

  testing 123456789
  split into groups: 789, 456, 123
  add/subtract alternately: 789 - 456 + 123 = 456
  factorise what's left: 456 = 2^3 * 3 * 19
  so 123456789 is not divisible by 7 or 11 or 13
[download]

If the resulting number is difficult to factorise in your head, you can always add/subtract multiples of one of those primes until you get to something that obviously is/isn't a multiple of that prime:

  456 = 400 + 56 (so it isn't divisible by 7)
  456 = 390 + 66 (so it isn't divisible by 11 or 13)
[download]

Hugo

Let's see. The fifth number has to be divisible by 5, so that digit is 0 or 5, but we don't have a 0 so that is 5. Digits in position 2, 4, 6, and 8 must be even, so that uses up 4 even digits - we only have 4 so all must be used there. Therefore the odd digits must be odd.

Oh, but we can go further still, so far we know that at position 4 we have (odd)(even)(odd)(even) and we need it divisible by 4, that will only happen if the 4'th digit is divisible by 2 but not 4. A similar thing happens at position 8. We only have 2 such digits, 2 and 6. Therefore 2 and 6 appear at positions 4 and 8. And 4 and 8 appear at positions 2 and 6.

We are now in a position to do exhaustive search. The pattern is that we want a permutation where the digits happen to fall into the sequence

1. 1, 3, 7, 9
2. 4, 8
3. 1, 3, 7, 9
4. 2, 6
5. 5
6. 4, 8
7. 1, 3, 7, 9
8. 2, 6
9. 1, 3, 7, 9

143 x
14725836 x
1472589 x
147658 x
149 x
183254 x
1836547 x
1836549 x
187 x
189254 x
1896547 x
1896549 x
341 x
347 x
349 x
381254 x
381654729 <--- Yes!
3816549 x
387254 x
3876541 x
3876549 x
389 x
7412583 x
7412589 x
741658 x
743 x
749 x
781 x
783254 x
7836541 x
78365492 x
789254 x
7896541 x
7896543 x
941 x
943 x
947 x
981254 x
9816543 x
9816547 x
983 x
987254 x
9876541 x
9876543 x
[download]

Incidentally that there would be about one answer should not surprise. After all we have 9! permutations. But odds are that all of them get through the first check, half the second, a third the third, a quarter the fourth, etc. So we'd expect about 1/9! of the permutations to get through. Which (hmmm...) works out an estimate of 1 right answer...