Menu Close

Etiqueta: toInteger

Mayor producto de n dígitos consecutivos de un número

José A. Alonso, ,

Definir la función

   mayorProducto :: Int -> Integer -> Integer

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

   mayorProducto 2 325                  ==  10
   mayorProducto 5 11111                ==  1
   mayorProducto 5 113111               ==  3
   mayorProducto 5 110111               ==  0
   mayorProducto 5 10151112             ==  10
   mayorProducto 5 101511124            ==  10
   mayorProducto 5 (product [1..1000])  ==  41472

Nota: Este ejercicio está basado en el problema 8 del Proyecto Euler

Soluciones

import Data.List (inits, tails)
import Data.Char (digitToInt)
 
-- 1ª solución
-- ===========
 
mayorProducto :: Int -> Integer -> Integer
mayorProducto n x =
  maximum [product xs | xs <- segmentos n (digitos x)]
 
-- (digitos x) es la lista de las digitos del número x. Por ejemplo, 
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos x = map (toInteger . digitToInt) (show x)
 
-- (segmentos n xs) es la lista de los segmentos de longitud n de la
-- lista xs. Por ejemplo,
--    segmentos 2 [3,5,4,6]  ==  [[3,5],[5,4],[4,6]]
segmentos :: Int -> [Integer] -> [[Integer]]
segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))
 
-- 2ª solución
-- ===========
 
mayorProducto2 :: Int -> Integer -> Integer
mayorProducto2 n x = maximum (aux ns)
    where ns     = [read [d] | d <- show x]
          aux xs | length xs < n = []
                 | otherwise     = product (take n xs) : aux (tail xs)
 
-- 3ª solución
-- ===========
 
mayorProducto3 :: Int -> Integer -> Integer
mayorProducto3 n = maximum
                 . map (product . take n)
                 . filter ((>=n) . length) 
                 . tails
                 . digitos
 
-- 4ª solución
-- ===========
 
mayorProducto4 :: Int -> Integer -> Integer
mayorProducto4 n = maximum  
                 . map (product . map (fromIntegral . digitToInt)) 
                 . filter ((==n) . length) 
                 . concatMap inits
                 . tails 
                 . show
 
-- Comparación de eficiencia
-- =========================
 
--    λ> mayorProducto 5 (product [1..500])
--    28224
--    (0.01 secs, 1,645,256 bytes)
--    λ> mayorProducto2 5 (product [1..500])
--    28224
--    (0.03 secs, 5,848,416 bytes)
--    λ> mayorProducto3 5 (product [1..500])
--    28224
--    (0.03 secs, 1,510,640 bytes)
--    λ> mayorProducto4 5 (product [1..500])
--    28224
--    (1.85 secs, 10,932,551,216 bytes)
--    
--    λ> mayorProducto 5 (product [1..7000])
--    46656
--    (0.10 secs, 68,590,808 bytes)
--    λ> mayorProducto2 5 (product [1..7000])
--    46656
--    (1.63 secs, 157,031,432 bytes)
--    λ> mayorProducto3 5 (product [1..7000])
--    46656
--    (1.55 secs, 65,727,176 bytes)

Pensamiento

“El control de la complejidad es la esencia de la programación.” ~ B.W. Kernigan

Leer más →

Sucesión de Lichtenberg

José A. Alonso, ,

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son

   Alternada ..... Lichtenberg
   0 ....................... 0
   1 ....................... 1
   10 ...................... 2
   101 ..................... 5
   1010 ................... 10
   10101 .................. 21
   101010 ................. 42
   1010101 ................ 85
   10101010 .............. 170
   101010101 ............. 341
   1010101010 ............ 682
   10101010101 .......... 1365
   101010101010 ......... 2730

Definir las funciones

   lichtenberg        :: [Integer]
   graficaLichtenberg :: Int -> IO ()

tales que

  • lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo, 
     λ> take 17 lichtenberg
     [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]
  • (graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja
    Sucesion_de_Lichtenberg

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Soluciones

import Data.Char (digitToInt)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
import Data.Numbers.Primes (isPrime)
 
-- 1ª solución
-- ===========
 
lichtenberg1 :: [Integer]
lichtenberg1 = map binarioAdecimal sucAlternada
 
-- sucAlternada es la lista cuyos elementos son los términos de la
-- sucesión de los dígitos 0 y 1 alternados. Por ejemplo,
--    λ> take 7 sucAlternada
--    ["0","1","10","101","1010","10101","101010"]
sucAlternada :: [String]
sucAlternada =
  ['0'] : [take n cadenaAlternada | n <- [1..]]
 
-- cadenaAltenada es la cadena formada alternando los caracteres 1 y
-- 0. Por ejemplo,
--    take 20 cadenaAlternada  ==  "10101010101010101010"
cadenaAlternada :: String
cadenaAlternada = cycle ['1','0']
 
-- (binarioAdecimal cs) es el número decimal correspondiente al número
-- binario cuya cadena de dígitos es cs. Por ejemplo,
--    binarioAdecimal "11101"  ==  29
binarioAdecimal :: String -> Integer
binarioAdecimal =
  foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0
 
-- 2ª solución
lichtenberg2 :: [Integer]
lichtenberg2 = map a [0..]
  where a 0 = 0
        a 1 = 1
        a n = a (n-1) + 2 * a (n-2) + 1
 
-- 3ª solución
lichtenberg3 :: [Integer]
lichtenberg3 =
  0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3)) 
 
-- Comprobación de eficiencia
--    λ> length (show (lichtenberg1 !! 27))
--    8
--    (0.02 secs, 155,384 bytes)
--    λ> length (show (lichtenberg2 !! 27))
--    8
--    (2.22 secs, 311,157,760 bytes)
--    
--    λ> length (show (lichtenberg1 !! (8*10^4)))
--    24083
--    (1.28 secs, 664,207,040 bytes)
--    λ> length (show (lichtenberg3 !! (8*10^4)))
--    24083
--    (2.59 secs, 1,253,328,200 bytes)
 
-- La propiedad es
propLichtenberg :: Int -> Property
propLichtenberg n =
  n > 4 ==> not (isPrime (lichtenberg1 !! n))
 
-- La comprobación es
--    λ> quickCheck propLichtenberg
--    +++ OK, passed 100 tests.
 
graficaLichtenberg :: Int -> IO ()
graficaLichtenberg n =
  plotList [ Key Nothing
           , Title "Numero de digitos de la sucesion de Lichtenberg"
           , PNG "Sucesion_de_Lichtenberg.png"
           ]
           (take n (map (length . show) lichtenberg1))
Leer más →

Números dígito potenciales

José A. Alonso, ,

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

  • 153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
  • 4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

   digitosPotencialesOrden :: Integer -> [Integer]
   digitosAutoPotenciales  :: [Integer]

tales que

  • (digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo, 
     take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
     take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
     take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
     take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]
  • digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo, 
     λ> take 20 digitosAutoPotenciales
     [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Soluciones

import Data.List (genericLength)
import Data.Char (digitToInt)
 
-- 1ª definición de digitosPotencialesOrden
-- ========================================
 
digitosPotencialesOrden :: Integer -> [Integer]
digitosPotencialesOrden n =
  [x | x <- [0..]
     , esDigitoPotencialOrden n x]
 
esDigitoPotencialOrden :: Integer -> Integer -> Bool
esDigitoPotencialOrden n x =
  x == sum [y^n | y <- digitos x]
 
digitos :: Integer -> [Integer]
digitos x = [read [d] | d <- show x] 
 
-- 2ª definición de digitosPotencialesOrden
-- ========================================
 
digitosPotencialesOrden2 :: Integer -> [Integer]
digitosPotencialesOrden2 n =
  filter (esDigitoPotencialOrden2 n) [0..]
 
esDigitoPotencialOrden2 :: Integer -> Integer -> Bool
esDigitoPotencialOrden2 n x =
  x == sum (map (^n) (digitos2 x))
 
digitos2 :: Integer -> [Integer]
digitos2 = map (toInteger . digitToInt) . show
 
-- 3ª definición de digitosPotencialesOrden
-- ========================================
 
--    digitosPotencialesOrden3 3  ==  [0,1,153,370,371,407]
--    digitosPotencialesOrden3 4  ==  [0,1,1634,8208,9474]
digitosPotencialesOrden3 :: Integer -> [Integer]
digitosPotencialesOrden3 n =
  filter (esDigitoPotencialOrden2 n) [0..10^d-1]
  where d = maximoNDigitosPotencialesOrden n 
 
-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de
-- los números dígitos potenciales de orden d. Por ejemplo,
--    maximoNDigitosPotencialesOrden 3  ==  5
--    maximoNDigitosPotencialesOrden 5  ==  7
maximoNDigitosPotencialesOrden :: Integer -> Integer
maximoNDigitosPotencialesOrden n =
  head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])
 
-- 1ª definición de esDigitoAutoPotencial
-- ======================================
 
esDigitoAutoPotencial :: Integer -> Bool
esDigitoAutoPotencial x =
  esDigitoPotencialOrden (genericLength (show x)) x
 
digitosAutoPotenciales :: [Integer]
digitosAutoPotenciales =
  filter esDigitoAutoPotencial [0..]
 
-- 2ª definición de esDigitoAutoPotencial
-- ======================================
 
digitosAutoPotenciales2 :: [Integer]
digitosAutoPotenciales2 =
  0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]
            | k <- [0..]]
Leer más →