Garciat
8/4/2017 - 8:36 PM

## Circle.hs

Hay 100 personas en círculo, la número 1 tiene un marcador y elimina al de al lado, y el marcador pasa al tercero (del 1 al 3, del 3 al 5, del 5 al 7, etc), este proceso sigue hasta que quede solo uno, los números asignados a una persona siempre se mantienen ¿Cuál es el número que pertenece a la persona que queda?

``````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)
``````