Menu Close

Escalada hasta un primo

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

5 soluciones de “Escalada hasta un primo

  1. alerodrod5

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

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

Leave a Reply

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