Menu Close

Etiqueta: find

Números taxicab

José A. Alonso, ,

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

   taxicab  :: [Integer]
   taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

   take 5 taxicab   ==  [1729,4104,13832,20683,32832]
   take 2 taxicab2  ==  [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.List  (find)
import Data.Maybe (fromJust)
 
taxicab :: [Integer]
taxicab = filter ((> 1) . length . descomposiciones) [1..]
 
-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.
-- Por ejemplo,
--    descomposiciones 1729  ==  [(10,9),(12,1)]
--    descomposiciones 1728  ==  [(12,0)]
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(x,y) | x <- [1..round (fromIntegral n ** (1/3))],
           let z = n - x^3,
           let z' = round (fromIntegral z ** (1/3)),
           z'^3 == z,
           let y = z',
           y <= x]
 
-- 2ª definición de descomposiciones
descomposiciones2 :: Integer -> [(Integer,Integer)]
descomposiciones2 n =
  [(x,y) | x <- [1..raizEnt n 3],
           let z = n - x^3,
           let y = raizEnt z 3,
           y <= x,    
           y^3 == z]
 
-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor
-- número entero y tal que y^n <= x. Por ejemplo, 
--    raizEnt  8 3      ==  2
--    raizEnt  9 3      ==  2
--    raizEnt 26 3      ==  2
--    raizEnt 27 3      ==  3
--    raizEnt (10^50) 2 ==  10000000000000000000000000
-- ---------------------------------------------------------------------
 
raizEnt :: Integer -> Integer -> Integer
raizEnt x n = aux (1,x)
  where aux (a,b) | d == x    = c
                  | c == a    = c
                  | d < x     = aux (c,b)
                  | otherwise = aux (a,c) 
          where c = (a+b) `div` 2
                d = c^n
 
taxicab2 :: [Integer]
taxicab2 = aux 1 [2..]
  where aux n xs = fx : aux (n+1) [fx+1..]
          where fx = fromJust (find ((== n) . length . descomposiciones) xs)
Leer más →

Números apocalípticos

José A. Alonso, ,

Un número apocalíptico es aquel número natural n tal que 2^n contiene la secuencia 666.

Definir las funciones

   esApocaliptico           :: Integer -> Bool
   apocalipticos            :: [Integer]
   mayorNoApocalipticoMenor :: Integer -> Maybe Integer
   grafica                  :: Integer -> IO ()

tales que

  • (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,
     esApocaliptico 666    ==  True
     esApocaliptico 29784  ==  False
  • apocalipticos es la lista de los números apocalípticos. Por ejemplo,
     take 9 apocalipticos  ==  [157,192,218,220,222,224,226,243,245]
     apocalipticos !! 55   ==  666
  • (mayorNoApocalipticoMenor n) es justo el mayor número no apocalíptico menor que n. Por ejemplo,
     mayorNoApocalipticoMenor  40000  ==  Just 29784
     mayorNoApocalipticoMenor  29784  ==  Just 26667
  • (grafica n) dibuja las gráficas de los n primeros términos de la sucesión de los números apocalípticos junto con los de la sucesión a(n) = 3715+n. Por ejemplo, (grafica 3000) dibuja
    Numeros_apocalipticos_3000
    y (grafica 30000) dibuja
    Numeros_apocalipticos_30000

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.List (isInfixOf, find, genericTake)
import Graphics.Gnuplot.Simple
 
esApocaliptico :: Integer -> Bool
esApocaliptico = isInfixOf "666" . show . (2^)
 
apocalipticos :: [Integer]
apocalipticos = filter esApocaliptico [1..]
 
mayorNoApocalipticoMenor :: Integer -> Maybe Integer
mayorNoApocalipticoMenor n = find (not . esApocaliptico) [n-1,n-2..1]
 
grafica :: Integer -> IO ()
grafica n = 
  plotLists [ Key Nothing
            , PNG ("Numeros_apocalipticos_" ++ show n ++ ".png")
            ]
            [ genericTake n apocalipticos
            , [3715..3715+n-1] ]
Leer más →

Elemento más cercano que cumple una propiedad

José A. Alonso, , 
-- Definir la función
--    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
-- tal que (cercano p n xs) es el elemento de xs más cercano a n que
-- verifica la propiedad p. La búsqueda comienza en n y los elementos se
-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo, 
--    cercano (`elem` "aeiou") 6 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 1 "Sevilla"     ==  Just 'e'
--    cercano (`elem` "aeiou") 2 "Sevilla"     ==  Just 'i'
--    cercano (`elem` "aeiou") 5 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 9 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") (-3) "Sevilla"  ==  Just 'e'
--    cercano (>100) 4 [200,1,150,2,4]         ==  Just 150
--    cercano even 5 [1,3..99]                 ==  Nothing

Soluciones

import Data.List
 
-- 1ª solución
-- ===========
 
cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano1 p n xs | null ys   = Nothing
                | otherwise = Just (head ys)
    where ys = filter p (ordenaPorCercanos xs n)
 
-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que
-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo, 
--    ordenaPorCercanos [0..9] 4     ==  [4,5,3,6,2,7,1,8,0,9]
--    ordenaPorCercanos [0..9] 7     ==  [7,8,6,9,5,4,3,2,1,0]
--    ordenaPorCercanos [0..9] 2     ==  [2,3,1,4,0,5,6,7,8,9]
--    ordenaPorCercanos [0..9] (-3)  ==  [0,1,2,3,4,5,6,7,8,9]
--    ordenaPorCercanos [0..9] 20    ==  [9,8,7,6,5,4,3,2,1,0]
ordenaPorCercanos :: [a] -> Int -> [a]
ordenaPorCercanos xs n 
    | n < 0          = xs
    | n >= length xs = reverse xs
    | otherwise      = z : intercala zs (reverse ys)
    where (ys,(z:zs)) = splitAt n xs
 
-- (intercala xs ys) es la lista obtenida intercalando los elementos de
-- las lista xs e ys. Por ejemplo,
--    intercala [1..4] [5..10]   ==  [1,5,2,6,3,7,4,8,9,10]
--    intercala [5..10] [1..4]   ==  [5,1,6,2,7,3,8,4,9,10]
intercala :: [a] -> [a] -> [a]
intercala [] ys = ys
intercala xs [] = xs
intercala (x:xs) (y:ys) = x : y : intercala xs ys
 
-- 2ª solución (usando find)
-- =========================
 
cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano2 p n xs = find p (ordenaPorCercanos xs n)

Referencia

El ejercicio está basado en el problema del 12 de mayo de 1HaskellADay.

Leer más →