Ejercicio

Caminos en un triángulo

PorJosé A. Alonso 14-febrero-202223-febrero-2022

Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo

7 4

2 4 6

8 5 9 3

se representa por

   [[3],[7,4],[2,4,6],[8,5,9,3]]

1	[[3],[7,4],[2,4,6],[8,5,9,3]]

Definir la función

   caminos :: [[a]] -> [[a]]

1	caminos :: [[a]] -> [[a]]

tal que (caminos xss) es la lista de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,

   λ> caminos [[3],[7,4]]
   [[3,7],[3,4]]
   λ> caminos [[3],[7,4],[2,4,6]]
   [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
   λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]]
   [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]

λ> caminos [[3],[7,4]]

[[3,7],[3,4]]

λ> caminos [[3],[7,4],[2,4,6]]

[[3,7,2],[3,7,4],[3,4,4],[3,4,6]]

λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]]

[[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]

Soluciones

caminos :: [[a]] -> [[a]]
caminos []    = [[]]
caminos [[x]] = [[x]]
caminos ([x]:[y1,y2]:zs) =
  [x:y1:us | (_:us) <- caminos ([y1] : map init zs)] ++
  [x:y2:vs | (_:vs) <- caminos ([y2] : map tail zs)]

caminos :: [[a]] -> [[a]]

caminos [] = [[]]

caminos [[x]] = [[x]]

caminos ([x]:[y1,y2]:zs) =

[x:y1:us | (_:us) <- caminos ([y1] : map init zs)] ++

[x:y2:vs | (_:vs) <- caminos ([y2] : map tail zs)]

El código se encuentra en GitHub.

Mayor órbita de la sucesión de Collatz

PorJosé A. Alonso 11-febrero-202215-abril-2022

Se considera la siguiente operación, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es

   13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

1	13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

Si observamos este ejemplo, la órbita de 13 es periódica, es decir, se repite indefinidamente a partir de un momento dado). La conjetura de Collatz dice que siempre alcanzaremos el 1 para cualquier número con el que comencemos. Por ejemplo,

Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta 9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Definir la función

   mayoresGeneradores :: Integer -> [Integer]

1	mayoresGeneradores :: Integer -> [Integer]

tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,

   mayoresGeneradores 20      ==  [18,19]
   mayoresGeneradores (10^6)  ==  [837799]

1 2	mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799]

Soluciones

import qualified Data.MemoCombinators as Memo (integral)
import Data.List (genericLength, genericTake, maximumBy)
import Test.QuickCheck (Positive(..), quickCheck)

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

mayoresGeneradores :: Integer -> [Integer]
mayoresGeneradores n =
  [x | (x,y) <- ps, y == m]
  where ps = genericTake n longitudesOrbitas
        m  = maximum (map snd ps)

-- longitudesOrbita es la lista de los números junto a las longitudes de
-- las órbitas de Collatz que generan. Por ejemplo,
--    λ> take 10 longitudesOrbitas
--    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]
longitudesOrbitas :: [(Integer, Integer)]
longitudesOrbitas =
  [(n, genericLength (collatz n)) | n <- [1..]]

-- (siguiente n) es el siguiente de n en la sucesión de Collatz. Por
-- ejemplo,
--    siguiente 13  ==  40
--    siguiente 40  ==  20
siguiente :: Integer -> Integer
siguiente n | even n    = n `div` 2
            | otherwise = 3*n+1

-- (collatz1 n) es la órbita de Collatz de n hasta alcanzar el
-- 1. Por ejemplo,
--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]

-- 1ª definición de collatz
collatz1 :: Integer -> [Integer]
collatz1 1 = [1]
collatz1 n = n : collatz1 (siguiente n)

-- 2ª definición de collatz
collatz2 :: Integer -> [Integer]
collatz2 n = takeWhile (/=1) (iterate siguiente n) ++ [1]

-- Usaremos la 2ª definición de collatz
collatz :: Integer -> [Integer]
collatz = collatz2

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

mayoresGeneradores2 :: Integer -> [Integer]
mayoresGeneradores2 n =
  [x | (x,y) <- ps, y == m]
  where ps = [(x, longitudOrbita x) | x <- [1..n]]
        m  = maximum (map snd ps)

-- (longitudOrbita x) es la longitud de la órbita de x. Por ejemplo,
--    longitudOrbita 13  ==  10
longitudOrbita :: Integer -> Integer
longitudOrbita 1 = 1
longitudOrbita x = 1 + longitudOrbita (siguiente x)

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

mayoresGeneradores3 :: Integer -> [Integer]
mayoresGeneradores3 n =
  [x | (x,y) <- ps, y == m]
  where ps = [(x, longitudOrbita2 x) | x <- [1..n]]
        m  = maximum (map snd ps)

longitudOrbita2 :: Integer -> Integer
longitudOrbita2 = Memo.integral longitudOrbita2'
  where
    longitudOrbita2' 1 = 1
    longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)


-- Equivalencia de definiciones
-- ============================

-- La propiedad es
prop_mayoresGeneradores :: (Positive Integer) -> Bool
prop_mayoresGeneradores (Positive n) =
  all (== (mayoresGeneradores n))
      [mayoresGeneradores2 n,
       mayoresGeneradores3 n]

-- La comprobación es
--    λ> quickCheck prop_mayoresGeneradores
--    +++ OK, passed 100 tests.

-- Comprobación de eficiencia
-- ==========================

-- La comprobación es
--    λ> mayoresGeneradores (10^5)
--    [77031]
--    (5.43 secs, 6,232,320,064 bytes)
--    λ> mayoresGeneradores2 (10^5)
--    [77031]
--    (7.68 secs, 5,238,991,616 bytes)
--    λ> mayoresGeneradores3 (10^5)
--    [77031]
--    (0.88 secs, 571,788,736 bytes)

100

101

102

103

104

import qualified Data.MemoCombinators as Memo (integral)

import Data.List (genericLength, genericTake, maximumBy)

import Test.QuickCheck (Positive(..), quickCheck)

-- 1ª solución

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

mayoresGeneradores :: Integer -> [Integer]

mayoresGeneradores n =

[x | (x,y) <- ps, y == m]

where ps = genericTake n longitudesOrbitas

m = maximum (map snd ps)

-- longitudesOrbita es la lista de los números junto a las longitudes de

-- las órbitas de Collatz que generan. Por ejemplo,

-- λ> take 10 longitudesOrbitas

-- [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]

longitudesOrbitas :: [(Integer, Integer)]

longitudesOrbitas =

[(n, genericLength (collatz n)) | n <- [1..]]

-- (siguiente n) es el siguiente de n en la sucesión de Collatz. Por

-- ejemplo,

-- siguiente 13 == 40

-- siguiente 40 == 20

siguiente :: Integer -> Integer

siguiente n | even n = n `div` 2

| otherwise = 3*n+1

-- (collatz1 n) es la órbita de Collatz de n hasta alcanzar el

-- 1. Por ejemplo,

-- collatz 13 == [13,40,20,10,5,16,8,4,2,1]

-- 1ª definición de collatz

collatz1 :: Integer -> [Integer]

collatz1 1 = [1]

collatz1 n = n : collatz1 (siguiente n)

-- 2ª definición de collatz

collatz2 :: Integer -> [Integer]

collatz2 n = takeWhile (/=1) (iterate siguiente n) ++ [1]

-- Usaremos la 2ª definición de collatz

collatz :: Integer -> [Integer]

collatz = collatz2

-- 2ª solución

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

mayoresGeneradores2 :: Integer -> [Integer]

mayoresGeneradores2 n =

[x | (x,y) <- ps, y == m]

where ps = [(x, longitudOrbita x) | x <- [1..n]]

m = maximum (map snd ps)

-- (longitudOrbita x) es la longitud de la órbita de x. Por ejemplo,

-- longitudOrbita 13 == 10

longitudOrbita :: Integer -> Integer

longitudOrbita 1 = 1

longitudOrbita x = 1 + longitudOrbita (siguiente x)

-- 3ª solución

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

mayoresGeneradores3 :: Integer -> [Integer]

mayoresGeneradores3 n =

[x | (x,y) <- ps, y == m]

where ps = [(x, longitudOrbita2 x) | x <- [1..n]]

m = maximum (map snd ps)

longitudOrbita2 :: Integer -> Integer

longitudOrbita2 = Memo.integral longitudOrbita2'

where

longitudOrbita2' 1 = 1

longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)

-- Equivalencia de definiciones

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

-- La propiedad es

prop_mayoresGeneradores :: (Positive Integer) -> Bool

prop_mayoresGeneradores (Positive n) =

all (== (mayoresGeneradores n))

[mayoresGeneradores2 n,

mayoresGeneradores3 n]

-- La comprobación es

-- λ> quickCheck prop_mayoresGeneradores

-- +++ OK, passed 100 tests.

-- Comprobación de eficiencia

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

-- La comprobación es

-- λ> mayoresGeneradores (10^5)

-- [77031]

-- (5.43 secs, 6,232,320,064 bytes)

-- λ> mayoresGeneradores2 (10^5)

-- [77031]

-- (7.68 secs, 5,238,991,616 bytes)

-- λ> mayoresGeneradores3 (10^5)

-- [77031]

-- (0.88 secs, 571,788,736 bytes)

El código se encuentra en GitHub.

Ternas pitagóricas con suma dada

PorJosé A. Alonso 10-febrero-202213-octubre-2022

Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a^2+b^2=c^2. Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

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

1	ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

   ternasPitagoricas 12     == [(3,4,5)]
   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

ternasPitagoricas 12 == [(3,4,5)]

ternasPitagoricas 60 == [(10,24,26),(15,20,25)]

ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Soluciones

import Data.List (nub,sort)
import Test.QuickCheck

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

ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas1 x =
  [(a,b,c) | a <- [0..x],
             b <- [a+1..x],
             c <- [b+1..x],
             a^2 + b^2 == c^2,
             a+b+c == x]

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

ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas2 x =
  [(a,b,c) | a <- [1..x],
             b <- [a+1..x-a],
             let c = x-a-b,
             a^2+b^2 == c^2]

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

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse
-- por
--    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,
-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas3 x =
  nub [(d*a,d*b,d*c) | d <- [1..x],
                       x `mod` d == 0,
                      (a,b,c) <- aux (x `div` d)]
  where
    aux y = [(a,b,c) | m <- [2..limite],
                       n <- [1..m-1],
                       let [a,b] = sort [m^2 - n^2, 2*m*n],
                       let c = m^2 + n^2,
                       a+b+c == y]
      where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_ternasPitagoricas :: Positive Integer -> Bool
prop_ternasPitagoricas (Positive x) =
  all (== (ternasPitagoricas1 x))
      [ternasPitagoricas2 x,
       ternasPitagoricas3 x]

-- La comprobación es
--    λ> quickCheck prop_ternasPitagoricas
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> ternasPitagoricas1 200
--    [(40,75,85)]
--    (1.90 secs, 2,404,800,856 bytes)
--    λ> ternasPitagoricas2 200
--    [(40,75,85)]
--    (0.06 secs, 19,334,232 bytes)
--    λ> ternasPitagoricas3 200
--    [(40,75,85)]
--    (0.01 secs, 994,224 bytes)
--
--    λ> ternasPitagoricas2 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (4.41 secs, 4,354,148,136 bytes)
--    λ> ternasPitagoricas3 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (0.05 secs, 17,110,360 bytes)

import Data.List (nub,sort)

import Test.QuickCheck

-- 1ª solución --

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

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

ternasPitagoricas1 x =

[(a,b,c) | a <- [0..x],

b <- [a+1..x],

c <- [b+1..x],

a^2 + b^2 == c^2,

a+b+c == x]

-- 2ª solución --

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

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

ternasPitagoricas2 x =

[(a,b,c) | a <- [1..x],

b <- [a+1..x-a],

let c = x-a-b,

a^2+b^2 == c^2]

-- 3ª solución --

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

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse

-- por

-- a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,

-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

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

ternasPitagoricas3 x =

nub [(d*a,d*b,d*c) | d <- [1..x],

x `mod` d == 0,

(a,b,c) <- aux (x `div` d)]

where

aux y = [(a,b,c) | m <- [2..limite],

n <- [1..m-1],

let [a,b] = sort [m^2 - n^2, 2*m*n],

let c = m^2 + n^2,

a+b+c == y]

where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_ternasPitagoricas :: Positive Integer -> Bool

prop_ternasPitagoricas (Positive x) =

all (== (ternasPitagoricas1 x))

[ternasPitagoricas2 x,

ternasPitagoricas3 x]

-- La comprobación es

-- λ> quickCheck prop_ternasPitagoricas

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> ternasPitagoricas1 200

-- [(40,75,85)]

-- (1.90 secs, 2,404,800,856 bytes)

-- λ> ternasPitagoricas2 200

-- [(40,75,85)]

-- (0.06 secs, 19,334,232 bytes)

-- λ> ternasPitagoricas3 200

-- [(40,75,85)]

-- (0.01 secs, 994,224 bytes)

-- λ> ternasPitagoricas2 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (4.41 secs, 4,354,148,136 bytes)

-- λ> ternasPitagoricas3 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (0.05 secs, 17,110,360 bytes)

El código se encuentra en GitHub.

Suma de múltiplos de 3 o de 5

PorJosé A. Alonso 9-febrero-202223-febrero-2022

Los números naturales menores que 10 que son múltiplos de 3 ó 5 son 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Definir la función

   sumaMultiplos :: Integer -> Integer

1	sumaMultiplos :: Integer -> Integer

tal que (sumaMultiplos n) es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

   sumaMultiplos 10      ==  23
   sumaMultiplos (10^2)  ==  2318
   sumaMultiplos (10^3)  ==  233168
   sumaMultiplos (10^4)  ==  23331668
   sumaMultiplos (10^5)  ==  2333316668
   sumaMultiplos (10^6)  ==  233333166668
   sumaMultiplos (10^7)  ==  23333331666668

sumaMultiplos 10 == 23

sumaMultiplos (10^2) == 2318

sumaMultiplos (10^3) == 233168

sumaMultiplos (10^4) == 23331668

sumaMultiplos (10^5) == 2333316668

sumaMultiplos (10^6) == 233333166668

sumaMultiplos (10^7) == 23333331666668

Soluciones

import Data.List (nub, union)
import Test.QuickCheck (Positive(..), quickCheck)

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

sumaMultiplos1 :: Integer -> Integer
sumaMultiplos1 n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es múltiplo de y. Por ejemplo,
--    multiplo 6 3  ==  True
--    multiplo 6 4  ==  False
multiplo :: Integer -> Integer -> Bool
multiplo x y = mod x y == 0

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

sumaMultiplos2 :: Integer -> Integer
sumaMultiplos2 n = sum [x | x <- [1..n-1], gcd x 15 > 1]

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

sumaMultiplos3 :: Integer -> Integer
sumaMultiplos3 n = sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

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

sumaMultiplos4 :: Integer -> Integer
sumaMultiplos4 n = sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución                                                        --
-- ===========

sumaMultiplos5 :: Integer -> Integer
sumaMultiplos5 n = sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución                                                      --
-- ===========

sumaMultiplos6 :: Integer -> Integer
sumaMultiplos6 n = suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por
-- ejemplo,
--    suma 3 10  ==  18
--    suma 5 10  ==  5
suma :: Integer -> Integer -> Integer
suma d x = (a+b)*n `div` 2
    where a = d
          b = d * ((x-1) `div` d)
          n = 1 + (b-a) `div` d

-- Equivalencia de definiciones
-- ============================

-- La propiedad es
prop_sumaMultiplos :: Positive Integer -> Bool
prop_sumaMultiplos (Positive n) =
  all (== (sumaMultiplos1 n))
      [f n | f <- [sumaMultiplos1,
                   sumaMultiplos2,
                   sumaMultiplos3,
                   sumaMultiplos4,
                   sumaMultiplos5,
                   sumaMultiplos6]]

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

-- La comparación es
--    λ> sumaMultiplos1 (5*10^4)
--    583291668
--    (0.05 secs, 21,446,456 bytes)
--    λ> sumaMultiplos2 (5*10^4)
--    583291668
--    (0.05 secs, 26,804,944 bytes)
--    λ> sumaMultiplos3 (5*10^4)
--    583291668
--    (0.01 secs, 5,136,728 bytes)
--    λ> sumaMultiplos4 (5*10^4)
--    583291668
--    (3.05 secs, 7,474,304 bytes)
--    λ> sumaMultiplos5 (5*10^4)
--    583291668
--    (5.14 secs, 12,787,717,152 bytes)
--    λ> sumaMultiplos6 (5*10^4)
--    583291668
--    (0.01 secs, 108,448 bytes)
--
--    λ> sumaMultiplos1 (3*10^6)
--    2099998500000
--    (2.14 secs, 1,281,805,696 bytes)
--    λ> sumaMultiplos2 (3*10^6)
--    2099998500000
--    (1.86 secs, 1,603,407,272 bytes)
--    λ> sumaMultiplos3 (3*10^6)
--    2099998500000
--    (0.39 secs, 304,681,080 bytes)
--    λ> sumaMultiplos6 (3*10^6)
--    2099998500000
--    (0.01 secs, 112,544 bytes)
--
--    λ> sumaMultiplos3 (10^7)
--    23333331666668
--    (1.69 secs, 1,015,468,352 bytes)
--    λ> sumaMultiplos6 (10^7)
--    23333331666668
--    (0.01 secs, 112,336 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

import Data.List (nub, union)

import Test.QuickCheck (Positive(..), quickCheck)

-- 1ª solución

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

sumaMultiplos1 :: Integer -> Integer

sumaMultiplos1 n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5]

-- (multiplo x y) se verifica si x es múltiplo de y. Por ejemplo,

-- multiplo 6 3 == True

-- multiplo 6 4 == False

multiplo :: Integer -> Integer -> Bool

multiplo x y = mod x y == 0

-- 2ª solución --

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

sumaMultiplos2 :: Integer -> Integer

sumaMultiplos2 n = sum [x | x <- [1..n-1], gcd x 15 > 1]

-- 3ª solución --

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

sumaMultiplos3 :: Integer -> Integer

sumaMultiplos3 n = sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]

-- 4ª solución --

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

sumaMultiplos4 :: Integer -> Integer

sumaMultiplos4 n = sum (nub ([3,6..n-1] ++ [5,10..n-1]))

-- 5ª solución --

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

sumaMultiplos5 :: Integer -> Integer

sumaMultiplos5 n = sum ([3,6..n-1] `union` [5,10..n-1])

-- 6ª solución --

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

sumaMultiplos6 :: Integer -> Integer

sumaMultiplos6 n = suma 3 n + suma 5 n - suma 15 n

-- (suma d x) es la suma de los múltiplos de d menores que x. Por

-- ejemplo,

-- suma 3 10 == 18

-- suma 5 10 == 5

suma :: Integer -> Integer -> Integer

suma d x = (a+b)*n `div` 2

where a = d

b = d * ((x-1) `div` d)

n = 1 + (b-a) `div` d

-- Equivalencia de definiciones

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

-- La propiedad es

prop_sumaMultiplos :: Positive Integer -> Bool

prop_sumaMultiplos (Positive n) =

all (== (sumaMultiplos1 n))

[f n | f <- [sumaMultiplos1,

sumaMultiplos2,

sumaMultiplos3,

sumaMultiplos4,

sumaMultiplos5,

sumaMultiplos6]]

-- Comparación de eficiencia

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

-- La comparación es

-- λ> sumaMultiplos1 (5*10^4)

-- 583291668

-- (0.05 secs, 21,446,456 bytes)

-- λ> sumaMultiplos2 (5*10^4)

-- 583291668

-- (0.05 secs, 26,804,944 bytes)

-- λ> sumaMultiplos3 (5*10^4)

-- 583291668

-- (0.01 secs, 5,136,728 bytes)

-- λ> sumaMultiplos4 (5*10^4)

-- 583291668

-- (3.05 secs, 7,474,304 bytes)

-- λ> sumaMultiplos5 (5*10^4)

-- 583291668

-- (5.14 secs, 12,787,717,152 bytes)

-- λ> sumaMultiplos6 (5*10^4)

-- 583291668

-- (0.01 secs, 108,448 bytes)

-- λ> sumaMultiplos1 (3*10^6)

-- 2099998500000

-- (2.14 secs, 1,281,805,696 bytes)

-- λ> sumaMultiplos2 (3*10^6)

-- 2099998500000

-- (1.86 secs, 1,603,407,272 bytes)

-- λ> sumaMultiplos3 (3*10^6)

-- 2099998500000

-- (0.39 secs, 304,681,080 bytes)

-- λ> sumaMultiplos6 (3*10^6)

-- 2099998500000

-- (0.01 secs, 112,544 bytes)

-- λ> sumaMultiplos3 (10^7)

-- 23333331666668

-- (1.69 secs, 1,015,468,352 bytes)

-- λ> sumaMultiplos6 (10^7)

-- 23333331666668

-- (0.01 secs, 112,336 bytes)

El código se encuentra en GitHub.

Exponente en la factorización

PorJosé A. Alonso 8-febrero-202215-abril-2022

Definir la función

   exponente :: Integer -> Integer -> Int

1	exponente :: Integer -> Integer -> Int

tal que (exponente x n) es el exponente de x en la factorizacón prima de n (se supone que x > 1 y n > 0). Por ejemplo,

   exponente 2 24  ==  3
   exponente 3 24  ==  1
   exponente 6 24  ==  0
   exponente 7 24  ==  0

exponente 2 24 == 3

exponente 3 24 == 1

exponente 6 24 == 0

exponente 7 24 == 0

Soluciones

import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck

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

exponente1 :: Integer -> Integer -> Int
exponente1 x n
  | esPrimo x = aux n
  | otherwise = 0
  where aux m | m `mod` x == 0 = 1 + aux (m `div` x)
              | otherwise      = 0

-- (esPrimo x) se verifica si x es un número primo. Por ejemplo,
--    esPrimo 7  ==  True
--    esPrimo 8  ==  False
esPrimo :: Integer -> Bool
esPrimo x =
  [y | y <- [1..x], x `mod` y == 0] == [1,x]

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

exponente2 :: Integer -> Integer -> Int
exponente2 x n
  | esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))
  | otherwise = 0

-- (divisible n x) se verifica si ne divisible por x. Por ejemplo,
--    divisible 6 2  ==  True
--    divisible 7 2  ==  False
divisible :: Integer -> Integer -> Bool
divisible n x = n `mod` x == 0

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

exponente3 :: Integer -> Integer -> Int
exponente3 x n =
  length (filter (==x) (primeFactors n))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_exponente :: Integer -> Integer -> Property
prop_exponente x n =
  x > 1 && n > 0 ==>
  exponente1 x n == exponente2 x n &&
  exponente1 x n == exponente3 x n

-- La comprobación es
--    λ> quickCheck prop_exponente
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

-- 1ª solución

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

exponente1 :: Integer -> Integer -> Int

exponente1 x n

| esPrimo x = aux n

| otherwise = 0

where aux m | m `mod` x == 0 = 1 + aux (m `div` x)

| otherwise = 0

-- (esPrimo x) se verifica si x es un número primo. Por ejemplo,

-- esPrimo 7 == True

-- esPrimo 8 == False

esPrimo :: Integer -> Bool

esPrimo x =

[y | y <- [1..x], x `mod` y == 0] == [1,x]

-- 2ª solución

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

exponente2 :: Integer -> Integer -> Int

exponente2 x n

| esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))

| otherwise = 0

-- (divisible n x) se verifica si ne divisible por x. Por ejemplo,

-- divisible 6 2 == True

-- divisible 7 2 == False

divisible :: Integer -> Integer -> Bool

divisible n x = n `mod` x == 0

-- 3ª solución

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

exponente3 :: Integer -> Integer -> Int

exponente3 x n =

length (filter (==x) (primeFactors n))

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_exponente :: Integer -> Integer -> Property

prop_exponente x n =

x > 1 && n > 0 ==>

exponente1 x n == exponente2 x n &&

exponente1 x n == exponente3 x n

-- La comprobación es

-- λ> quickCheck prop_exponente

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Caminos en un triángulo

Soluciones

Mayor órbita de la sucesión de Collatz

Soluciones

Ternas pitagóricas con suma dada

Soluciones

Suma de múltiplos de 3 o de 5

Soluciones

Exponente en la factorización

Soluciones

Entradas recientes

Buscar

Correo electrónico