Puzzles/DivN

From http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/August2005.html

For k as large as possible, produce a k-digit integer m such that for each n=1,2,...,k , the integer given by the first n digits of m is divisible by n .

An example is k=4 , m=7084 , because 7 is divisible by 1; 70 is divisible by 2; 708 is divisible by 3; and 7084 is divisible by 4.

Solution

The divisibility requirement implies that when the number of digits is k , the last digit of m must be restricted according to 10|k as indicated in the following table:

0	0
1	0 1 2 3 4 5 6 7 8 9
2	0 2 4 6 8
3	0 1 2 3 4 5 6 7 8 9
4	0 2 4 6 8
5	0 5
6	0 2 4 6 8
7	0 1 2 3 4 5 6 7 8 9
8	0 2 4 6 8
9	0 1 2 3 4 5 6 7 8 9

Therefore, at each step, extend the candidate numbers by the appropriate list of digits. When k=1 , the solutions are 1+i.9x . Thus:

D  =: 0 1 2 1 2 3 2 1 2 1 { (,0); (i.10); 0 2 4 6 8; 0 5
ext=: 3 : 'c #~ 0=k|c=. , (10*y) +/ D {::~ 10|k=. 1+#":{.y'

   ] t=: 1+i.9x
1 2 3 4 5 6 7 8 9

   ext t
10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 ...

   ext^:2 t
102 105 108 120 123 126 129 141 144 147 162 165 168 180 183 186 189 201 ...

   3 : '# ext^:y 1+i.9x'"0 i.3 10
   9   45  150  375 750 1200 1713 2227 2492 2492
2225 2041 1575 1132 770  571  335  180   90   44
  18   12    6    3   1    0    0    0    0    0

   ext^:24 t
3608528850368400786036725

---

Contributed by Roger Hui.