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
|
1 2 3 4 |
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,
|
1 2 3 4 5 6 7 8 9 10 |
λ> 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,
|
1 2 |
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,
|
1 2 3 |
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
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
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]] |