Conjetura de Collatz generalizada

PorJosé A. Alonso 10-febrero-202017-febrero-2020

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]

-> 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]

1	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]

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.

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 Comentarios

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)

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)

Responder

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

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

Responder

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.

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.

Responder

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

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

Responder

Conjetura de Collatz generalizada

Soluciones

Otras soluciones

Pensamiento

4 Comentarios

Leave a Reply to rebgongorCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

4 Comentarios

Leave a Reply to rebgongorCancel reply

Entradas recientes

Buscar

Correo electrónico