# Puzzles/Div9

Find a 9-digit number , containing all the digits 1,2,...,9, such that divides for each .

## Solution

Since 5 divides , must be 5.
Similarly must be even for even
and by elimination , , and
must be the remaining digits 1, 3, 7 and 9 in some order.
Candidate solutions thus have the form `oeoe5eoeo` where `o`=odd, `e`=even.

From this point it's not too difficult to reduce the candidates to a unique solution; here is how one might use J:

oe=: (i.24)&A.&> 1 3 7 9; 2 4 6 8 NB. permuted odds and evens a0=: 5 ,. ,/ ,"1// oe NB. proto-candidates (5ooooeeee) a =: 1 5 2 6 0 7 3 8 4 {"1 a0 NB. candidates (oeoe5eoeo) ok=: 0 = (# | 10&#.)\"1 a NB. 0 remainders in all prefixes (*./"1 ok) # a NB. solution 3 8 1 6 5 4 7 2 9

Still using the same` oeoe5eoeo `idea, but building the solution one
column at time:

nd =: 0 1 0 1 2 1 0 1 0 { 1 3 7 9 ; 2 4 6 8 ; ,5 ext =: [: ,/ ] ,."2 0 {:@$ {:: nd"_ ok =: *./@~:"1 *. 0: = {:@$ | 10&#. extend=: (ok # ]) @ ext extend^:9 i.1 0 3 8 1 6 5 4 7 2 9

Initially, there is 1 solution of 0
columns.` i{::nd `are the digits to use when the current solution has` i `columns,
and` ext `appends each of these digits to each row of the current
solution.` ok `indicates the valid rows -- unique digits and divisible
by` i+1 `.

The method keeps the number of rows small, and therefore might be the method to use if one were to solve the problem by hand (with only pencil and paper).

3 : '# extend^:y i.1 0'"0 i.10 1 4 16 20 30 30 20 8 1 1

Contributed by Roger Hui and Ewart Shaw.