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 RogerHui.