gistfile1.hs

import Data.List(sort)
import Math.Algebra.Group.PermutationGroup(fromPairs)

data Op = DN | UP deriving (Show, Eq, Ord)

paso :: (Integral a) => (a -> a) -> a -> a
paso hazpar x = if odd x then div (hazpar x) 2 else div x 2

-- 'take n $ serieInfinita binarios x' da una representación binaria de
-- x truncada a n bits, 'DN' es 0, 'UP' es 1, el primer bit en la cadena
-- es el más a la derecha en la representación binaria estándar

-- 'take n $ serieInfinita collatz x' presenta el comportamiento hasta
-- n pasos de x iterando bajo reglas de Collatz

serieInfinita :: (Integral a) => (a -> a) -> a -> [Op]
serieInfinita f x = actual : serieInfinita f siguiente where
    actual = if odd x then UP else DN
    siguiente = paso f x

-- Funciones de hacer par

binarios :: (Integral a) => a -> a
binarios n = n - 1

collatz :: (Integral a) => a -> a
collatz  n = 3*n + 1

-- para cada lista de n bits presenta un par (binario,collatz) en el que
-- 'binario' es la representación decimal de la lista en orden inverso
-- interpretada como binario, y 'collatz' es el número entre 0 y 2^n - 1
-- que presenta ese comportamiento

pares :: Int -> [(Integer,Integer)]
pares n = zip t1 t2 where
    t1 = map snd $ sort $ zip (map (take n . serieInfinita binarios) ys) ys
    t2 = map snd $ sort $ zip (map (take n . serieInfinita collatz) ys) ys
    ys = [0..((2^n)-1)]

-- Si la transformación bajo reglas binaria y collatz de un número entre
-- 0 y 2^n - 1 es la misma, ese número no aparece entre los ciclos. En otro
-- caso, el ciclo [a1, a2, a3, ... ak] significa que la representación binaria
-- de ai es la representación collatz de a(i+1), y que la representación
-- binaria de ak es la representación collatz de a1.

ciclos n = fromPairs $ pares n