map

La función de Smarandache

PorJosé A. Alonso 27-febrero-20186-marzo-2018

La función de Smarandache, también conocida como la función de Kempner, es la función que asigna a cada número entero positivo n el menor número cuyo factorial es divisible por n y se representa por S(n). Por ejemplo, el número 8 no divide a 1!, 2!, 3!, pero sí divide 4!; por tanto, S(8) = 4.

Definir las funciones

   smarandache        :: Integer -> Integer
   graficaSmarandache :: Integer -> IO ()

1 2	smarandache :: Integer -> Integer graficaSmarandache :: Integer -> IO ()

tales que

(smarandache n) es el menor número cuyo factorial es divisible por n. Por ejemplo,

     smarandache 8   ==  4
     smarandache 10  ==  5
     smarandache 16  ==  6

smarandache 8 == 4

smarandache 10 == 5

smarandache 16 == 6

(graficaSmarandache n) dibuja la gráfica de los n primeros términos de la sucesión de Smarandache. Por ejemplo, (graficaSmarandache 100) dibuja

(graficaSmarandache 500) dibuja

Soluciones

import Data.List (genericLength)
import Graphics.Gnuplot.Simple

smarandache :: Integer -> Integer
smarandache x =
  head [n | (n,y) <- zip [0..] factoriales
          , y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo, 
--    λ> take 12 factoriales
--    [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

graficaSmarandache :: Integer -> IO ()
graficaSmarandache n =
  plotList [Key Nothing
           , PNG ("La_funcion_de_Smarandache_" ++ show n ++ ".png")
           ]
           (map smarandache [1..n])

import Data.List (genericLength)

import Graphics.Gnuplot.Simple

smarandache :: Integer -> Integer

smarandache x =

head [n | (n,y) <- zip [0..] factoriales

, y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo,

-- λ> take 12 factoriales

-- [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]

factoriales :: [Integer]

factoriales = 1 : scanl1 (*) [1..]

graficaSmarandache :: Integer -> IO ()

graficaSmarandache n =

plotList [Key Nothing

, PNG ("La_funcion_de_Smarandache_" ++ show n ++ ".png")

]

(map smarandache [1..n])

Ceros con los n primeros números

PorJosé A. Alonso 23-febrero-20182-marzo-2018

Los números del 1 al 3 se pueden escribir de dos formas, con el signo más o menos entre ellos, tales que su suma sea 0:

    1+2-3 = 0
   -1-2+3 = 0

1 2	1+2-3 = 0 -1-2+3 = 0

Definir la función

   ceros :: Int -> [[Int]]

1	ceros :: Int -> [[Int]]

tal que (ceros n) son las posibles formas de obtener cero sumando los números del 1 al n, con el signo más o menos entre ellos. Por ejemplo,

   ceros 3           ==  [[1,2,-3],[-1,-2,3]]
   ceros 4           ==  [[1,-2,-3,4],[-1,2,3,-4]]
   ceros 5           ==  []
   length (ceros 7)  ==  8
   take 3 (ceros 7)  ==  [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7]]

ceros 3 == [[1,2,-3],[-1,-2,3]]

ceros 4 == [[1,-2,-3,4],[-1,2,3,-4]]

ceros 5 == []

length (ceros 7) == 8

take 3 (ceros 7) == [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7]]

Soluciones

-- 1ª solución
-- ===========

ceros :: Int -> [[Int]]
ceros n = [xs | xs <- candidatos n, sum xs == 0]

-- (candidatos n) es la lista de los números del 1 al n con los signos
-- más o menos. Por ejemplo,
--    λ> candidatos 1
--    [[1],[-1]]
--    λ> candidatos 2
--    [[1,2],[1,-2],[-1,2],[-1,-2]]
--    λ> candidatos 3
--    [[1,2,3],[1,2,-3],[1,-2,3],[1,-2,-3],[-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]]
candidatos :: Int -> [[Int]]
candidatos n = productoCartesiano [[i,-i] | i <- [1..n]]

-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo, 
--    λ> productoCartesiano [[1,3],[2,5],[6,4]]
--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano []       = [[]]
productoCartesiano (xs:xss) =
  [x:ys | x <- xs, ys <- productoCartesiano xss]

-- 2ª solución
-- ===========

ceros2 :: Int -> [[Int]]
ceros2 n = [xs | xs <- candidatos2 n, sum xs == 0]

candidatos2 :: Int -> [[Int]]
candidatos2 n = mapM (\i -> [i,-i]) [1..n]

-- 3ª solución
-- ===========

ceros3 :: Int -> [[Int]]
ceros3 n = [xs | xs <- mapM (\i -> [i,-i]) [1..n], sum xs == 0]

-- 4ª solución
-- ===========

ceros4 :: Integer -> [[Integer]]
ceros4 = map fst
       . filter ((==0) . snd)
       . sumas

-- (sumas n) es la lista de las candidatos con los n primeros números y
-- sus sumas. Por ejemplo,
--    λ> sumas 2
--    [([1,2],3),([-1,2],1),([1,-2],-1),([-1,-2],-3)]
--    λ> sumas 3
--    [([1,2,3],6),([-1,2,3],4),([1,-2,3],2),([-1,-2,3],0),([1,2,-3],0),
--     ([-1,2,-3],-2),([1,-2,-3],-4),([-1,-2,-3],-6)]
sumas :: Integer -> [([Integer],Integer)]
sumas = foldr aux [([], 0)]
      . enumFromTo 1
  where
    aux n = concatMap (\(ns', s') -> [(n : ns', s' + n), (-n : ns', s' - n)])

-- Comparación de eficiencia
-- =========================

--    λ> length (ceros 18)
--    0
--    (4.14 secs, 1,094,854,776 bytes)
--    λ> length (ceros2 18)
--    0
--    (1.16 secs, 375,541,680 bytes)
--    λ> length (ceros3 18)
--    0
--    (1.13 secs, 375,540,192 bytes)
--    λ> length (ceros4 18)
--    0
--    (0.69 secs, 157,316,688 bytes)

-- 1ª solución

-- ===========

ceros :: Int -> [[Int]]

ceros n = [xs | xs <- candidatos n, sum xs == 0]

-- (candidatos n) es la lista de los números del 1 al n con los signos

-- más o menos. Por ejemplo,

-- λ> candidatos 1

-- [[1],[-1]]

-- λ> candidatos 2

-- [[1,2],[1,-2],[-1,2],[-1,-2]]

-- λ> candidatos 3

-- [[1,2,3],[1,2,-3],[1,-2,3],[1,-2,-3],[-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]]

candidatos :: Int -> [[Int]]

candidatos n = productoCartesiano [[i,-i] | i <- [1..n]]

-- (productoCartesiano xss) es el producto cartesiano de los conjuntos

-- xss. Por ejemplo,

-- λ> productoCartesiano [[1,3],[2,5],[6,4]]

-- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]

productoCartesiano :: [[a]] -> [[a]]

productoCartesiano [] = [[]]

productoCartesiano (xs:xss) =

[x:ys | x <- xs, ys <- productoCartesiano xss]

-- 2ª solución

-- ===========

ceros2 :: Int -> [[Int]]

ceros2 n = [xs | xs <- candidatos2 n, sum xs == 0]

candidatos2 :: Int -> [[Int]]

candidatos2 n = mapM (\i -> [i,-i]) [1..n]

-- 3ª solución

-- ===========

ceros3 :: Int -> [[Int]]

ceros3 n = [xs | xs <- mapM (\i -> [i,-i]) [1..n], sum xs == 0]

-- 4ª solución

-- ===========

ceros4 :: Integer -> [[Integer]]

ceros4 = map fst

. filter ((==0) . snd)

. sumas

-- (sumas n) es la lista de las candidatos con los n primeros números y

-- sus sumas. Por ejemplo,

-- λ> sumas 2

-- [([1,2],3),([-1,2],1),([1,-2],-1),([-1,-2],-3)]

-- λ> sumas 3

-- [([1,2,3],6),([-1,2,3],4),([1,-2,3],2),([-1,-2,3],0),([1,2,-3],0),

-- ([-1,2,-3],-2),([1,-2,-3],-4),([-1,-2,-3],-6)]

sumas :: Integer -> [([Integer],Integer)]

sumas = foldr aux [([], 0)]

. enumFromTo 1

where

aux n = concatMap (\(ns', s') -> [(n : ns', s' + n), (-n : ns', s' - n)])

-- Comparación de eficiencia

-- =========================

-- λ> length (ceros 18)

-- 0

-- (4.14 secs, 1,094,854,776 bytes)

-- λ> length (ceros2 18)

-- 0

-- (1.16 secs, 375,541,680 bytes)

-- λ> length (ceros3 18)

-- 0

-- (1.13 secs, 375,540,192 bytes)

-- λ> length (ceros4 18)

-- 0

-- (0.69 secs, 157,316,688 bytes)

Menor potencia de 2 que comienza por n

PorJosé A. Alonso 22-febrero-201826-marzo-2022

Definir las funciones

   menorPotencia            :: Integer -> (Integer,Integer)
   graficaMenoresExponentes :: Integer -> IO ()

1 2	menorPotencia :: Integer -> (Integer,Integer) graficaMenoresExponentes :: Integer -> IO ()

tales que

(menorPotencia n) es el par (k,m) donde m es la menor potencia de 2 que empieza por n y k es su exponentes (es decir, 2^k = m). Por ejemplo,

     menorPotencia 3             ==  (5,32)
     menorPotencia 7             ==  (46,70368744177664)
     fst (menorPotencia 982)     ==  3973
     fst (menorPotencia 32627)   ==  28557
     fst (menorPotencia 158426)  ==  40000

menorPotencia 3 == (5,32)

menorPotencia 7 == (46,70368744177664)

fst (menorPotencia 982) == 3973

fst (menorPotencia 32627) == 28557

fst (menorPotencia 158426) == 40000

(graficaMenoresExponentes n) dibuja la gráfica de los exponentes de 2 en las menores potencias de los n primeros números enteros positivos. Por ejemplo, (graficaMenoresExponentes 200) dibuja

Soluciones

import Data.List               (isPrefixOf)
import Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)

-- 1ª definición
-- =============

menorPotencia :: Integer -> (Integer,Integer)
menorPotencia n =
  head [(k,m) | (k,m) <- zip [0..] potenciasDe2
              , cs `isPrefixOf` show m]
  where cs = show n

-- potenciasDe 2 es la lista de las potencias de dos. Por ejemplo,
--    take 12 potenciasDe2  ==  [1,2,4,8,16,32,64,128,256,512,1024,2048]
potenciasDe2 :: [Integer]
potenciasDe2 = iterate (*2) 1

-- 2ª definición 
-- =============

menorPotencia2 :: Integer -> (Integer,Integer)
menorPotencia2 n = aux (0,1)
  where aux (k,m) | cs `isPrefixOf` show m = (k,m)
                  | otherwise              = aux (k+1,2*m)
        cs = show n

-- 3ª definición 
-- =============

menorPotencia3 :: Integer -> (Integer,Integer)
menorPotencia3 n =
  until (isPrefixOf n1 . show . snd) (\(x,y) -> (x+1,2*y)) (0,1)
  where n1 = show n

-- Comparación de eficiencia
-- =========================

--    λ> maximum [fst (menorPotencia n) | n <- [1..1000]]
--    3973
--    (3.69 secs, 1,094,923,696 bytes)
--    λ> maximum [fst (menorPotencia2 n) | n <- [1..1000]]
--    3973
--    (5.13 secs, 1,326,382,872 bytes)
--    λ> maximum [fst (menorPotencia3 n) | n <- [1..1000]]
--    3973
--    (4.71 secs, 1,240,498,128 bytes)

graficaMenoresExponentes :: Integer -> IO ()
graficaMenoresExponentes n =
  plotList [ Key Nothing
           , PNG "Menor_potencia_de_2_que_comienza_por_n.png"
           ]
           (map (fst . menorPotencia) [1..n])

import Data.List (isPrefixOf)

import Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)

-- 1ª definición

-- =============

menorPotencia :: Integer -> (Integer,Integer)

menorPotencia n =

head [(k,m) | (k,m) <- zip [0..] potenciasDe2

, cs `isPrefixOf` show m]

where cs = show n

-- potenciasDe 2 es la lista de las potencias de dos. Por ejemplo,

-- take 12 potenciasDe2 == [1,2,4,8,16,32,64,128,256,512,1024,2048]

potenciasDe2 :: [Integer]

potenciasDe2 = iterate (*2) 1

-- 2ª definición

-- =============

menorPotencia2 :: Integer -> (Integer,Integer)

menorPotencia2 n = aux (0,1)

where aux (k,m) | cs `isPrefixOf` show m = (k,m)

| otherwise = aux (k+1,2*m)

cs = show n

-- 3ª definición

-- =============

menorPotencia3 :: Integer -> (Integer,Integer)

menorPotencia3 n =

until (isPrefixOf n1 . show . snd) (\(x,y) -> (x+1,2*y)) (0,1)

where n1 = show n

-- Comparación de eficiencia

-- =========================

-- λ> maximum [fst (menorPotencia n) | n <- [1..1000]]

-- 3973

-- (3.69 secs, 1,094,923,696 bytes)

-- λ> maximum [fst (menorPotencia2 n) | n <- [1..1000]]

-- 3973

-- (5.13 secs, 1,326,382,872 bytes)

-- λ> maximum [fst (menorPotencia3 n) | n <- [1..1000]]

-- 3973

-- (4.71 secs, 1,240,498,128 bytes)

graficaMenoresExponentes :: Integer -> IO ()

graficaMenoresExponentes n =

plotList [ Key Nothing

, PNG "Menor_potencia_de_2_que_comienza_por_n.png"

]

(map (fst . menorPotencia) [1..n])

Representación ampliada de matrices dispersas

PorJosé A. Alonso 21-febrero-201828-febrero-2018

En el ejercicio anterior se explicó una representación reducida de las matrices dispersas. A partir del número de columnas y la representación reducida se puede construir la matriz.

Definir la función

   ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a

1	ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a

tal que (ampliada n xss) es la matriz con n columnas cuya representación reducida es xss. Por ejemplo,

   λ> ampliada 3 [[(3,4)],[(2,5)],[]]
   ( 0 0 4 )
   ( 0 5 0 )
   ( 0 0 0 )
   
   λ> ampliada 3 [[],[]]
   ( 0 0 0 )
   ( 0 0 0 )
   
   λ> ampliada 2 [[],[],[]]
   ( 0 0 )
   ( 0 0 )
   ( 0 0 )

λ> ampliada 3 [[(3,4)],[(2,5)],[]]

( 0 0 4 )

( 0 5 0 )

( 0 0 0 )

λ> ampliada 3 [[],[]]

( 0 0 0 )

λ> ampliada 2 [[],[],[]]

( 0 0 )

Soluciones

import Data.Matrix (Matrix, fromLists)
import Data.List   (lookup)

ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a
ampliada n xss =
  fromLists [filaAmpliada n xs | xs <- xss]

-- Se puede redefinir con un argumento
ampliada2 :: Num a => Int -> [[(Int,a)]] -> Matrix a
ampliada2 n = fromLists . map (filaAmpliada n)

-- Se puede redefinir sin argumentos usando las siguientes reducciones
--      fromLists . map (filaAmpliada n)
--    = fromLists . ((map . filaAmpliada) n)
--    = ((fromLists .) . (map . filaAmpliada)) n
--    = ((fromLists .) . map . filaAmpliada) n
ampliada3 :: Num a => Int -> [[(Int,a)]] -> Matrix a
ampliada3 = (fromLists .) . map . filaAmpliada

-- (filaAmpliada n xs) es la fila ampliada de la representación reducida
-- xs de una matriz con n columnas. Por ejemplo, 
--    filaAmpliada 3 [(2,5)]        ==  [0,5,0]
--    filaAmpliada 7 [(2,5),(1,3)]  ==  [3,5,0,0,0,0,0]
filaAmpliada :: Num a => Int -> [(Int,a)] -> [a]
filaAmpliada n xs =
  [f (lookup i xs) | i <- [1..n]]
  where f Nothing  = 0
        f (Just x) = x

import Data.Matrix (Matrix, fromLists)

import Data.List (lookup)

ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a

ampliada n xss =

fromLists [filaAmpliada n xs | xs <- xss]

-- Se puede redefinir con un argumento

ampliada2 :: Num a => Int -> [[(Int,a)]] -> Matrix a

ampliada2 n = fromLists . map (filaAmpliada n)

-- Se puede redefinir sin argumentos usando las siguientes reducciones

-- fromLists . map (filaAmpliada n)

-- = fromLists . ((map . filaAmpliada) n)

-- = ((fromLists .) . (map . filaAmpliada)) n

-- = ((fromLists .) . map . filaAmpliada) n

ampliada3 :: Num a => Int -> [[(Int,a)]] -> Matrix a

ampliada3 = (fromLists .) . map . filaAmpliada

-- (filaAmpliada n xs) es la fila ampliada de la representación reducida

-- xs de una matriz con n columnas. Por ejemplo,

-- filaAmpliada 3 [(2,5)] == [0,5,0]

-- filaAmpliada 7 [(2,5),(1,3)] == [3,5,0,0,0,0,0]

filaAmpliada :: Num a => Int -> [(Int,a)] -> [a]

filaAmpliada n xs =

[f (lookup i xs) | i <- [1..n]]

where f Nothing = 0

f (Just x) = x

Vértices de un cuadrado

PorJosé A. Alonso 16-febrero-20187-marzo-2018

Definir la función

   esCuadrado :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a) -> (a,a) -> Bool

1	esCuadrado :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a) -> (a,a) -> Bool

tal que (esCuadrado p q r s) se verifica si los puntos p, q, r y s son los vértices de un cuadrado. Por ejemplo,

   esCuadrado (0,0) (0,1) (1,1) (1,0)    == True
   esCuadrado (0,0) (2,1) (3,-1) (1, -2) == True
   esCuadrado (0,0) (1,1) (0,1) (1,0)    == True
   esCuadrado (1,1) (1,1) (1,1) (1,1)    == True
   esCuadrado (0,0) (0,2) (3,2) (3,0)    == False
   esCuadrado (0,0) (3,4) (8,4) (5,0)    == False
   esCuadrado (0,0) (0,0) (1,1) (0,0)    == False
   esCuadrado (0,0) (0,0) (1,0) (0,1)    == False
   esCuadrado (0,0) (1,0) (0,1) (-1,-1)  == False

esCuadrado (0,0) (0,1) (1,1) (1,0) == True

esCuadrado (0,0) (2,1) (3,-1) (1, -2) == True

esCuadrado (0,0) (1,1) (0,1) (1,0) == True

esCuadrado (1,1) (1,1) (1,1) (1,1) == True

esCuadrado (0,0) (0,2) (3,2) (3,0) == False

esCuadrado (0,0) (3,4) (8,4) (5,0) == False

esCuadrado (0,0) (0,0) (1,1) (0,0) == False

esCuadrado (0,0) (0,0) (1,0) (0,1) == False

esCuadrado (0,0) (1,0) (0,1) (-1,-1) == False

Soluciones

import Data.List (sort, tails)

esCuadrado :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a) -> (a,a) -> Bool
esCuadrado p q r s = and [a == b, b == c, c == d, e == f, a + b == e]
  where [a,b,c,d,e,f] = sort (distancias p q r s)

-- (distancias p q r s) es la lista de los cuadrados de las longitudes
-- de los lados y de las diagonales del cuadrilátero cuyos vértices son
-- los puntos p, q, r y s. Por ejemplo,
--    distancias (0,0) (0,1) (1,1) (1,0)  ==  [1,2,1,1,2,1]
--    distancias (0,0) (3,4) (8,4) (5,0)  ==  [25,80,25,25,20,25]
--    distancias (0,0) (0,2) (3,2) (3,0)  ==  [4,13,9,9,13,4]
--    distancias (0,0) (0,0) (1,1) (0,0)  ==  [0,2,0,2,0,2]
--    distancias (0,0) (0,0) (1,0) (0,1)  ==  [0,1,1,1,1,2]
distancias :: Num a => (a,a) -> (a,a) -> (a,a) -> (a,a) -> [a]
distancias p q r s =
  [l | (h:t) <- tails [p,q,r,s], l <- map (dist h) t]

-- (dist p q) es el cuadrado de la distancia del punto p al q. Por
-- ejemplo,
--    dist (6,4) (3,8)  ==  25
dist :: Num a => (a,a) -> (a,a) -> a
dist (x1,y1) (x2,y2) = (x2-x1)^2 + (y2-y1)^2

import Data.List (sort, tails)

esCuadrado :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a) -> (a,a) -> Bool

esCuadrado p q r s = and [a == b, b == c, c == d, e == f, a + b == e]

where [a,b,c,d,e,f] = sort (distancias p q r s)

-- (distancias p q r s) es la lista de los cuadrados de las longitudes

-- de los lados y de las diagonales del cuadrilátero cuyos vértices son

-- los puntos p, q, r y s. Por ejemplo,

-- distancias (0,0) (0,1) (1,1) (1,0) == [1,2,1,1,2,1]

-- distancias (0,0) (3,4) (8,4) (5,0) == [25,80,25,25,20,25]

-- distancias (0,0) (0,2) (3,2) (3,0) == [4,13,9,9,13,4]

-- distancias (0,0) (0,0) (1,1) (0,0) == [0,2,0,2,0,2]

-- distancias (0,0) (0,0) (1,0) (0,1) == [0,1,1,1,1,2]

distancias :: Num a => (a,a) -> (a,a) -> (a,a) -> (a,a) -> [a]

distancias p q r s =

[l | (h:t) <- tails [p,q,r,s], l <- map (dist h) t]

-- (dist p q) es el cuadrado de la distancia del punto p al q. Por

-- ejemplo,

-- dist (6,4) (3,8) == 25

dist :: Num a => (a,a) -> (a,a) -> a

dist (x1,y1) (x2,y2) = (x2-x1)^2 + (y2-y1)^2

La función de Smarandache

Soluciones

Ceros con los n primeros números

Soluciones

Menor potencia de 2 que comienza por n

Soluciones

Representación ampliada de matrices dispersas

Soluciones

Vértices de un cuadrado

Soluciones

Entradas recientes

Buscar

Correo electrónico