agosto 2022 – Exercitium

División segura

PorJosé A. Alonso 31-agosto-202214-diciembre-2022

Definir la función

   divisionSegura :: Double -> Double -> Double

1	divisionSegura :: Double -> Double -> Double

tal que (divisionSegura x y) es x/y si y no es cero y 9999 en caso contrario. Por ejemplo,

   divisionSegura 7 2  ==  3.5
   divisionSegura 7 0  ==  9999.0

1 2	divisionSegura 7 2 == 3.5 divisionSegura 7 0 == 9999.0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición
divisionSegura1 :: Double -> Double -> Double
divisionSegura1 x y =
  if y == 0 then 9999 else x/y

-- 2ª definición
divisionSegura2 :: Double -> Double -> Double
divisionSegura2 _ 0 = 9999
divisionSegura2 x y = x/y

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_divisionSegura :: Double -> Double -> Bool
prop_divisionSegura x y =
  divisionSegura1 x y == divisionSegura2 x y

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

import Test.QuickCheck

-- 1ª definición

divisionSegura1 :: Double -> Double -> Double

divisionSegura1 x y =

if y == 0 then 9999 else x/y

-- 2ª definición

divisionSegura2 :: Double -> Double -> Double

divisionSegura2 _ 0 = 9999

divisionSegura2 x y = x/y

-- Comprobación de equivalencia

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

-- La propiedad es

prop_divisionSegura :: Double -> Double -> Bool

prop_divisionSegura x y =

divisionSegura1 x y == divisionSegura2 x y

-- La comprobación es

-- λ> quickCheck prop_divisionSegura

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from hypothesis import given, strategies as st

# 1ª definición
def divisionSegura1(x: float, y: float) -> float:
    if y == 0:
        return 9999.0
    return x/y

# 2ª definición
def divisionSegura2(x: float, y: float) -> float:
    match y:
        case 0:
            return 9999.0
        case _:
            return x/y

# La propiedad de equivalencia es
@given(st.floats(allow_nan=False, allow_infinity=False),
       st.floats(allow_nan=False, allow_infinity=False))
def test_equiv_divisionSegura(x, y):
    assert divisionSegura1(x, y) == divisionSegura2(x, y)

# La comprobación es
#    src> poetry run pytest -q division_segura.py
#    1 passed in 0.37s

from hypothesis import given, strategies as st

# 1ª definición

def divisionSegura1(x: float, y: float) -> float:

if y == 0:

return 9999.0

return x/y

# 2ª definición

def divisionSegura2(x: float, y: float) -> float:

match y:

case 0:

return 9999.0

case _:

return x/y

# La propiedad de equivalencia es

@given(st.floats(allow_nan=False, allow_infinity=False),

st.floats(allow_nan=False, allow_infinity=False))

def test_equiv_divisionSegura(x, y):

assert divisionSegura1(x, y) == divisionSegura2(x, y)

# La comprobación es

# src> poetry run pytest -q division_segura.py

# 1 passed in 0.37s

El código se encuentra en GitHub.

Comentarios

El condicional se escribe en Haskell como

if <condición> then <valor1> else <valor2>

1	if <condición> then <valor1> else <valor2>

y en Python como

if <condición>:
    return <valor1>
return <valor2>

if <condición>:

return <valor1>

return <valor2>

Una alternativa al uso de los condicionales son los patrones que en Haskell se escribe en los argumentos de las ecuaciones y en Python con match cases.

Tres diferentes

PorJosé A. Alonso 30-agosto-202214-diciembre-2022

Definir la función

   tresDiferentes :: Int -> Int -> Int -> Bool

1	tresDiferentes :: Int -> Int -> Int -> Bool

tal que (tresDiferentes x y z) se verifica si los elementos x, y y z son distintos. Por ejemplo,

   tresDiferentes 3 5 2  ==  True
   tresDiferentes 3 5 3  ==  False

1 2	tresDiferentes 3 5 2 == True tresDiferentes 3 5 3 == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

tresDiferentes :: Int -> Int -> Int -> Bool
tresDiferentes x y z = x /= y && x /= z && y /= z

1 2	tresDiferentes :: Int -> Int -> Int -> Bool tresDiferentes x y z = x /= y && x /= z && y /= z

El código se encuentra en GitHub.

Soluciones en Python

def tresDiferentes(x: int, y: int, z: int) -> bool:
    return x != y and x != z and y != z

1 2	def tresDiferentes(x: int, y: int, z: int) -> bool: return x != y and x != z and y != z

El código se encuentra en GitHub.

Comentarios

Para decidir si x e y son distintos, se escribe
- x /= y en Haskell y
- x != y en Python.

Tres iguales

PorJosé A. Alonso 29-agosto-202214-diciembre-2022

Definir la función

   tresIguales :: Int -> Int -> Int -> Bool

1	tresIguales :: Int -> Int -> Int -> Bool

tal que (tresIguales x y z) se verifica si los elementos x, y y z son iguales. Por ejemplo,

   tresIguales 4 4 4  ==  True
   tresIguales 4 3 4  ==  False

1 2	tresIguales 4 4 4 == True tresIguales 4 3 4 == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

tresIguales :: Int -> Int -> Int -> Bool
tresIguales x y z = x == y && y == z

1 2	tresIguales :: Int -> Int -> Int -> Bool tresIguales x y z = x == y && y == z

El código se encuentra en GitHub.

Soluciones en Python

from hypothesis import given, strategies as st

# 1ª definición
def tresIguales1(x: int, y: int, z: int) -> bool:
    return x == y and y == z

# 2ª definición
def tresIguales2(x: int, y: int, z: int) -> bool:
    return x == y == z

# La propiedad de equivalencia es
@given(st.integers(), st.integers(), st.integers())
def test_equiv_tresIguales(x, y, z):
    assert tresIguales1(x, y, z) == tresIguales2(x, y, z)

# La comprobación es
#    src> poetry run pytest -q tres_iguales.py
#    1 passed in 0.16s

from hypothesis import given, strategies as st

# 1ª definición

def tresIguales1(x: int, y: int, z: int) -> bool:

return x == y and y == z

# 2ª definición

def tresIguales2(x: int, y: int, z: int) -> bool:

return x == y == z

# La propiedad de equivalencia es

@given(st.integers(), st.integers(), st.integers())

def test_equiv_tresIguales(x, y, z):

assert tresIguales1(x, y, z) == tresIguales2(x, y, z)

# La comprobación es

# src> poetry run pytest -q tres_iguales.py

# 1 passed in 0.16s

El código se encuentra en GitHub.

Comentarios

La conjunción de x e y se calcula
- en Haskell, con x && y y
- en Python, con x and y.
En Python, x == y == z es equivalente a x == y and y == z.

Primeros y últimos elementos

PorJosé A. Alonso 25-agosto-202214-diciembre-2022

Definir la función

   extremos :: Int -> [a] -> [a]

1	extremos :: Int -> [a] -> [a]

tal que (extremos n xs) es la lista formada por los n primeros elementos de xs y los n finales elementos de xs. Por ejemplo,

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

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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

extremos :: Int -> [a] -> [a]
extremos n xs = take n xs ++ drop (length xs - n) xs

1 2	extremos :: Int -> [a] -> [a] extremos n xs = take n xs ++ drop (length xs - n) xs

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar

A = TypeVar('A')

def extremos(n: int, xs: list[A]) -> list[A]:
    return xs[:n] + xs[-n:]

from typing import TypeVar

A = TypeVar('A')

def extremos(n: int, xs: list[A]) -> list[A]:

return xs[:n] + xs[-n:]

El código se encuentra en GitHub.

Segmento de una lista

PorJosé A. Alonso 24-agosto-202214-diciembre-2022

Definir la función

   segmento :: Int -> Int -> [a] -> [a]

1	segmento :: Int -> Int -> [a] -> [a]

tal que (segmento m n xs) es la lista de los elementos de xs comprendidos entre las posiciones m y n. Por ejemplo,

   segmento 3 4 [3,4,1,2,7,9,0]  ==  [1,2]
   segmento 3 5 [3,4,1,2,7,9,0]  ==  [1,2,7]
   segmento 5 3 [3,4,1,2,7,9,0]  ==  []

segmento 3 4 [3,4,1,2,7,9,0] == [1,2]

segmento 3 5 [3,4,1,2,7,9,0] == [1,2,7]

segmento 5 3 [3,4,1,2,7,9,0] == []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

segmento :: Int -> Int -> [a] -> [a]
segmento m n xs = drop (m-1) (take n xs)

1 2	segmento :: Int -> Int -> [a] -> [a] segmento m n xs = drop (m-1) (take n xs)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# 1ª definición
def segmento1(m: int, n: int, xs: list[A]) -> list[A]:
    ys = xs[:n]
    if m == 0:
        return ys
    return ys[m - 1:]

# 2ª definición
def segmento2(m: int, n: int, xs: list[A]) -> list[A]:
    if m == 0:
        return xs[:n]
    return xs[m-1:n]

# La propiedad de equivalencia es
@given(st.integers(min_value=0),
       st.integers(min_value=0),
       st.lists(st.integers()))
def test_equiv_segmento(m: int, n: int, xs: list[int]) -> None:
    assert segmento1(m, n, xs) == segmento2(m, n, xs)

# La comprobación es
#    src> poetry run pytest -q segmento_de_una_lista.py
#    1 passed in 0.19s

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# 1ª definición

def segmento1(m: int, n: int, xs: list[A]) -> list[A]:

ys = xs[:n]

if m == 0:

return ys

return ys[m - 1:]

# 2ª definición

def segmento2(m: int, n: int, xs: list[A]) -> list[A]:

if m == 0:

return xs[:n]

return xs[m-1:n]

# La propiedad de equivalencia es

@given(st.integers(min_value=0),

st.integers(min_value=0),

st.lists(st.integers()))

def test_equiv_segmento(m: int, n: int, xs: list[int]) -> None:

assert segmento1(m, n, xs) == segmento2(m, n, xs)

# La comprobación es

# src> poetry run pytest -q segmento_de_una_lista.py

# 1 passed in 0.19s

El código se encuentra en GitHub.

Elementos finales

PorJosé A. Alonso 23-agosto-202214-diciembre-2022

Definir la función

   finales :: Int -> [a] -> [a]

1	finales :: Int -> [a] -> [a]

tal que (finales n xs) es la lista formada por los n finales elementos de xs. Por ejemplo,

   finales 3 [2,5,4,7,9,6]  ==  [7,9,6]

1	finales 3 [2,5,4,7,9,6] == [7,9,6]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición
finales1 :: Int -> [a] -> [a]
finales1 n xs = drop (length xs - n) xs

-- 2ª definición
finales2 :: Int -> [a] -> [a]
finales2 n xs = reverse (take n (reverse xs))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_finales :: Int -> [Int] -> Bool
prop_finales n xs =
  finales1 n xs == finales2 n xs

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

import Test.QuickCheck

-- 1ª definición

finales1 :: Int -> [a] -> [a]

finales1 n xs = drop (length xs - n) xs

-- 2ª definición

finales2 :: Int -> [a] -> [a]

finales2 n xs = reverse (take n (reverse xs))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_finales :: Int -> [Int] -> Bool

prop_finales n xs =

finales1 n xs == finales2 n xs

-- La comprobación es

-- λ> quickCheck prop_finales

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub

Soluciones en Python

from typing import TypeVar
from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª definición
def finales1(n: int, xs: list[A]) -> list[A]:
    if len(xs) <= n:
        return xs
    return xs[len(xs) - n:]

# 2ª definición
def finales2(n: int, xs: list[A]) -> list[A]:
    if n == 0:
        return []
    return xs[-n:]

# 3ª definición
def finales3(n: int, xs: list[A]) -> list[A]:
    ys = list(reversed(xs))
    return list(reversed(ys[:n]))

# La propiedad de equivalencia es
@given(st.integers(min_value=0), st.lists(st.integers()))
def test_equiv_finales(n, xs):
    assert finales1(n, xs) == finales2(n, xs) == finales3(n, xs)

# La comprobación es
#    src> poetry run pytest -q elementos_finales.py
#    1 passed in 0.18s

from typing import TypeVar

from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª definición

def finales1(n: int, xs: list[A]) -> list[A]:

if len(xs) <= n:

return xs

return xs[len(xs) - n:]

# 2ª definición

def finales2(n: int, xs: list[A]) -> list[A]:

if n == 0:

return []

return xs[-n:]

# 3ª definición

def finales3(n: int, xs: list[A]) -> list[A]:

ys = list(reversed(xs))

return list(reversed(ys[:n]))

# La propiedad de equivalencia es

@given(st.integers(min_value=0), st.lists(st.integers()))

def test_equiv_finales(n, xs):

assert finales1(n, xs) == finales2(n, xs) == finales3(n, xs)

# La comprobación es

# src> poetry run pytest -q elementos_finales.py

# 1 passed in 0.18s

El código se encuentra en GitHub

Comentarios

La longitud de la lista xs se calcula
- en Haskell, con length xs y
- en Python, con len(xs).

Interior de una lista

PorJosé A. Alonso 22-agosto-202214-diciembre-2022

Definir la función

   interior :: [a] -> [a]

1	interior :: [a] -> [a]

tal que (interior xs) es la lista obtenida eliminando los extremos de la lista xs. Por ejemplo,

   interior [2,5,3,7,3]  ==  [5,3,7]
   interior [2..7]       ==  [3,4,5,6]

1 2	interior [2,5,3,7,3] == [5,3,7] interior [2..7] == [3,4,5,6]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

interior :: [a] -> [a]
interior xs = tail (init xs)

1 2	interior :: [a] -> [a] interior xs = tail (init xs)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª solución
def interior1(xs: list[A]) -> list[A]:
    return xs[1:][:-1]

# 2ª solución
def interior2(xs: list[A]) -> list[A]:
    return xs[1:-1]

# La propiedad de equivalencia es
@given(st.lists(st.integers()))
def test_triangular(xs):
    assert interior1(xs) == interior2(xs)

# La comprobación es
#    src> poetry run pytest -q interior_de_una_lista.py
#    1 passed in 0.21s

from typing import TypeVar

from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª solución

def interior1(xs: list[A]) -> list[A]:

return xs[1:][:-1]

# 2ª solución

def interior2(xs: list[A]) -> list[A]:

return xs[1:-1]

# La propiedad de equivalencia es

@given(st.lists(st.integers()))

def test_triangular(xs):

assert interior1(xs) == interior2(xs)

# La comprobación es

# src> poetry run pytest -q interior_de_una_lista.py

# 1 passed in 0.21s

El código se encuentra en GitHub.

Comentarios

Los elementos iniciales de una lista xs se calcula
- en Haskell, con init xs y
- en Python, con xs[:-1].

Reconocimiento de palíndromos

PorJosé A. Alonso 19-agosto-202214-diciembre-2022

Definir la función

   palindromo :: Eq a => [a] -> Bool

1	palindromo :: Eq a => [a] -> Bool

tal que (palindromo xs) se verifica si xs es un palíndromo; es decir, es lo mismo leer xs de izquierda a derecha que de derecha a izquierda. Por ejemplo,

   palindromo [3,2,5,2,3]    ==  True
   palindromo [3,2,5,6,2,3]  ==  False

1 2	palindromo [3,2,5,2,3] == True palindromo [3,2,5,6,2,3] == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

palindromo :: Eq a => [a] -> Bool
palindromo xs =
  xs == reverse xs

palindromo :: Eq a => [a] -> Bool

palindromo xs =

xs == reverse xs

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar

A = TypeVar('A')

def palindromo(xs: list[A]) -> bool:
    return xs == list(reversed(xs))

from typing import TypeVar

A = TypeVar('A')

def palindromo(xs: list[A]) -> bool:

return xs == list(reversed(xs))

El código se encuentra en GitHub.

Comentarios

La inversa de la lista xs se calcula
- en Haskell, con reverse xs y
- en Python, con list(reversed(xs)).
Para comparar la igualdad de dos listas xs e ys se escribe igual qh Haskell y en Python: xs == ys.

Rango de una lista

PorJosé A. Alonso 18-agosto-202214-diciembre-2022

Definir la función

   rango :: [Int] -> [Int]

1	rango :: [Int] -> [Int]

tal que (rango xs) es la lista formada por el menor y mayor elemento de xs. Por ejemplo,

   rango [3,2,7,5]  ==  [2,7]

1	rango [3,2,7,5] == [2,7]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

rango :: [Int] -> [Int]
rango xs = [minimum xs, maximum xs]

1 2	rango :: [Int] -> [Int] rango xs = [minimum xs, maximum xs]

El código se encuentra en GitHub.

Soluciones en Python

def rango(xs: list[int]) -> list[int]:
    return [min(xs), max(xs)]

1 2	def rango(xs: list[int]) -> list[int]: return [min(xs), max(xs)]

El código se encuentra en GitHub.

Comentarios

El menor elemento de la lista xs se calcula
- en Haskell, con minimum xs y
- en Python, con min(xs).
El mayor elemento de la lista xs se calcula
- en Haskell, con maximum xs y
- en Python, con max(xs).

Los primeros al final

PorJosé A. Alonso 17-agosto-202214-diciembre-2022

Definir la función

   rota :: Int -> [a] -> [a]

1	rota :: Int -> [a] -> [a]

tal que (rota n xs) es la lista obtenida poniendo los n primeros elementos de xs al final de la lista. Por ejemplo,

   rota 1 [3,2,5,7]  ==  [2,5,7,3]
   rota 2 [3,2,5,7]  ==  [5,7,3,2]
   rota 3 [3,2,5,7]  ==  [7,3,2,5]

rota 1 [3,2,5,7] == [2,5,7,3]

rota 2 [3,2,5,7] == [5,7,3,2]

rota 3 [3,2,5,7] == [7,3,2,5]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

rota :: Int -> [a] -> [a]
rota n xs = drop n xs ++ take n xs

1 2	rota :: Int -> [a] -> [a] rota n xs = drop n xs ++ take n xs

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar

A = TypeVar('A')

def rota(n: int, xs: list[A]) -> list[A]:
    return xs[n:] + xs[:n]

from typing import TypeVar

A = TypeVar('A')

def rota(n: int, xs: list[A]) -> list[A]:

return xs[n:] + xs[:n]

El código se encuentra en GitHub.

Comentarios
+ Los n primeros elementos de la lista xs se calcula
+ en Haskell, con take n xs y
+ en Python, con xs[n:].
+ La lista xs sin sus n primeros elementos se calcula
+ en Haskell, con drop n xs y
+ en Python, con xs[:n].

El primero al final

PorJosé A. Alonso 16-agosto-202214-diciembre-2022

Definir la función

   rota1 :: [a] -> [a]

1	rota1 :: [a] -> [a]

tal que (rota1 xs) es la lista obtenida poniendo el primer elemento de xs al final de la lista. Por ejemplo,

   rota1 [3,2,5,7]  ==  [2,5,7,3]

1	rota1 [3,2,5,7] == [2,5,7,3]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

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

rota1a :: [a] -> [a]
rota1a [] = []
rota1a xs = tail xs ++ [head xs]

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

rota1b :: [a] -> [a]
rota1b []     = []
rota1b (x:xs) = xs ++ [x]

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_rota1 :: [Int] -> Bool
prop_rota1 xs =
  rota1a xs == rota1b xs

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

import Test.QuickCheck

-- 1ª solución

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

rota1a :: [a] -> [a]

rota1a [] = []

rota1a xs = tail xs ++ [head xs]

-- 2ª solución

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

rota1b :: [a] -> [a]

rota1b [] = []

rota1b (x:xs) = xs ++ [x]

-- Comprobación de equivalencia

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

-- La propiedad es

prop_rota1 :: [Int] -> Bool

prop_rota1 xs =

rota1a xs == rota1b xs

-- La comprobación es

-- λ> quickCheck prop_rota1

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª solución
def rota1a(xs: list[A]) -> list[A]:
    if xs == []:
        return []
    return xs[1:] + [xs[0]]

# 2ª solución
def rota1b(xs: list[A]) -> list[A]:
    if xs == []:
        return []
    ys = xs[1:]
    ys.append(xs[0])
    return ys

# 3ª solución
def rota1c(xs: list[A]) -> list[A]:
    if xs == []:
        return []
    y, *ys = xs
    return ys + [y]

# La equivalencia de las definiciones es
@given(st.lists(st.integers()))
def test_rota1(xs: list[int]) -> None:
    assert rota1a(xs) == rota1b(xs) == rota1c(xs)

# La comprobación es
#    src> poetry run pytest -q el_primero_al_final.py
#    1 passed in 0.20s

from typing import TypeVar

from hypothesis import given, strategies as st

A = TypeVar('A')

# 1ª solución

def rota1a(xs: list[A]) -> list[A]:

if xs == []:

return []

return xs[1:] + [xs[0]]

# 2ª solución

def rota1b(xs: list[A]) -> list[A]:

if xs == []:

return []

ys = xs[1:]

ys.append(xs[0])

return ys

# 3ª solución

def rota1c(xs: list[A]) -> list[A]:

if xs == []:

return []

y, *ys = xs

return ys + [y]

# La equivalencia de las definiciones es

@given(st.lists(st.integers()))

def test_rota1(xs: list[int]) -> None:

assert rota1a(xs) == rota1b(xs) == rota1c(xs)

# La comprobación es

# src> poetry run pytest -q el_primero_al_final.py

# 1 passed in 0.20s

El código se encuentra en GitHub.

Comentarios

El primer elemento de la lista xs se calcula
- en Haskell, con head xs
- en Python, con xs[0]
El resto de la lista xs se calcula
- en Haskell, con tail xs
- en Python, con xs[1:]
La concatenación de las listas xse ysse calcula
- en Haskell, con xs ++ ys
- en Python, con xs + ys
En Python. xs.append(x) modifica la lista xs añadiéndole x al final. Por ejemplo,

>>> xs = [3, 2, 5]
>>> xs.append(1)
>>> xs
[3, 2, 5, 1]

>>> xs = [3, 2, 5]

>>> xs.append(1)

>>> xs

[3, 2, 5, 1]

Máximo de tres números

PorJosé A. Alonso 15-agosto-202214-diciembre-2022

Definir la función

   maxTres :: Int -> Int -> Int -> Int

1	maxTres :: Int -> Int -> Int -> Int

tal que (maxTres x y z) es el máximo de x, y y z. Por ejemplo,

   maxTres 6 2 4  ==  6
   maxTres 6 7 4  ==  7
   maxTres 6 7 9  ==  9

maxTres 6 2 4 == 6

maxTres 6 7 4 == 7

maxTres 6 7 9 == 9

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Solución en Haskell

maxTres :: Int -> Int -> Int -> Int
maxTres x y z = max x (max y z)

1 2	maxTres :: Int -> Int -> Int -> Int maxTres x y z = max x (max y z)

El código se encuentra en GitHub.

Soluciones en Python

def maxTres(x: int, y: int, z: int) -> int:
    return max(x, max(y, z))

1 2	def maxTres(x: int, y: int, z: int) -> int: return max(x, max(y, z))

El código se encuentra en GitHub.

Comentarios

El máximo de x e y se escribe
- en Haskell, max x y y
- en Python, max(x, y).

Último dígito

PorJosé A. Alonso 12-agosto-202214-diciembre-2022

Definir la función

   ultimoDigito :: Int -> Int

1	ultimoDigito :: Int -> Int

tal que (ultimoDigito x) es el último dígito del número x. Por ejemplo,

   ultimoDigito 325  ==  5

1	ultimoDigito 325 == 5

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Solución en Haskell

ultimoDigito :: Int -> Int
ultimoDigito x = rem x 10

1 2	ultimoDigito :: Int -> Int ultimoDigito x = rem x 10

El código se encuentra en GitHub.

Solución en Python

def ultimoDigito(x: int) -> int:
    return x % 10

1 2	def ultimoDigito(x: int) -> int: return x % 10

El código se encuentra en GitHub.

Comentarios

El resto de la división entera se x entre y sn ecribe
- en Haskell, rem x y,
- en Python, x % y.

Área de la corona circular

PorJosé A. Alonso 11-agosto-202214-diciembre-2022

Definir la función

   areaDeCoronaCircular :: Double -> Double -> Double

1	areaDeCoronaCircular :: Double -> Double -> Double

tal que (areaDeCoronaCircular r1 r2) es el área de una corona circular de radio interior r1 y radio exterior r2. Por ejemplo,

   areaDeCoronaCircular 1 2 == 9.42477796076938
   areaDeCoronaCircular 2 5 == 65.97344572538566
   areaDeCoronaCircular 3 5 == 50.26548245743669

areaDeCoronaCircular 1 2 == 9.42477796076938

areaDeCoronaCircular 2 5 == 65.97344572538566

areaDeCoronaCircular 3 5 == 50.26548245743669

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Solución en Haskell

areaDeCoronaCircular :: Double -> Double -> Double
areaDeCoronaCircular r1 r2 = pi*(r2^2 -r1^2)

1 2	areaDeCoronaCircular :: Double -> Double -> Double areaDeCoronaCircular r1 r2 = pi*(r2^2 -r1^2)

El código se encuentra en GitHub.

Solución en Python

from math import pi

def areaDeCoronaCircular(r1: float, r2: float) -> float:
    return pi * (r2 ** 2 - r1 ** 2)

from math import pi

def areaDeCoronaCircular(r1: float, r2: float) -> float:

return pi * (r2 ** 2 - r1 ** 2)

El código se encuentra en GitHub.

Comentarios

La diferencia de dos números x e y se escribe en Python igual que en Haskell: x - y.

Volumen de la esfera

PorJosé A. Alonso 10-agosto-202214-diciembre-2022

Definir la función

   volumenEsfera :: Double -> Double

1	volumenEsfera :: Double -> Double

tal que (volumenEsfera r) es el volumen de la esfera de radio r. Por ejemplo,

   volumenEsfera 10  ==  4188.790204786391

1	volumenEsfera 10 == 4188.790204786391

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Solución en Haskell

volumenEsfera :: Double -> Double
volumenEsfera r = (4/3)*pi*r^3

1 2	volumenEsfera :: Double -> Double volumenEsfera r = (4/3)pir^3

El código se encuentra en GitHub.

Solución en Python

from math import pi

def volumenEsfera(r: float) -> float:
    return (4 / 3) * pi * r ** 3

from math import pi

def volumenEsfera(r: float) -> float:

return (4 / 3) * pi * r ** 3

El código se encuentra en GitHub.

Comentarios

El número $\pi$ se representa igual en Python que en Haskell; pero, en Python. para usarlo hay que importarlo de la librería math.
La potencia de número x elevado al entero n se escribe
- en Haskell, x^n y
- en Python, x ** n.

Suma de monedas

PorJosé A. Alonso 9-agosto-202214-diciembre-2022

Definir la función

   sumaMonedas :: Int -> Int -> Int -> Int -> Int -> Int

1	sumaMonedas :: Int -> Int -> Int -> Int -> Int -> Int

tal que (sumaMonedas a b c d e) es la suma de los euros correspondientes a a monedas de 1 euro, b de 2 euros, c de 5 euros, d de 10 euros y e de 20 euros. Por ejemplo,

   sumaMonedas 0 0 0 0 1  ==  20
   sumaMonedas 0 0 8 0 3  == 100
   sumaMonedas 1 1 1 1 1  ==  38

sumaMonedas 0 0 0 0 1 == 20

sumaMonedas 0 0 8 0 3 == 100

sumaMonedas 1 1 1 1 1 == 38

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

sumaMonedas :: Int -> Int -> Int -> Int -> Int -> Int
sumaMonedas a b c d e = 1*a+2*b+5*c+10*d+20*e

1 2	sumaMonedas :: Int -> Int -> Int -> Int -> Int -> Int sumaMonedas a b c d e = 1a+2b+5c+10d+20*e

El código se encuentra en GitHub.

Soluciones en Python

def sumaMonedas(a: int, b: int, c: int, d: int, e: int) -> int:
    return 1 * a + 2 * b + 5 * c + 10 * d + 20 * e

1 2	def sumaMonedas(a: int, b: int, c: int, d: int, e: int) -> int: return 1 * a + 2 * b + 5 * c + 10 * d + 20 * e

El código se encuentra en GitHub.

Comentarios

El producto de dos números x e y se escribe en Python igual que en Haskell: x * y.

Media aritmética de tres números

PorJosé A. Alonso 8-agosto-202214-diciembre-2022

Definir la función

   media3 :: Float -> Float -> Float -> Float

1	media3 :: Float -> Float -> Float -> Float

tal que (media3 x y z) es la media aritmética de los números x, y y z. Por ejemplo,

   media3 1 3 8     ==  4.0
   media3 (-1) 0 7  ==  2.0
   media3 (-3) 0 3  ==  0.0

media3 1 3 8 == 4.0

media3 (-1) 0 7 == 2.0

media3 (-3) 0 3 == 0.0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Solución en Haskell

media3 :: Float -> Float -> Float -> Float
media3 x y z = (x+y+z)/3

1 2	media3 :: Float -> Float -> Float -> Float media3 x y z = (x+y+z)/3

El código se encuentra en GitHub.

Soluciones en Python

def media3(x: float, y: float, z: float) -> float:
    return (x + y + z)/3

1 2	def media3(x: float, y: float, z: float) -> float: return (x + y + z)/3

El código se encuentra en GitHub.

Comentarios

Los comentarios irán resaltando las diferencias de la solución en Python respecto de la de Haskell (que no se hayan comentado en ningún ejercicio anterior).
La estructura de la definición en Python es

def <nombre de la función>(<argumento 1>,...,<argumento n>):
    # type: <signatura de la función>
    ...
    return <resultado>

def <nombre de la función>(<argumento 1>,...,<argumento n>):

# type: <signatura de la función>

...

return <resultado>

La suma de dos números x e y se escribe en Python igual que en Haskell: x + y.
El cociente de dos números decimales x e y se escribe en Python igual que en Haskell: x / y.

Curso de introducción a la programación con Haskell y Python

PorJosé A. Alonso 7-agosto-202210-agosto-2022

Mañana comenzará en Exercitium un curso práctico de introducción a la programación con Haskell y Python.

Diariamente, se publicará un ejercicio con sus soluciones en Haskell y en Python. El orden de los ejercicios se corresponde con el de los temas del curso de Programación funcional con Haskell. Además, en cada ejercicio se comentarán las diferencias entre ambos lenguajes y se irá extendiendo la tabla de equivalencia entre Haskell y Python.

Las soluciones de los ejercicios con Haskell se irán añadiendo al repositorio Exercitium em GitHub. Están como un proyecto con Stack (en concreto, la LTS-18.24) de forma que se puede verificar los ejemplos con

stack test

1	stack test

Las soluciones de los ejercicios con Python se irán añadiendo al repositorio Exercitium-Python em GitHub. Están como un proyecto con Poetry que usa la versión 3.10 de Python. También se pueden verificar los ejemplos con

poetry run pytest

1	poetry run pytest

He intentado escribir soluciones en Python parecidas a la de Haskell, conservando el estilo funcional. De todas formas, en los comentarios se pueden escribir definiciones alternativas en cualquiera de los lenguajes.

Los libros de Haskell en los que me he basado son

Algorithms: A functional programming approach de F. Rabhi y G. Lapalme.
Algorithm design with Haskell de E. Bird y J. Gibbons.
An introduction to functional programming systems using Haskell de A.J.T. Davie.
An introduction to functional programming through lambda calculus de G. Michaelson.
¡Aprende Haskell por el bien de todos! de M. Lipovača.
Beautiful code, compelling evidence (Functional programming for information visualization) de J.R. Heard.
Beginning Haskell (A project based approach). ~ A. Serrano.
Categories and Haskell de J.W. Buurlage.
Category theory applied to functional programming J.P. Villa.
Computational semantics and type theory de J. van Eijck.
Computational semantics with functional programming de J. van Eijck y C. Unger.
Developing web applications with Haskell and Yesod de M. Snoyman.
Discrete mathematics using a computer de J. O’Donnell, C. Hall y R. Page.
Domain-specific languages of Mathematics de P. Jansson, C. Ionescu y J.P. Bernardy.
Ejercicios de programación funcional con Haskell de J.A. Alonso y M.J. Hidalgo.
Exámenes de programación funcional con Haskell de J.A. Alonso y als.
Functional programming and graph algorithms de D.J. King.
Get programming with Haskell de W. Kurt.
Haskell cookbook de Y. Sajanikar.
Haskell data analysis cookbook de N. Shukla.
Haskell design patterns de R. Lemmer.
Haskell financial data modeling and predictive analytics de P. Ryzhov.
Haskell high performance programming de S. Thomasson.
Haskell (Notes for professionals).
Haskell programming from first principles de C. Allen y J. Moronuki.
Haskell quick syntax reference de S.L. Nita y M. Mihailescu.
Haskell tutorial and cookbook de M. Watson.
Haskell (The craft of functional programming) de S. Thompson.
Introducción a la programación funcional con Haskell de R. Bird.
Introduction to computation Haskell, logic and automata de D. Sannella, M. Fourman, H. Peng y P. Wadler.
Learn you a Haskell for great good! de M. Lipovaca y J. Brock.
Learning Haskell data analysis de J. Church.
Parallel and concurrent programming in Haskell. S. Marlow.
Pearls of functional algorithm design de R. Bird.
Piensa en Haskell de J.A. Alonso y M.J. Hidalgo.
Practical Haskell (A real World guide to programming) de A. Serrano.
Practical Web development with Haskell de E. Putrady.
Practical concurrent Haskell (with big data applications) de S.L. Nita y M. Mihailescu.
Programming in Haskell (2nd edition) de G. Hutton.
Purely functional data structures de D. Okasaki.
Real world Haskell de B. O’Sullivan, J. Goerzen y D. Stewart.
Temas de programación funcional de J.A. Alonso.
The Dao of functional programming de B. Milewski.
The Haskell school of music (from signals to symphonies) de P. Hudak.
The Haskell road to logic, maths and programming de K. Doets y J van Eijck.
Thinking functionally with Haskell de R. Bird.
Thinking with types de S. Maguire.
Yet another Haskell tutorial de Hal Daume III et al.

Los libros de Python en los que me he basado son

Advanced guide to Python 3 programming de J. Hunt.
Algorithmic problem solving with Python de J.B. Schneider, S.L. Broschat y J. Dahmen.
Aprenda a pensar como un programador con Python de A. Downey, J. Elkner y C. Meyers.
Aprende a programar en Python como si estuvieras en el siglo XXI de J.J. Merelo.
Artificial intelligence with Python de P. Joshi.
Automate the boring stuff with Python de A. Sweigart.
A beginners guide to Python 3 programming de J. Hunt.
A concise introduction to programming in Python de M.J. Johnson.
A functional start to computing with Python de T. Herman.
A primer on scientific programming with Python de H.P. Langtangen.
A programmer’s introduction to mathematics de J. Kun.
A very basic introduction to scientific Python programming de H.P. Langtangen.
Basic cheat sheet for Python de Swigartpdf
Beginning Python (From novice to professional) de M.L. Hetland.
Clean Python (Elegant coding in Python) de S. Kapil.
Competitive programming in Python de C. Durr y J.L. Vie.
Computational physics with Python de E. Ayars.
Computational quantum mechanics de J. Izaac y J. Wang.
Data science from scratch (First principles with Python) de J. Grus.
Data structures and algorithms in Python de M.T. Goodrich, R. Tamassia y M.H.Goldwasser.
Doing math with Python de A. Saha.
Effective computation in physics de A. Scopatz y K.D. Huff.
El lenguaje Python de D. Masip.
Fluent Python de L. Ramalho.
Functional Python programming de D.F. Lott.
Functional programming in Python de D. Mertz.
Fundamentals of Python (From first programs through data structures) de K.A. Lambert.
Hacking secret ciphers with Python de A. Sweigart.
Introducción a la programación con Python 3 de A. Marzal. I. Gracia y P. García.
Introduction a l’algorithmique avec Python de P. Olivier.
Introduction to Python for computational science and engineering de H. ~ Fangohr.
Introduction to Python for econometrics, statistics and data analysis. ~ Sheppard-14.pdf
Introduction to Python for science and engineering de D.J. Pine.
Introduction to Python for scientists and engineers de S. Nagar.
Introduction to computation and programming using Python de J.V. Guttag.
Introduction to recursive programming de M. Rubio.
Learning to program using Python de C. Jackson.
Lectures on mathematical computing with Python de J. Gopalakrishnan.
Mastering Python de R. van Hattem.
Problem solving with algorithms and data structures using Python de B. Miller y D. Ranum.
Programmation en Python pour les mathématiques de A. Casamayou P. Chauvin y G. Connan.
Programming and mathematical thinking de A.M. Stavely.
Programming for computations (A gentle introduction to numerical simulations with Python 3.6) de S. Linge y H.P. Langtangen.
Programming with Python de T.R. Padmanabhan.
Python 3 for absolute beginners de T. Hall y J-P Stacey.
Python algorithms (Mastering basic algorithms in the Python language) de M.L. Lie.
Python descriptors de J. Zimmerman.
Python programming (An introduction to computer science) de J. Zelle.
Python scientific lecture notes de V. Haenel, E. Gouillart y G. Varoquaux..
Scipy Lecture Notes (One document to learn numerics, science, and data with Python) de G. Varoquaux et als.
Serious Python de J. Danjou.
The Python workbook (A brief introduction with exercises and solutions) de B. Stephenson.

Números de Pentanacci

PorJosé A. Alonso 5-agosto-202214-diciembre-2022

Los números de Fibonacci se definen mediante las ecuaciones

   F(0) = 0
   F(1) = 1
   F(n) = F(n-1) + F(n-2), si n > 1

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2), si n > 1

Los primeros números de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones

   P(0) = 0
   P(1) = 1
   P(2) = 1
   P(3) = 2
   P(4) = 4
   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

P(0) = 0

P(1) = 1

P(2) = 1

P(3) = 2

P(4) = 4

P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

1	0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Definir la sucesión

   pentanacci :: [Integer]

1	pentanacci :: [Integer]

cuyos elementos son los números de Pentanacci. Por ejemplo,

   λ> take 15 pentanacci
   [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
   λ> (pentanacci !! (10^5)) `mod` (10^30) 
   482929150584077921552549215816
   231437922897686901289110700696
   λ> length (show (pentanacci !! (10^5)))
   29357

λ> take 15 pentanacci

[0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]

λ> (pentanacci !! (10^5)) `mod` (10^30)

482929150584077921552549215816

231437922897686901289110700696

λ> length (show (pentanacci !! (10^5)))

29357

Soluciones

import Data.List (zipWith5)
import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)

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

pentanacci1 :: [Integer]
pentanacci1 = [pent n | n <- [0..]]

pent :: Integer -> Integer
pent 0 = 0
pent 1 = 1
pent 2 = 1
pent 3 = 2
pent 4 = 4
pent n = pent (n-1) + pent (n-2) + pent (n-3) + pent (n-4) + pent (n-5)

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

pentanacci2 :: [Integer]
pentanacci2 = 
  0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4)
  where f a b c d e = a+b+c+d+e
        r n         = drop n pentanacci2

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

pentanacci3 :: [Integer]
pentanacci3 = p (0, 1, 1, 2, 4)
  where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

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

pentanacci4 :: [Integer]
pentanacci4 = 0: 1: 1: 2: 4: p pentanacci4
  where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_pentanacci :: NonNegative Int -> Bool
prop_pentanacci (NonNegative n) =
  all (== pentanacci1 !! n)
      [pentanacci1 !! n,
       pentanacci2 !! n,
       pentanacci3 !! n]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanacci
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> pentanacci1 !! 25
--    5976577
--    (3.18 secs, 1,025,263,896 bytes)
--    λ> pentanacci2 !! 25
--    5976577
--    (0.00 secs, 562,360 bytes)
--    
--    λ> length (show (pentanacci2 !! (10^5)))
--    29357
--    (1.04 secs, 2,531,259,408 bytes)
--    λ> length (show (pentanacci3 !! (10^5)))
--    29357
--    (1.00 secs, 2,548,868,384 bytes)
--    λ> length (show (pentanacci4 !! (10^5)))
--    29357
--    (0.96 secs, 2,580,065,520 bytes)

import Data.List (zipWith5)

import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)

-- 1ª solución

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

pentanacci1 :: [Integer]

pentanacci1 = [pent n | n <- [0..]]

pent :: Integer -> Integer

pent 0 = 0

pent 1 = 1

pent 2 = 1

pent 3 = 2

pent 4 = 4

pent n = pent (n-1) + pent (n-2) + pent (n-3) + pent (n-4) + pent (n-5)

-- 2ª solución

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

pentanacci2 :: [Integer]

pentanacci2 =

0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4)

where f a b c d e = a+b+c+d+e

r n = drop n pentanacci2

-- 3ª solución

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

pentanacci3 :: [Integer]

pentanacci3 = p (0, 1, 1, 2, 4)

where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

-- 4ª solución

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

pentanacci4 :: [Integer]

pentanacci4 = 0: 1: 1: 2: 4: p pentanacci4

where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_pentanacci :: NonNegative Int -> Bool

prop_pentanacci (NonNegative n) =

all (== pentanacci1 !! n)

[pentanacci1 !! n,

pentanacci2 !! n,

pentanacci3 !! n]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanacci

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> pentanacci1 !! 25

-- 5976577

-- (3.18 secs, 1,025,263,896 bytes)

-- λ> pentanacci2 !! 25

-- 5976577

-- (0.00 secs, 562,360 bytes)

-- λ> length (show (pentanacci2 !! (10^5)))

-- 29357

-- (1.04 secs, 2,531,259,408 bytes)

-- λ> length (show (pentanacci3 !! (10^5)))

-- 29357

-- (1.00 secs, 2,548,868,384 bytes)

-- λ> length (show (pentanacci4 !! (10^5)))

-- 29357

-- (0.96 secs, 2,580,065,520 bytes)

El código se encuentra en GitHub.

Referencias

Tito III Piezas y Eric Weisstein, Pentanacci number.
N. J. A. Sloane, Sucesión A001591 de la OEIS.

Número de representaciones de n como suma de dos cuadrados

PorJosé A. Alonso 4-agosto-202214-diciembre-2022

Sea $n$ un número natural cuya factorización prima es
$$n = 2^{a} \times p(1)^{b(1)} \times \dots \times p(n)^{b(n)} \times q(1)^{c(1)} \times \dots \times q(m)^{c(m)}$$
donde los $p(i)$ son los divisores primos de $n$ congruentes con 3 módulo 4 y los $q(j)$ son los divisores primos de $n$ congruentes con 1 módulo 4. Entonces, el número de forma de descomponer $n$ como suma de dos
cuadrados es 0, si algún $b(i)$ es impar y es el techo (es decir, el número entero más próximo por exceso) de
$$\frac{(1+c(1)) \times \dots \times (1+c(m))}{2}$$
en caso contrario. Por ejemplo, el número
$$2^{3} \times (3^{9} \times 7^{8}) \times (5^{3} \times 13^{6})$$
no se puede descomponer como sumas de dos cuadrados (porque el exponente de 3 es impar) y el número
$$2^{3} \times (3^{2} \times 7^{8}) \times (5^{3} \times 13^{6})$$
tiene 14 descomposiciones como suma de dos cuadrados (porque los exponentes de 3 y 7 son pares y el techo de
$$\frac{(1+3) \times (1+6)}{2}$$
es 14).

Definir la función

   nRepresentaciones :: Integer -> Integer

1	nRepresentaciones :: Integer -> Integer

tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,

   nRepresentaciones (2^3*3^9*5^3*7^8*13^6)        ==  0
   nRepresentaciones (2^3*3^2*5^3*7^8*13^6)        ==  14
   head [n | n <- [1..], nRepresentaciones n > 8]  ==  71825

nRepresentaciones (2^3*3^9*5^3*7^8*13^6) == 0

nRepresentaciones (2^3*3^2*5^3*7^8*13^6) == 14

head [n | n <- [1..], nRepresentaciones n > 8] == 71825

Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad

   prop_representacion :: Positive Integer -> Bool
   prop_representacion (Positive n) =
     nRepresentaciones2 n == genericLength (representaciones n)

prop_representacion :: Positive Integer -> Bool

prop_representacion (Positive n) =

nRepresentaciones2 n == genericLength (representaciones n)

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck (Positive (Positive), quickCheck)

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

nRepresentaciones1 :: Integer -> Integer
nRepresentaciones1 n =
  ceiling (fromIntegral (product (map aux (factorizacion n))) / 2)
  where aux (p,e) | p == 2         = 1
                  | p `mod` 4 == 3 = if even e then 1 else 0
                  | otherwise      = e+1

-- (factorizacion n) es la factorización prima de n. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  map (\xs -> (head xs, genericLength xs)) (group (primeFactors n))

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

nRepresentaciones2 :: Integer -> Integer
nRepresentaciones2 n =
  (1 + product (map aux (factorizacion n))) `div`  2
  where aux (p,e) | p == 2         = 1
                  | p `mod` 4 == 3 = if even e then 1 else 0
                  | otherwise      = e+1

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_nRepresentaciones :: Positive Integer -> Bool
prop_nRepresentaciones (Positive n) =
  nRepresentaciones1 n == nRepresentaciones2 n
  
-- La comprobación es
--    λ> quickCheck prop_nRepresentaciones
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> head [n | n <- [1..], nRepresentaciones1 n > 8]
--    71825
--    (1.39 secs, 2,970,063,760 bytes)
--    λ> head [n | n <- [1..], nRepresentaciones2 n > 8]
--    71825
--    (1.71 secs, 2,943,788,424 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_representacion :: Positive Integer -> Bool
prop_representacion (Positive n) =
  nRepresentaciones2 n == genericLength (representaciones n)

representaciones :: Integer -> [(Integer,Integer)]
representaciones n =
  [(x,raiz z) | x <- [0..raiz (n `div` 2)], 
                let z = n - x*x,
                esCuadrado z]

esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x

raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))
    
-- La comprobación es
--    λ> quickCheck prop_representacion
--    +++ OK, passed 100 tests.

import Data.List (genericLength, group)

import Data.Numbers.Primes (primeFactors)

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

-- 1ª solución

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

nRepresentaciones1 :: Integer -> Integer

nRepresentaciones1 n =

ceiling (fromIntegral (product (map aux (factorizacion n))) / 2)

where aux (p,e) | p == 2 = 1

| p `mod` 4 == 3 = if even e then 1 else 0

| otherwise = e+1

-- (factorizacion n) es la factorización prima de n. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

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

factorizacion n =

map (\xs -> (head xs, genericLength xs)) (group (primeFactors n))

-- 2ª solución

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

nRepresentaciones2 :: Integer -> Integer

nRepresentaciones2 n =

(1 + product (map aux (factorizacion n))) `div` 2

where aux (p,e) | p == 2 = 1

| p `mod` 4 == 3 = if even e then 1 else 0

| otherwise = e+1

-- Comprobación de equivalencia

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

-- La propiedad es

prop_nRepresentaciones :: Positive Integer -> Bool

prop_nRepresentaciones (Positive n) =

nRepresentaciones1 n == nRepresentaciones2 n

-- La comprobación es

-- λ> quickCheck prop_nRepresentaciones

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> head [n | n <- [1..], nRepresentaciones1 n > 8]

-- 71825

-- (1.39 secs, 2,970,063,760 bytes)

-- λ> head [n | n <- [1..], nRepresentaciones2 n > 8]

-- 71825

-- (1.71 secs, 2,943,788,424 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_representacion :: Positive Integer -> Bool

prop_representacion (Positive n) =

nRepresentaciones2 n == genericLength (representaciones n)

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

representaciones n =

[(x,raiz z) | x <- [0..raiz (n `div` 2)],

let z = n - x*x,

esCuadrado z]

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

raiz :: Integer -> Integer

raiz x = floor (sqrt (fromIntegral x))

-- La comprobación es

-- λ> quickCheck prop_representacion

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Referencias

W. Stein, Which numbers are the sum of two squares?.
E.W. Weisstein, Sum of squares function en MathWorld.
N.J.A. Sloane,Sucesión A004018 de OEIS.
Expressing a number as a sum of two squares.
Sum of squares.

Representaciones de un número como suma de dos cuadrados

PorJosé A. Alonso 3-agosto-202214-diciembre-2022

Definir la función

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

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

tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.

   representaciones  20              ==  [(2,4)]
   representaciones  25              ==  [(0,5),(3,4)]
   representaciones 325              ==  [(1,18),(6,17),(10,15)]
   length (representaciones (10^14)) == 8

representaciones 20 == [(2,4)]

representaciones 25 == [(0,5),(3,4)]

representaciones 325 == [(1,18),(6,17),(10,15)]

length (representaciones (10^14)) == 8

Comprobar con QuickCheck que un número natural n se puede como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck (Positive (Positive), quickCheck)

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

representaciones1 :: Integer -> [(Integer,Integer)]
representaciones1 n =
  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]

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

representaciones2 :: Integer -> [(Integer,Integer)]
representaciones2 n =
  [(x,raiz z) | x <- [0..raiz (n `div` 2)], 
                let z = n - x*x,
                esCuadrado z]

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz = floor . sqrt . fromIntegral
    
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x

-- 3ª solución
-- ===========
 
representaciones3 :: Integer -> [(Integer, Integer)]
representaciones3 n = aux 0 (raiz n)
  where aux x y
          | x > y     = [] 
          | otherwise = case compare (x*x + y*y) n of
                          LT -> aux (x + 1) y
                          EQ -> (x, y) : aux (x + 1) (y - 1)
                          GT -> aux x (y - 1)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_representaciones :: Positive Integer -> Bool
prop_representaciones (Positive n) =
  all (== representaciones1 n)
      [representaciones2 n,
       representaciones3 n]

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

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

-- La comparación es
--    λ> representaciones1 4000
--    [(20,60),(36,52)]
--    (4.95 secs, 2,434,929,624 bytes)
--    λ> representaciones2 4000
--    [(20,60),(36,52)]
--    (0.00 secs, 599,800 bytes)
--    λ> representaciones3 4000
--    [(20,60),(36,52)]
--    (0.01 secs, 591,184 bytes)
--    
--    λ> length (representaciones2 (10^14))
--    8
--    (6.64 secs, 5,600,837,088 bytes)
--    λ> length (representaciones3 (10^14))
--    8
--    (9.37 secs, 4,720,548,264 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_representacion :: Positive Integer -> Bool
prop_representacion (Positive n) =
  not (null (representaciones2 n)) == 
  all (\(p,e) -> p `mod` 4 /= 3 || even e) (factorizacion n)

-- (factorizacion n) es la factorización prima de n. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  map (\xs -> (head xs, genericLength xs)) (group (primeFactors n))

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

100

import Data.List (genericLength, group)

import Data.Numbers.Primes (primeFactors)

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

-- 1ª solución

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

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

representaciones1 n =

[(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]

-- 2ª solución

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

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

representaciones2 n =

[(x,raiz z) | x <- [0..raiz (n `div` 2)],

let z = n - x*x,

esCuadrado z]

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz 25 == 5

-- raiz 24 == 4

-- raiz 26 == 5

raiz :: Integer -> Integer

raiz = floor . sqrt . fromIntegral

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado 25 == True

-- esCuadrado 26 == False

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

-- 3ª solución

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

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

representaciones3 n = aux 0 (raiz n)

where aux x y

| x > y = []

| otherwise = case compare (x*x + y*y) n of

LT -> aux (x + 1) y

EQ -> (x, y) : aux (x + 1) (y - 1)

GT -> aux x (y - 1)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_representaciones :: Positive Integer -> Bool

prop_representaciones (Positive n) =

all (== representaciones1 n)

[representaciones2 n,

representaciones3 n]

-- La comprobación es

-- λ> quickCheck prop_representaciones

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> representaciones1 4000

-- [(20,60),(36,52)]

-- (4.95 secs, 2,434,929,624 bytes)

-- λ> representaciones2 4000

-- [(20,60),(36,52)]

-- (0.00 secs, 599,800 bytes)

-- λ> representaciones3 4000

-- [(20,60),(36,52)]

-- (0.01 secs, 591,184 bytes)

-- λ> length (representaciones2 (10^14))

-- 8

-- (6.64 secs, 5,600,837,088 bytes)

-- λ> length (representaciones3 (10^14))

-- 8

-- (9.37 secs, 4,720,548,264 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_representacion :: Positive Integer -> Bool

prop_representacion (Positive n) =

not (null (representaciones2 n)) ==

all (\(p,e) -> p `mod` 4 /= 3 || even e) (factorizacion n)

-- (factorizacion n) es la factorización prima de n. Por ejemplo,

-- factorizacion 600 == [(2,3),(3,1),(5,2)]

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

factorizacion n =

map (\xs -> (head xs, genericLength xs)) (group (primeFactors n))

-- La comprobación es

-- λ> quickCheck prop_representacion

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Factorizaciones de números de Hilbert

PorJosé A. Alonso 2-agosto-202224-julio-2022

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …

Un primo de Hilbert es un número de Hilbert n que no es por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …

Definir la función

   factorizacionesH :: Integer -> [[Integer]]

1	factorizacionesH :: Integer -> [[Integer]]

tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,

  factorizacionesH  25    ==  [[5,5]]
  factorizacionesH  45    ==  [[5,9]]
  factorizacionesH 441    ==  [[9,49],[21,21]]
  factorizacionesH 80109  ==  [[9,9,989],[9,69,129]]

factorizacionesH 25 == [[5,5]]

factorizacionesH 45 == [[5,9]]

factorizacionesH 441 == [[9,49],[21,21]]

factorizacionesH 80109 == [[9,9,989],[9,69,129]]

Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).

Soluciones

import Data.Numbers.Primes (isPrime, primeFactors)
import Test.QuickCheck (Positive (Positive), quickCheck)

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

factorizacionesH1 :: Integer -> [[Integer]]
factorizacionesH1 = aux primosH1
  where
    aux (x:xs) n 
      | x == n         = [[n]]
      | x > n          = []
      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n 
      | otherwise      = aux xs n 

primosH1 :: [Integer]
primosH1 = [n | n <- tail numerosH,
                divisoresH n == [1,n]]

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,
--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]
numerosH :: [Integer]
numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a
-- n. Por ejemplo,
--   divisoresH 117  ==  [1,9,13,117]
--   divisoresH  21  ==  [1,21]
divisoresH :: Integer -> [Integer]
divisoresH n = [x | x <- takeWhile (<=n) numerosH,
                    n `mod` x == 0]

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

factorizacionesH2 :: Integer -> [[Integer]]
factorizacionesH2 = aux primosH2
  where
    aux (x:xs) n 
      | x == n         = [[n]]
      | x > n          = []
      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n 
      | otherwise      = aux xs n 

primosH2 :: [Integer]
primosH2 = filter esPrimoH (tail numerosH) 
  where esPrimoH n = all noDivideAn [5,9..m]
          where noDivideAn x = n `mod` x /= 0
                m            = ceiling (sqrt (fromIntegral n))

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

-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo 
-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) × (4b + 3)
-- (ver en https://bit.ly/3zq7h4e ).

factorizacionesH3 :: Integer -> [[Integer]]
factorizacionesH3 = aux primosH3
  where
    aux (x:xs) n 
      | x == n         = [[n]]
      | x > n          = []
      | n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n 
      | otherwise      = aux xs n 

primosH3 :: [Integer]
primosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]
  where semiPrimoH n = length xs == 2 && all (\x -> (x-3) `mod` 4 == 0) xs
          where xs = primeFactors n

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_factorizacionesH :: Positive Integer -> Bool
prop_factorizacionesH (Positive n) =
  all (== factorizacionesH1 m)
      [factorizacionesH2 m,
       factorizacionesH3 m]
  where m = 1 + 4 * n
  
-- La comprobación es
--    λ> quickCheck prop_factorizacionesH
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> factorizacionesH1 80109
--    [[9,9,989],[9,69,129]]
--    (42.77 secs, 14,899,787,640 bytes)
--    λ> factorizacionesH2 80109
--    [[9,9,989],[9,69,129]]
--    (0.26 secs, 156,051,104 bytes)
--    λ> factorizacionesH3 80109
--    [[9,9,989],[9,69,129]]
--    (0.35 secs, 1,118,236,536 bytes)

-- Propiedad de factorización
-- ==========================

-- La propiedad es
prop_factorizable :: Positive Integer -> Bool
prop_factorizable (Positive n) =
  not (null (factorizacionesH1 (1 + 4 * n)))

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

100

101

102

103

104

105

106

107

108

109

110

111

import Data.Numbers.Primes (isPrime, primeFactors)

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

-- 1ª solución

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

factorizacionesH1 :: Integer -> [[Integer]]

factorizacionesH1 = aux primosH1

where

aux (x:xs) n

| x == n = [[n]]

| x > n = []

| n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n

| otherwise = aux xs n

primosH1 :: [Integer]

primosH1 = [n | n <- tail numerosH,

divisoresH n == [1,n]]

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,

-- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]

numerosH :: [Integer]

numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a

-- n. Por ejemplo,

-- divisoresH 117 == [1,9,13,117]

-- divisoresH 21 == [1,21]

divisoresH :: Integer -> [Integer]

divisoresH n = [x | x <- takeWhile (<=n) numerosH,

n `mod` x == 0]

-- 2ª solución

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

factorizacionesH2 :: Integer -> [[Integer]]

factorizacionesH2 = aux primosH2

where

aux (x:xs) n

| x == n = [[n]]

| x > n = []

| n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n

| otherwise = aux xs n

primosH2 :: [Integer]

primosH2 = filter esPrimoH (tail numerosH)

where esPrimoH n = all noDivideAn [5,9..m]

where noDivideAn x = n `mod` x /= 0

m = ceiling (sqrt (fromIntegral n))

-- 3ª solución

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

-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo

-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) × (4b + 3)

-- (ver en https://bit.ly/3zq7h4e ).

factorizacionesH3 :: Integer -> [[Integer]]

factorizacionesH3 = aux primosH3

where

aux (x:xs) n

| x == n = [[n]]

| x > n = []

| n `mod` x == 0 = map (x:) (aux (x:xs) (n `div` x) ) ++ aux xs n

| otherwise = aux xs n

primosH3 :: [Integer]

primosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]

where semiPrimoH n = length xs == 2 && all (\x -> (x-3) `mod` 4 == 0) xs

where xs = primeFactors n

-- Comprobación de equivalencia

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

-- La propiedad es

prop_factorizacionesH :: Positive Integer -> Bool

prop_factorizacionesH (Positive n) =

all (== factorizacionesH1 m)

[factorizacionesH2 m,

factorizacionesH3 m]

where m = 1 + 4 * n

-- La comprobación es

-- λ> quickCheck prop_factorizacionesH

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> factorizacionesH1 80109

-- [[9,9,989],[9,69,129]]

-- (42.77 secs, 14,899,787,640 bytes)

-- λ> factorizacionesH2 80109

-- [[9,9,989],[9,69,129]]

-- (0.26 secs, 156,051,104 bytes)

-- λ> factorizacionesH3 80109

-- [[9,9,989],[9,69,129]]

-- (0.35 secs, 1,118,236,536 bytes)

-- Propiedad de factorización

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

-- La propiedad es

prop_factorizable :: Positive Integer -> Bool

prop_factorizable (Positive n) =

not (null (factorizacionesH1 (1 + 4 * n)))

-- La comprobación es

-- λ> quickCheck prop_factorizable

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Referencias

Basado en el artículo Failure of unique factorization (A example of the failure of the fundamental theorem of arithmetic) de R.J. Lipton en el blog Gödel’s Lost Letter and P=NP.

Otras referencias

Wikipedia, Hilbert number.
E.W. Weisstein, Hilbert number en MathWorld.
N.J.A. Sloane, Sucesión A057948 en la OEIS.
N.J.A. Sloane, Sucesión A057949 en la OEIS.

Números primos de Hilbert

PorJosé A. Alonso 1-agosto-202223-julio-2022

Un número de Hilbert es un positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, …

Definir la sucesión

   primosH :: [Integer]

1	primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

   take 15 primosH     == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
   primosH !! (3*10^4) == 313661

1 2	take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! (3*10^4) == 313661

Soluciones

import Data.Numbers.Primes (isPrime, primeFactors) 
import Test.QuickCheck (NonNegative (NonNegative), quickCheck)

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

primosH1 :: [Integer]
primosH1 = [n | n <- tail numerosH,
                divisoresH n == [1,n]]

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,
--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]
numerosH :: [Integer]
numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a
-- n. Por ejemplo,
--   divisoresH 117  ==  [1,9,13,117]
--   divisoresH  21  ==  [1,21]
divisoresH :: Integer -> [Integer]
divisoresH n = [x | x <- takeWhile (<=n) numerosH,
                    n `mod` x == 0]

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

primosH2 :: [Integer]
primosH2 = filter esPrimoH (tail numerosH) 
  where esPrimoH n = all noDivideAn [5,9..m]
          where noDivideAn x = n `mod` x /= 0
                m            = ceiling (sqrt (fromIntegral n))

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

-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo 
-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) × (4b + 3)
-- (ver en https://bit.ly/3zq7h4e ).

primosH3 :: [Integer]
primosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]
  where semiPrimoH n = length xs == 2 && all (\x -> (x-3) `mod` 4 == 0) xs
          where xs = primeFactors n

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_primosH :: NonNegative Int -> Bool
prop_primosH (NonNegative n) =
  all (== primosH1 !! n)
      [primosH2 !! n,
       primosH3 !! n]

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

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

-- La comparación es
--    λ> primosH1 !! 2000
--    16957
--    (2.16 secs, 752,085,752 bytes)
--    λ> primosH2 !! 2000
--    16957
--    (0.03 secs, 19,771,008 bytes)
--    λ> primosH3 !! 2000
--    16957
--    (0.07 secs, 152,029,168 bytes)
--    
--    λ> primosH2 !! (3*10^4)
--    313661
--    (1.44 secs, 989,761,888 bytes)
--    λ> primosH3 !! (3*10^4)
--    313661
--    (2.06 secs, 6,554,068,992 bytes)

import Data.Numbers.Primes (isPrime, primeFactors)

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

-- 1ª solución

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

primosH1 :: [Integer]

primosH1 = [n | n <- tail numerosH,

divisoresH n == [1,n]]

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,

-- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]

numerosH :: [Integer]

numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a

-- n. Por ejemplo,

-- divisoresH 117 == [1,9,13,117]

-- divisoresH 21 == [1,21]

divisoresH :: Integer -> [Integer]

divisoresH n = [x | x <- takeWhile (<=n) numerosH,

n `mod` x == 0]

-- 2ª solución

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

primosH2 :: [Integer]

primosH2 = filter esPrimoH (tail numerosH)

where esPrimoH n = all noDivideAn [5,9..m]

where noDivideAn x = n `mod` x /= 0

m = ceiling (sqrt (fromIntegral n))

-- 3ª solución

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

-- Basada en la siguiente propiedad: Un primo de Hilbert es un primo

-- de la forma 4n + 1 o un semiprimo de la forma (4a + 3) × (4b + 3)

-- (ver en https://bit.ly/3zq7h4e ).

primosH3 :: [Integer]

primosH3 = [ n | n <- numerosH, isPrime n || semiPrimoH n ]

where semiPrimoH n = length xs == 2 && all (\x -> (x-3) `mod` 4 == 0) xs

where xs = primeFactors n

-- Comprobación de equivalencia

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

-- La propiedad es

prop_primosH :: NonNegative Int -> Bool

prop_primosH (NonNegative n) =

all (== primosH1 !! n)

[primosH2 !! n,

primosH3 !! n]

-- La comprobación es

-- λ> quickCheck prop_primosH

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> primosH1 !! 2000

-- 16957

-- (2.16 secs, 752,085,752 bytes)

-- λ> primosH2 !! 2000

-- 16957

-- (0.03 secs, 19,771,008 bytes)

-- λ> primosH3 !! 2000

-- 16957

-- (0.07 secs, 152,029,168 bytes)

-- λ> primosH2 !! (3*10^4)

-- 313661

-- (1.44 secs, 989,761,888 bytes)

-- λ> primosH3 !! (3*10^4)

-- 313661

-- (2.06 secs, 6,554,068,992 bytes)

El código se encuentra en GitHub.

Meses: agosto 2022

División segura

Tres diferentes

Tres iguales

Elemento mediano

Primeros y últimos elementos

Segmento de una lista

Elementos finales

Interior de una lista

Reconocimiento de palíndromos

Rango de una lista

Los primeros al final

El primero al final

Máximo de tres números

Último dígito

Área de la corona circular

Volumen de la esfera

Suma de monedas

Media aritmética de tres números

Curso de introducción a la programación con Haskell y Python

Números de Pentanacci

Soluciones

Referencias

Número de representaciones de n como suma de dos cuadrados

Soluciones

Referencias

Representaciones de un número como suma de dos cuadrados

Soluciones

Factorizaciones de números de Hilbert

Soluciones

Referencias

Números primos de Hilbert

Soluciones

Entradas recientes

Buscar

Correo electrónico