Menu Close

Escalada hasta un primo

José A. Alonso,

Este ejercicio está basado en el artículo La conjetura de la «escalada hasta un primo» publicado esta semana por Miguel Ángel Morales en su blog Gaussianos.

La conjetura de escalada hasta un primo trata, propuesta por John Horton Conway, es sencilla de plantear, pero primero vamos a ver qué es eso de escalar hasta un primo. Tomamos un número cualquiera y lo descomponemos en factores primos (colocados en orden ascendente). Si el número era primo, ya hemos acabado; si no era primo, construimos el número formado por los factores primos y los exponentes de los mismos colocados tal cual salen en la factorización. Con el número obtenido hacemos lo mismo que antes. La escalada finaliza cuando obtengamos un número primo. Por ejemplo, para obtener la escalada prima de 1400, como no es primo, se factoriza (obteniéndose 2^3 * 5^2 * 7) y se unen bases y exponentes (obteniéndose 23527). Con el 23527 se repite el proceso obteniéndose la factorización (7 * 3361) y su unión (73361). Como el 73361 es primo, termina la escalada. Por tanto, la escalada de 1400 es [1400,23527,73361].

La conjetura de Conway sobre «escalada hasta un primo» dice que todo número natural mayor o igual que 2 termina su escalada en un número primo.

Definir las funciones

   escaladaPrima                :: Integer -> [Integer]
   longitudEscaladaPrima        :: Integer -> Integer
   longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
   graficaEscalada              :: Integer -> Integer -> IO ()

tales que

  • (escaladaPrima n) es la escalada prima de n. Por ejemplo,
     λ> escaladaPrima 1400
     [1400,23527,73361]
     λ> escaladaPrima 333
     [333,3237,31383,3211317,3217139151,39722974813]
     λ> take 10 (escaladaPrima 20)
     [20,225,3252,223271,297699,399233,715623,3263907,32347303,160720129]
     λ> take 3 (escaladaPrima 13532385396179)
     [13532385396179,13532385396179,13532385396179]
     λ> take 2 (escaladaPrima 45214884853168941713016664887087462487)
     [45214884853168941713016664887087462487,13532385396179]
  • (longitudEscaladaPrima n) es la longitud de la escalada prima de n. Por ejemplo,
     longitudEscaladaPrima 1400  ==  3
     longitudEscaladaPrima 333   ==  6
  • (longitudEscaladaPrimaAcotada n k) es el mínimo entre la longitud de la escalada prima de n y k. Por ejemplo,
     longitudEscaladaPrimaAcotada 333 10  ==  6
     longitudEscaladaPrimaAcotada 333 4   ==  4
     longitudEscaladaPrimaAcotada 20 4    ==  4
  • (graficaEscalada n k) dibuja la gráfica de (longitudEscaladaPrimaAcotada x k) para x entre 2 y n. Por ejemplo, (graficaEscalada 120 15) dibuja
    Escalada_hasta_un_primo

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes
import Graphics.Gnuplot.Simple
 
-- Definición de escaladaPrima 
escaladaPrima :: Integer -> [Integer]
escaladaPrima n
  | isPrime n = [n]
  | otherwise = n : escaladaPrima (siguiente n)
 
-- (siguiente n) es el siguiente de n en la escalada hacia un primo. Por
-- ejemplo, 
--    siguiente 1400  ==  23527
siguiente :: Integer -> Integer
siguiente = paresAnumero . factorizacion
 
-- (factorizacion n) es la factorizacion prima de n. Por ejemplo,
--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(x,genericLength xs) | xs@(x:_) <- group (primeFactors n)]
 
-- (paAnumero p) es el número obtenido pegando las dos componentes de p
-- (si la segunda es mayor que 1) o sólo la primera componente, en caso
-- contrario. Por ejemplo, 
--    parAnumero (7,1)  ==  7
--    parAnumero (23,5)  ==  235
parAnumero :: (Integer,Integer) -> Integer
parAnumero (n,1) = n
parAnumero (n,k) = read (show n ++ show k)
 
-- (paresA numeros ps) es el número obtenido aplicando parAnumero a cada
-- uno de los pares de ps. Por ejemplo,
--    paresAnumero [(2,3),(5,2),(7,1)]  ==  23527
paresAnumero :: [(Integer,Integer)] -> Integer
paresAnumero = read . concatMap (show . parAnumero)
 
-- Definición de longitudEscaladaPrima
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima n
  | isPrime n = 1
  | otherwise = 1 + longitudEscaladaPrima (siguiente n)
 
-- Definición de longitudEscaladaPrimaAcotada
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada _ 0 = 0
longitudEscaladaPrimaAcotada n k
  | isPrime n = 1
  | otherwise = 1 + longitudEscaladaPrimaAcotada (siguiente n) (k-1)
 
-- Definición de graficaEscalada 
graficaEscalada :: Integer -> Integer -> IO ()
graficaEscalada n k =
  plotList [ Key Nothing
           , PNG "Escalada_hasta_un_primo.png"
           , Title ("graficaEscalada " ++ show n ++ " " ++ show k)
           , XLabel "Numeros"
           , YLabel "Longitud de escalada"
           ]
           [(x,longitudEscaladaPrimaAcotada x k) | x <- [2..n]]
Posted in Medio
Tagged , , , , , , , , , , ,

5 Comments

  1. alerodrod5
    Responder

    Aquí una primera definición, lo único es que no se como hacer para que la n y x del título de la grafica cambien en función de la que vas poniendo.

    import Data.Numbers.Primes
import Data.List
import Graphics.Gnuplot.Simple
escaladaPrima                :: Integer -> [Integer]
escaladaPrima x | isPrime x = [x]
                | otherwise = x : escaladaPrima (numero2(primosconpotencia x))
 
primosconpotencia :: Integer -> [Integer]
primosconpotencia x = concat(map (separa)[(x,y)| (x,y) <- zip (map head ys)(map genericLength ys)])
  where ys=group(primeFactors x)
 
numero xs =sum [x*10^y | (x,y) <- zip xs [length xs-1, length xs -2..0]]
 
numero2 xs = numero(concat (map cifras xs))
  where cifras x = [read [d] | d<-show x]
 
separa (x,1) = [x]
separa (x,y) = x :[y]
 
longitudEscaladaPrima        :: Integer -> Integer
longitudEscaladaPrima x = genericLength (escaladaPrima x)
 
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada x n | isPrime (aux(drop (fromInteger n) (escaladaPrima x))) = longitudEscaladaPrima x
                                 |otherwise = n
                                  where aux [] = 2
                                        aux xs = head xs
longitudEscalada n x  = [longitudEscaladaPrimaAcotada y x  | y<-[2..n]]
 
graficaEscalada              :: Integer -> Integer -> IO ()
graficaEscalada n x = plotList [Title "graficaEscalada", XLabel "Numeros", YLabel "Longitud de escalada", Key Nothing] ( (longitudEscalada n x))
  2. jaibengue
    Responder 
    import Data.Numbers.Primes
import Data.List
 
escaladaPrima :: Integer -> [Integer]
escaladaPrima n | isPrime n = [n]
                | otherwise = n : escaladaPrima itt
  where itt              = (read.concat.aux.group.primeFactors) n
        aux []           = []
        aux ([x]:xss)    = show x:aux xss
        aux ((x:xs):xss) = show x:show (1 + length xs):aux xss
 
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima = fromIntegral.length.escaladaPrima
 
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada n m | n > m     = m
                                 | isPrime n = 1
                                 | otherwise = 1 + longitudEscaladaPrimaAcotada itt m
  where itt              = (read.concat.aux.group.primeFactors) n
        aux []           = []
        aux ([x]:xss)    = show x:aux xss
        aux ((x:xs):xss) = show x:show (1 + length xs):aux xss
  3. jaibengue
    Responder 
    import Data.Numbers.Primes
import Data.List
 
escaladaPrima :: Integer -> [Integer]
escaladaPrima n | isPrime n = [n]
                | otherwise = n : escaladaPrima itt
  where itt              = (read.concat.aux.group.primeFactors) n
        aux []           = []
        aux ([x]:xss)    = show x:aux xss
        aux ((x:xs):xss) = show x:show (1 + length xs):aux xss
 
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima = fromIntegral.length.escaladaPrima
 
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada n m | m == 0    = 0
                                 | isPrime n = 1
                                 | otherwise = 1 + longitudEscaladaPrimaAcotada itt (m-1)
  where itt              = (read.concat.aux.group.primeFactors) n
        aux []           = []
        aux ([x]:xss)    = show x:aux xss
        aux ((x:xs):xss) = show x:show (1 + length xs):aux xss
  4. carriomon1
    Responder

    import Data.List
    import Data.Numbers.Primes
    import Graphics.Gnuplot.Simple

     
escaladaPrima :: Integer -> [Integer]
escaladaPrima x =  takeWhile (not.isPrime) zs ++ [head (dropWhile (not.isPrime) zs)]
              where zs = iterate escalada x 
 
escalada :: Integer ->Integer
escalada n = listaAnum (concat $ map (delete 1)[[a,b] | (a,b) <- as])
    where as = zip (nub xs) ((map genericLength $ group xs))
          xs = map toInteger $ primeFactors n
 
listaAnum :: [Integer] -> Integer
listaAnum xs = read ( concat (map show xs))
 
 
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima  = genericLength . escaladaPrima 
 
 
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada n k | genericTake (k-1) ws == genericTake k  ws = longitudEscaladaPrima n
                                 | otherwise = k
                            where ws = escaladaPrima n
 
graficaEscalada :: Integer -> Integer -> IO ()
graficaEscalada n k = plotList [Title "graficaEscalada n k" , XLabel "Numeros" ,
                                YLabel "Longitud de Escalada", Key Nothing]
                                [longitudEscaladaPrimaAcotada x k | x <- [2..n]]
  5. angruicam1
    Responder 
    import Data.Numbers.Primes (primeFactors,isPrime)
import Data.List (group,genericLength,genericTake)
import Graphics.Gnuplot.Simple (plotList,Attribute(Title,XLabel,YLabel,Key))
 
escaladaPrima :: Integer -> [Integer]
escaladaPrima = aux . iterate escalada
  where aux (x:xs) | isPrime x = [x]
                   | otherwise = x : aux xs
 
-- (escalada x) obtiene el siguiente término a x
-- en la sucesión escaladaPrima.
 
escalada :: Integer -> Integer
escalada =
  read
  . concat
  . concatMap ( y@(x:xs) ->
                 if null xs
                 then [show x]
                 else [show x,show . length $ y])
  . group
  . primeFactors
 
longitudEscaladaPrima :: Integer -> Integer
longitudEscaladaPrima = genericLength . escaladaPrima
 
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
longitudEscaladaPrimaAcotada n k =
  min k (genericLength . genericTake k . escaladaPrima $ n)
 
graficaEscalada :: Integer -> Integer -> IO ()
graficaEscalada n k =
  plotList
  [Title $ "graficaEscalada " ++ show n ++ " " ++ show k,
   XLabel "Numeros",
   YLabel "Longitud de escalada",
   Key Nothing]
  (map (`longitudEscaladaPrimaAcotada` k) [2..n])

Escribe tu solución

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