Puzzles/DivN
< Puzzles
Jump to navigation
Jump to search
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.