import Control.Monad
import Math.NumberTheory.Logarithms (integerLog2)

simulate :: Integer -> Integer
simulate n = head (go [1..n])
    where
        go [x] = [x]
        go (x1:x2:xs) = go (xs ++ [x1])


analysis :: IO ()
analysis = do
    forM_ [1..100] $ \n -> do
        print (n, simulate n)
    
    {-
    Output is:
        (1,1)
        (2,1)
        (3,3)
        (4,1)
        (5,3)
        (6,5)
        (7,7)
        (8,1)
        (9,3)
        (10,5)
        (11,7)
        (12,9)
        (13,11)
        (14,13)
        (15,15)
        (16,1)
        ...
    
    Notice that the second element in the tuple
    increases exclusively by `2`. However, when
    the elements are equal (input == output),
    the sequence restarts at `1`.

    The numbers that "cause" the sequence to restart are:
    1 3 7 15 31 63 127 ...

    These numbers can be described by the formula:
                    M(n) = 2 ^ n - 1
    Otherwise known as "Mersenne numbers". [1]

    By making use of these facts, we can arrive at a
    more efficient algorithm:

    Given the size of the circle `n`, the solution is:
        2 * (n - 'nearest Mersenne number') - 1

    It is possible to find the nearest Mersenne number
    in constant time with an Integer base-2 logarithm function.
    Thus, the resulting algorithm is also constant-time.

    We make use of a packaged solution found in the
    hackage package 'integer-logarithms'.
    
    [1] http://mathworld.wolfram.com/MersenneNumber.html
    -}

nearestMersenne :: Integer -> Integer
nearestMersenne n = 2 ^ (toInteger $ integerLog2 n) - 1

solve :: Integer -> Integer
solve n = 2 * (n - nearestMersenne n) - 1

main :: IO ()
main = do
    forM_ [1..100] $ \n -> do
        print (n, solve n)