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?
Last active
September 14, 2017 22:44
-
-
Save Garciat/90c40974386462f1c88bba673ccd513b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment