{- A090822
Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such
that the word a(1)a(2)...a(n-1) is of the form xy^k for words x and y
(where y has positive length), i.e. the maximal number of repeating
blocks at the end of the sequence so far. -}

module Main where

import Data.List
import System.IO
import System.Environment

-- a 0     = 1
-- a (n+1) = largest k such that a(0..n) has a suffix
--           of the form w^k (k concatenations of the same word)

a090822 :: Int -> Int
a090822 0 = 1
a090822 n = reps 1 1 $ reverse $ take n a090822_list

a090822_list :: [Int]
a090822_list = map a090822 [0..]

-- find repetitions of length n in a prefix of xs, where m is the current maximum
-- terminate early if n * m > length xs
reps :: Int -> Int -> [Int] -> Int
reps n m xs = loop n m where
  l = length xs
  loop n m
    | n * (m+1) > l = m
    | otherwise     = let (h,t) = splitAt n xs
                      in  loop (n+1) (max m (1 + numPrefs h t))

numPrefs :: [Int] -> [Int] -> Int
numPrefs w xs = loop w xs where
  loop [] xs         = 1 + loop w xs
  loop w []          = 0
  loop (y:ys) (x:xs) = if x==y then loop ys xs else 0

-- | Main program
main :: IO ()
main = do
  [arg] <- getArgs
  hSetBuffering stdout NoBuffering
  print $ take (read arg) a090822_list

-- Andreas Abel and Andres Loeh, May 12 2012