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)