Menu Close

Conjetura de Collatz generalizada

Sea p un número primo. Toma un número natural positivo, si es divisible entre un número primo menor que p divídelo entre el menor de dicho divisores, y en otro caso multiplícalo por p y súmale uno; si el resultado no es igual a uno, repite el proceso. Por ejemplo, para p = 7 y empezando en 42 el proceso es

   42
   -> 21   [= 42/2]
   -> 7    [= 21/3]
   -> 50   [= 7*7+1]
   -> 25   [= 50/5]
   -> 5    [= 25/5]
   -> 1    [= 5/5]

La conjetura de Collatz generalizada afirma que este proceso siempre acaba en un número finito de pasos.

Definir la función

   collatzGeneral :: Integer -> Integer -> [Integer]

tal que (collatzGeneral p x) es la sucesión de los elementos obtenidos en el proceso anterior para el primo p enpezando en x. Por ejemplo,

   take 15 (collatzGeneral 7 42) == [42,21,7,50,25,5,1,8,4,2,1,8,4,2,1]
   take 15 (collatzGeneral 3  6) == [6,3,10,5,16,8,4,2,1,4,2,1,4,2,1]
   take 15 (collatzGeneral 5  6) == [6,3,1,6,3,1,6,3,1,6,3,1,6,3,1]
   take 15 (collatzGeneral 7  6) == [6,3,1,8,4,2,1,8,4,2,1,8,4,2,1]
   take 15 (collatzGeneral 9  6) == [6,3,1,10,5,1,10,5,1,10,5,1,10,5,1]

Comprobar con QuickCheck que se verifica la conjetura de Collatz generalizada; es decir, para todos enteros positivos n, x si p es el primo n-ésimo entonces 1 pertenece a (collatzGeneral p x).

Nota: El ejercicio etá basado en el artículo Los primos de la conjetura de Collatz publicado la semana pasada por Francisco R. Villatoro en su blog La Ciencia de la Mula Francis.

Soluciones

import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck
 
collatzGeneral :: Integer -> Integer -> [Integer]
collatzGeneral p x =
  iterate (siguiente p) x
 
siguiente :: Integer -> Integer -> Integer
siguiente p x 
  | null xs   = p * x + 1
  | otherwise = x `div` head xs
  where xs = takeWhile (<p) (primeFactors x)
 
prop_collatzGeneral :: Int -> Integer -> Property
prop_collatzGeneral n x =
  n > 0 && x > 0 ==>
  1 `elem` collatzGeneral p x
  where p = primes !! n 
 
-- La comprobación es
--    λ> quickCheck prop_collatzGeneral
--    +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

“Las matemáticas son la ciencia que utiliza palabras fáciles para ideas difíciles.”

Edward Kasner y James R. Newman

4 soluciones de “Conjetura de Collatz generalizada

  1. claniecas
    import Data.Numbers.Primes
     
    collatzGeneralA1 :: Integer -> Integer -> [Integer]
    collatzGeneralA1 p x = x : collatzAux p x
     
    collatzAux :: Integer -> Integer -> [Integer]
    collatzAux p x = a : collatzAux p a
      where a = collatz p x
     
    collatz :: Integer -> Integer -> Integer
    collatz p x | x == 1    = p + 1
                | y < p     = div x y
                | otherwise = p*x + 1
      where y = head (primeFactors x)
  2. fercarnav
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
     
    collatzGeneral :: Integer -> Integer -> [Integer]
    collatzGeneral p x = x : collatzGeneral p (collatz x p) 
     
    collatz :: Integer -> Integer -> Integer
    collatz x y
      | divisorElegido x ys == 0 = x*y+1
      | otherwise                = div x  (divisorElegido x ys)
      where ys = takeWhile (<y) primes
     
    divisorElegido :: Integer -> [Integer] ->  Integer
    divisorElegido x [] = 0
    divisorElegido x (y:ys)
      | mod x y == 0 = y
      | otherwise    = divisorElegido x ys
     
    prop_collatz :: Integer -> Integer -> Property
    prop_collatz n x = n > 0 && x > 0 ==>
      elem 1 (collatzGeneral p x)
      where p = genericIndex primes n
  3. rebgongor
    import Data.List (genericIndex)
    import Data.Numbers.Primes (primeFactors, primes)
    import Test.QuickCheck
     
    collatzGeneral :: Integer -> Integer -> [Integer]
    collatzGeneral p x = iterate (collatz p) x
     
    collatz :: Integer -> Integer -> Integer
    collatz p x
      | any (<p) [n | n <- primeFactors x, rem x n == 0] =
        div x (head (primeFactors x))
      |otherwise = p*x+1
     
    conjetura :: Positive Integer -> Positive Integer -> Bool
    conjetura (Positive n) (Positive x) =
      elem 1 (collatzGeneral (genericIndex primes n) x)
     
    -- λ> quickCheck conjetura
    -- +++ OK, passed 100 tests.
  4. Carlos
    import Data.Numbers.Primes
    import Test.QuickCheck
     
    collatzGeneral :: Integer -> Integer -> [Integer]
    collatzGeneral p = iterate collatz
      where ps = takeWhile (<p) primes
            collatz n = case [d | (d,m) <- map (divMod n) ps, m==0] of
                        (x:_) -> x
                        []    -> p*n + 1
     
    findCycle :: Eq a => [a] -> ([a],[a])
    findCycle xxs = fCycle xxs xxs
      where fCycle (x:xs) (_:y:ys)
             | x == y              = fStart xxs xs
             | otherwise           = fCycle xs ys
            fCycle _      _        = (xxs,[]) -- not cyclic
            fStart (x:xs) (y:ys)
             | x == y              = ([], x:fLength x xs)
             | otherwise           = let (as,bs) = fStart xs ys in (x:as,bs)
            fLength x (y:ys)
             | x == y              = []
             | otherwise           = y:fLength x ys
     
    prop_Collatz :: (Positive Int) -> (Positive Integer) -> Property
    prop_Collatz (Positive k) (Positive n) = elem 1 xs === True
      where xs = uncurry (++) $ findCycle $ collatzGeneral p n
            p = primes !! k
     
    main = quickCheck prop_Collatz
     
    -- *** Failed! Falsified (after 21 tests):
    -- Positive {getPositive = 4}
    -- Positive {getPositive = 17}
    -- False /= True

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.