111 is divisible by 3. 111111111 is divisible by 9. For which N is the number composed of N 1s divisible by N?

divisible.hs

-- https://twitter.com/jamestanton/status/438258919413387264
-- "111 is divisible by 3. 111111111 is divisible by 9. 
-- For which N is the number composed of N 1s divisible by N?"


-- Version 1: very slow due to the construction of the numerator
numerator1 x = sum $ map (\y -> 10^y) [0..(x-1)]
test1 x = numerator1 x `rem` x == 0


-- Version 2: Version 1 combined into a single function
test2 x = (sum $ map (\y -> 10^y) [0..(x-1)]) `rem` x == 0


-- Version 3: fastest so far
numerator3 x = read (replicate x '1') :: Integer
test3 = numerator3 x `rem` (toInteger x) == 0


-- answer = filter test3 [1..60000]
-- answer = [1,3,9,27,81,111,243,333,729,999,2187,2997,4107,6561,8991,12321,13203,19683,20439,26973,36963,39609,59049]


-- Note: Many of the answers are simply 3 times a smaller answer.
--       There is a small subset of the answers that represent the first of
--       their series, where they are not simply a multiple of a smaller answer.
--       I'm denoting them as "origins".

-- origins = [1,111,4107,13203,20439] 

-- import qualified Data.List
-- Data.List.sort [y * 3 ^ x | x <- [0..20], y <- origins]