Sequence.hs

-- | Find the triangle number T(n)
triangle :: Integer -> Integer
triangle n = (n * (1 + n)) `div` 2

-- | Find the greatest k where T(k) <= n
invTriangle :: Integer -> Integer
invTriangle n = (intSqrt (1 + 8*n) - 1) `div` 2

-- | Find the greatest k where k^2 <= n
intSqrt :: Integer -> Integer
intSqrt = floor . (sqrt :: Double -> Double) . fromInteger

-- | The sequence [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ..]
theSequence :: Integer -> Integer
theSequence k = k - triangle (invTriangle k)

-- | Find a subsequence [n, n, n, ..] i.e. for all k, n_k = n
subSequence :: Integer -> Integer -> Integer
subSequence n = \k -> theSequence (triangle (n + k) + n)