3
     7 4
    2 4 6
   8 5 9 3

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

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

   λ> 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]]

module Caminos_en_un_triangulo where

import Test.Hspec (Spec, hspec, it, shouldBe)

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)]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminos [[3],[7,4]] `shouldBe`
    [[3,7],[3,4]]
  it "e2" $
    caminos [[3],[7,4],[2,4,6]] `shouldBe`
    [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
  it "e3" $
    caminos [[3],[7,4],[2,4,6],[8,5,9,3]] `shouldBe`
    [[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]]

-- La verificación es
--    λ> verifica
--
--    3 examples, 0 failures

from typing import TypeVar

A = TypeVar('A')

def caminos(xss: list[list[A]]) -> list[list[A]]:
    if not xss:
        return [[]]
    if len(xss) == 1:
        return xss
    x = xss[0][0]
    y1 = xss[1][0]
    y2 = xss[1][1]
    zss = xss[2:]
    return [[x, y1] + us for _, *us in caminos([[y1]] + [zs[:-1] for zs in zss])] + \
           [[x, y2] + us for _, *us in caminos([[y2]] + [zs[1:] for zs in zss])]

# Verificación
# ============

def test_caminos() -> None:
    assert caminos([[3],[7,4]]) == \
        [[3,7],[3,4]]
    assert caminos([[3],[7,4],[2,4,6]]) == \
        [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
    assert 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]]
    print("Verificado")

# La verificación es
#    >>> test_caminos()
#    Verificado

      3
     7 4
    2 4 6
   8 5 9 3

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

   maximaSuma :: [[Integer]] -> Integer

   maximaSuma [[3],[7,4]]                    ==  10
   maximaSuma [[3],[7,4],[2,4,6]]            ==  14
   maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]]  ==  23
   maximaSuma [[n..n+n] | n <- [0..100]]     ==  10100
   maximaSuma [[n..n+n] | n <- [0..1000]]    ==  1001000
   maximaSuma [[n..n+n] | n <- [0..2000]]    ==  4002000
   maximaSuma [[n..n+n] | n <- [0..3000]]    ==  9003000
   maximaSuma [[n..n+n] | n <- [0..4000]]    ==  16004000

module Maxima_suma_de_caminos_en_un_triangulo where

import Data.List (tails)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

maximaSuma1 :: [[Integer]] -> Integer
maximaSuma1 xss =
  maximum [sum ys | ys <- caminos xss]

caminos :: [[Integer]] -> [[Integer]]
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)]

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

maximaSuma2 :: [[Integer]] -> Integer
maximaSuma2 xss = maximum (map sum (caminos xss))

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

maximaSuma3 :: [[Integer]] -> Integer
maximaSuma3 = maximum . map sum . caminos

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

maximaSuma4 :: [[Integer]] -> Integer
maximaSuma4 []    = 0
maximaSuma4 [[x]] = x
maximaSuma4 ([x]:[y1,y2]:zs) =
  x + max (maximaSuma4 ([y1] : map init zs))
          (maximaSuma4 ([y2] : map tail zs))

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

maximaSuma5 :: [[Integer]] -> Integer
maximaSuma5 xss = head (foldr1 g xss)
  where
    f x y z = x + max y z
    g xs ys = zipWith3 f xs ys (tail ys)

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

maximaSuma6 :: [[Integer]] -> Integer
maximaSuma6 xss = head (foldr1 aux xss)
  where aux a b = zipWith (+) a (zipWith max b (tail b))

-- 7ª solución
-- ===========

maximaSuma7 :: [[Integer]] -> Integer
maximaSuma7 xss = head (foldr (flip f) (last xss) (init xss))
  where f = zipWith ((+) . maximum . take 2) . tails

-- 8ª solución
-- ===========

maximaSuma8 :: [[Integer]] -> Integer
maximaSuma8 = head . foldr1 aux
  where
    aux [] _              = []
    aux (x:xs) (y0:y1:ys) = x + max y0 y1 : aux xs (y1:ys)

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

-- Para la comparaciones se usará la siguiente función que construye un
-- triángulo de la altura dada. Por ejemplo,
--    triangulo 2  ==  [[0],[1,2]]
--    triangulo 3  ==  [[0],[1,2],[2,3,4]]
--    triangulo 4  ==  [[0],[1,2],[2,3,4],[3,4,5,6]]
triangulo :: Integer -> [[Integer]]
triangulo n = [[k..k+k] | k <- [0..n-1]]

-- La comparación es
--    (1.97 secs, 876,483,056 bytes)
--    λ> maximaSuma1 (triangulo 19)
--    342
--    (2.37 secs, 1,833,637,824 bytes)
--    λ> maximaSuma2 (triangulo 19)
--    342
--    (2.55 secs, 1,804,276,472 bytes)
--    λ> maximaSuma3 (triangulo 19)
--    342
--    (2.57 secs, 1,804,275,320 bytes)
--    λ> maximaSuma4 (triangulo 19)
--    342
--    (0.28 secs, 245,469,384 bytes)
--    λ> maximaSuma5 (triangulo 19)
--    342
--    (0.01 secs, 153,272 bytes)
--    λ> maximaSuma6 (triangulo 19)
--    342
--    (0.01 secs, 161,360 bytes)
--    λ> maximaSuma7 (triangulo 19)
--    342
--    (0.01 secs, 187,456 bytes)
--    λ> maximaSuma8 (triangulo 19)
--    342
--    (0.01 secs, 191,160 bytes)
--
--    λ> maximaSuma4 (triangulo 22)
--    462
--    (2.30 secs, 1,963,037,888 bytes)
--    λ> maximaSuma5 (triangulo 22)
--    462
--    (0.00 secs, 173,512 bytes)
--    λ> maximaSuma6 (triangulo 22)
--    462
--    (0.01 secs, 182,904 bytes)
--    λ> maximaSuma7 (triangulo 22)
--    462
--    (0.01 secs, 216,560 bytes)
--    λ> maximaSuma8 (triangulo 22)
--    462
--    (0.01 secs, 224,160 bytes)
--
--    λ> maximaSuma5 (triangulo 3000)
--    8997000
--    (2.25 secs, 2,059,784,792 bytes)
--    λ> maximaSuma6 (triangulo 3000)
--    8997000
--    (2.15 secs, 2,404,239,896 bytes)
--    λ> maximaSuma7 (triangulo 3000)
--    8997000
--    (1.53 secs, 2,612,659,504 bytes)
--    λ> maximaSuma8 (triangulo 3000)
--    8997000
--    (3.47 secs, 3,520,910,256 bytes)
--
--    λ> maximaSuma7 (triangulo 4000)
--    15996000
--    (3.12 secs, 4,634,841,200 bytes)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([[Integer]] -> Integer) -> Spec
specG maximaSuma = do
  it "e1" $
    maximaSuma [[3],[7,4]]                    `shouldBe`  10
  it "e2" $
    maximaSuma [[3],[7,4],[2,4,6]]            `shouldBe`  14
  it "e3" $
    maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]]  `shouldBe`  23

spec :: Spec
spec = do
  describe "def. 1" $ specG maximaSuma1
  describe "def. 2" $ specG maximaSuma2
  describe "def. 3" $ specG maximaSuma3
  describe "def. 4" $ specG maximaSuma4
  describe "def. 5" $ specG maximaSuma5
  describe "def. 6" $ specG maximaSuma6
  describe "def. 7" $ specG maximaSuma7
  describe "def. 8" $ specG maximaSuma8

-- La verificación es
--    λ> verifica
--    Finished in 0.0053 seconds
--    24 examples, 0 failures

from timeit import Timer, default_timer

# 1ª solución
# ===========

def caminos(xss: list[list[int]]) -> list[list[int]]:
    if not xss:
        return [[]]
    if len(xss) == 1:
        return xss
    x = xss[0][0]
    y1 = xss[1][0]
    y2 = xss[1][1]
    zss = xss[2:]
    return [[x, y1] + us for _, *us in caminos([[y1]] + [zs[:-1] for zs in zss])] + \
           [[x, y2] + us for _, *us in caminos([[y2]] + [zs[1:] for zs in zss])]

# maximaSuma1 :: [[Integer]] -> Integer
def maximaSuma1(xss: list[list[int]]) -> int:
    return max((sum(ys) for ys in caminos(xss)))

# 2ª solución
# ===========

def maximaSuma2(xss: list[list[int]]) -> int:
    if not xss:
        return 0
    if len(xss) == 1:
        return xss[0][0]
    x = xss[0][0]
    y1 = xss[1][0]
    y2 = xss[1][1]
    zss = xss[2:]
    return x + max(maximaSuma2([[y1]] + [us[:-1] for us in zss]),
                   maximaSuma2([[y2]] + [us[1:] for us in zss]))

# Verificación
# ============

def test_maximaSuma() -> None:
    for maximaSuma in [maximaSuma1, maximaSuma2]:
        assert maximaSuma([[3],[7,4]]) == 10
        assert maximaSuma([[3],[7,4],[2,4,6]]) == 14
        assert maximaSuma([[3],[7,4],[2,4,6],[8,5,9,3]]) == 23
    print("Verificado")

# La verificación es
#    >>> test_maximaSuma()
#    Verificado

# Comparación de eficiencia
# =========================

# Para la comparaciones se usará la siguiente función que construye un
# triángulo de la altura dada. Por ejemplo,
#    >>> triangulo(2)
#    [[0], [1, 2]]
#    >>> triangulo(3)
#    [[0], [1, 2], [2, 3, 4]]
#    >>> triangulo(4)
#    [[0], [1, 2], [2, 3, 4], [3, 4, 5, 6]]
def triangulo(n: int) -> list[list[int]]:
    return [list(range(k, k+k+1)) for k in range(n)]

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('maximaSuma1(triangulo(20))')
#    3.21 segundos
#    >>> tiempo('maximaSuma2(triangulo(20))')
#    0.59 segundos

   amigos :: Integer -> Integer -> Bool

   amigos 220 284 == True
   amigos 220 23  == False
   amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True

module Numeros_amigos where

import Data.List (genericLength, group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

amigos1 :: Integer -> Integer -> Bool
amigos1 x y = sumaDivisoresPropios1 x == y &&
              sumaDivisoresPropios1 y == x

-- (sumaDivisoresPropios1 x) es la suma de los divisores propios de
-- x. Por ejemplo,
--    sumaDivisoresPropios1 220  ==  284
--    sumaDivisoresPropios1 284  ==  220
sumaDivisoresPropios1 :: Integer -> Integer
sumaDivisoresPropios1 = sum . divisoresPropios1

-- (divisoresPropios1 x) es la lista de los divisores propios de x. Por
-- ejemplo,
--    divisoresPropios1 220  ==  [1,2,4,5,10,11,20,22,44,55,110]
--    divisoresPropios1 284  ==  [1,2,4,71,142]
divisoresPropios1 :: Integer -> [Integer]
divisoresPropios1 x = [n | n <- [1..x-1], x `mod` n == 0]

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

amigos2 :: Integer -> Integer -> Bool
amigos2 x y = sumaDivisoresPropios2 x == y &&
              sumaDivisoresPropios2 y == x

sumaDivisoresPropios2 :: Integer -> Integer
sumaDivisoresPropios2 = sum . divisoresPropios2

divisoresPropios2 :: Integer -> [Integer]
divisoresPropios2 x = filter ((== 0) . mod x) [1..x-1]

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

amigos3 :: Integer -> Integer -> Bool
amigos3 x y = sumaDivisoresPropios3 x == y &&
              sumaDivisoresPropios3 y == x

sumaDivisoresPropios3 :: Integer -> Integer
sumaDivisoresPropios3 = sum . divisoresPropios3

divisoresPropios3 :: Integer -> [Integer]
divisoresPropios3 =
  init . nub . sort . map product . subsequences . primeFactors

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

amigos4 :: Integer -> Integer -> Bool
amigos4 x y = sumaDivisoresPropios4 x == y &&
              sumaDivisoresPropios4 y == x

sumaDivisoresPropios4 :: Integer -> Integer
sumaDivisoresPropios4 = sum . divisoresPropios4

divisoresPropios4 :: Integer -> [Integer]
divisoresPropios4 =
  init
  . sort
  . map (product . concat)
  . productoCartesiano
  . map inits
  . group
  . primeFactors

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

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

amigos5 :: Integer -> Integer -> Bool
amigos5 x y = sumaDivisoresPropios5 x == y &&
              sumaDivisoresPropios5 y == x

sumaDivisoresPropios5 :: Integer -> Integer
sumaDivisoresPropios5 =
  sum . divisoresPropios5

divisoresPropios5 :: Integer -> [Integer]
divisoresPropios5 =
  init
  . sort
  . map (product . concat)
  . sequence
  . map inits
  . group
  . primeFactors

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

amigos6 :: Integer -> Integer -> Bool
amigos6 x y = sumaDivisoresPropios6 x == y &&
              sumaDivisoresPropios6 y == x

sumaDivisoresPropios6 :: Integer -> Integer
sumaDivisoresPropios6 =
  sum
  . init
  . map (product . concat)
  . sequence
  . map inits
  . group
  . primeFactors

-- 7ª solución                                                   --
-- ===========

amigos7 :: Integer -> Integer -> Bool
amigos7 x y = sumaDivisoresPropios7 x == y &&
              sumaDivisoresPropios7 y == x

-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
--   ------------------- . ------------------- ... -------------------
--        p(1)-1                p(2)-1                  p(n)-1
-- Ver la demostración en http://bit.ly/2zUXZPc

-- (sumaDivisoresPropios7 x) es la suma de los divisores propios de
-- x. Por ejemplo,
--    sumaDivisoresPropios7 220  ==  284
--    sumaDivisoresPropios7 284  ==  220
sumaDivisoresPropios7 :: Integer -> Integer
sumaDivisoresPropios7 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - x

-- (factorizacion x) es la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) = (x, 1 + genericLength xs)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer -> Bool) -> Spec
specG amigos = do
  it "e1" $
    amigos 220 284 `shouldBe` True
  it "e2" $
    amigos 220 23  `shouldBe` False

spec :: Spec
spec = do
  describe "def. 1" $ specG amigos1
  describe "def. 2" $ specG amigos2
  describe "def. 3" $ specG amigos3
  describe "def. 4" $ specG amigos4
  describe "def. 5" $ specG amigos5
  describe "def. 6" $ specG amigos6
  describe "def. 7" $ specG amigos7

-- La verificación es
--    λ> verifica
--    14 examples, 0 failures

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

-- La comparación es
--    λ> amigos1 2803580 3716164
--    True
--    (2.27 secs, 1,304,055,864 bytes)
--    λ> amigos2 2803580 3716164
--    True
--    (0.81 secs, 782,478,584 bytes)
--    λ> amigos3 2803580 3716164
--    True
--    (0.01 secs, 383,888 bytes)
--    λ> amigos4 2803580 3716164
--    True
--    (0.01 secs, 461,376 bytes)
--    λ> amigos5 2803580 3716164
--    True
--    (0.00 secs, 412,560 bytes)
--    λ> amigos6 2803580 3716164
--    True
--    (0.00 secs, 387,816 bytes)
--    λ> amigos7 2803580 3716164
--    True
--    (0.01 secs, 339,008 bytes)
--
--    λ> amigos2 5864660 7489324
--    True
--    (1.74 secs, 1,602,582,592 bytes)
--    λ> amigos3 5864660 7489324
--    True
--    (0.00 secs, 277,056 bytes)
--    λ> amigos4 5864660 7489324
--    True
--    (0.01 secs, 354,872 bytes)
--    λ> amigos5 5864660 7489324
--    True
--    (0.01 secs, 305,792 bytes)
--    λ> amigos6 5864660 7489324
--    True
--    (0.00 secs, 281,528 bytes)
--    λ> amigos7 5864660 7489324
--    True
--    (0.01 secs, 237,176 bytes)
--
--    λ> amigos3 42262694537514864075544955198125 42405817271188606697466971841875
--    True
--    (107.54 secs, 5,594,306,392 bytes)
--    λ> amigos4 42262694537514864075544955198125 42405817271188606697466971841875
--    True
--    (1.03 secs, 942,530,824 bytes)
--    λ> amigos5 42262694537514864075544955198125 42405817271188606697466971841875
--    True
--    (0.51 secs, 591,144,304 bytes)
--    λ> amigos6 42262694537514864075544955198125 42405817271188606697466971841875
--    True
--    (0.26 secs, 379,534,608 bytes)
--    λ> amigos7 42262694537514864075544955198125 42405817271188606697466971841875
--    True
--    (0.05 secs, 25,635,464 bytes)

from functools import reduce
from operator import mul
from timeit import Timer, default_timer

from sympy import divisor_sigma, factorint, is_amicable, proper_divisors

# 1ª solución
# ===========

# divisoresPropios1(x) es la lista de los divisores propios de x. Por
# ejemplo,
#    divisoresPropios1(220)  ==  [1,2,4,5,10,11,20,22,44,55,110]
#    divisoresPropios1(284)  ==  [1,2,4,71,142]
def divisoresPropios1(x: int) -> list[int]:
    return [n for n in range(1, x) if x % n == 0]

# sumaDivisoresPropios1(x) es la suma de los divisores propios de
# x. Por ejemplo,
#    sumaDivisoresPropios1(220)  ==  284
#    sumaDivisoresPropios1(284)  ==  220
def sumaDivisoresPropios1(x: int) -> int:
    return sum(divisoresPropios1(x))

def amigos1(x: int, y: int) -> bool:
    return sumaDivisoresPropios1(x)== y and \
           sumaDivisoresPropios1(y)== x

# 2ª solución
# ===========

def divisoresPropios2(x: int) -> list[int]:
    return proper_divisors(x)

def sumaDivisoresPropios2(x: int) -> int:
    return sum(divisoresPropios2(x))

def amigos2(x: int, y: int) -> bool:
    return sumaDivisoresPropios2(x)== y and \
           sumaDivisoresPropios2(y)== x

# 3ª solución
# ===========

# Si la descomposición de x en factores primos es
#    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
# entonces la suma de los divisores de x es
#    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
#   ------------------- . ------------------- ... -------------------
#        p(1)-1                p(2)-1                  p(n)-1
# Ver la demostración en http://bit.ly/2zUXZPc

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([2, 3, 5]) == 30
def producto(xs: list[int]) -> int:
    return reduce(mul, xs)

# sumaDivisoresPropios3(x) es la suma de los divisores propios de
# x. Por ejemplo,
#    sumaDivisoresPropios3(220)  ==  284
#    sumaDivisoresPropios3(284)  ==  220
def sumaDivisoresPropios3(x: int) -> int:
    return producto([(p**(e+1)-1) // (p-1)
                     for (p,e) in factorint(x).items()]) - x

def amigos3(x: int, y: int) -> bool:
    return sumaDivisoresPropios3(x)== y and \
           sumaDivisoresPropios3(y)== x

# 4ª solución
# ===========

def amigos4(x: int, y: int) -> bool:
    return divisor_sigma(x, 1) == divisor_sigma(y, 1)

# 5ª solución
# ===========

def amigos5(x: int, y: int) -> bool:
    return is_amicable(x, y)

# Verificación
# ============

def test_amigos() -> None:
    for amigos in [amigos1, amigos2, amigos3, amigos4, amigos5]:
        assert amigos(220, 284)
        assert not amigos(220, 23)
    print("Verificado")

# La verificación es
#    >>> test_amigos()
#    Verificado

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('amigos1(5864660, 7489324)')
#    0.65 segundos
#    >>> tiempo('amigos2(5864660, 7489324)')
#    0.00 segundos
#    >>> tiempo('amigos3(5864660, 7489324)')
#    0.00 segundos
#    >>> tiempo('amigos4(5864660, 7489324)')
#    0.00 segundos
#    >>> tiempo('amigos5(5864660, 7489324)')
#    0.00 segundos
#
#    >>> x = 42262694537514864075544955198125
#    >>> y = 42405817271188606697466971841875
#    >>> tiempo('amigos2(x, y)')
#    0.10 segundos
#    >>> tiempo('amigos3(x, y)')
#    0.00 segundos
#    >>> tiempo('amigos4(x, y)')
#    0.00 segundos
#    >>> tiempo('amigos5(x, y)')
#    0.00 segundos

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

   take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
   take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
   take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
   take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]
   primosEquidistantes 4 !! (10^5) ==  (18467047,18467051)

module Primos_equidistantes where

import Data.Numbers.Primes (primes)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

primosEquidistantes1 :: Integer -> [(Integer,Integer)]
primosEquidistantes1 k = aux primos
  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)
                     | otherwise  = aux (y:ps)

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

-- primos es la lista de los números primos. Por ejemplo,
--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]

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

primosEquidistantes2 :: Integer -> [(Integer,Integer)]
primosEquidistantes2 k = aux primos2
  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)
                     | otherwise  = aux (y:ps)

primos2 :: [Integer]
primos2 = criba [2..]
  where criba (p:ps) = p : criba [n | n <- ps, mod n p /= 0]

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

primosEquidistantes3 :: Integer -> [(Integer,Integer)]
primosEquidistantes3 k =
  [(x,y) | (x,y) <- zip primos2 (tail primos2)
         , y - x == k]

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

primosEquidistantes4 :: Integer -> [(Integer,Integer)]
primosEquidistantes4 k = aux primes
  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)
                     | otherwise  = aux (y:ps)

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

primosEquidistantes5 :: Integer -> [(Integer,Integer)]
primosEquidistantes5 k =
  [(x,y) | (x,y) <- zip primes (tail primes)
         , y - x == k]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> [(Integer,Integer)]) -> Spec
specG primosEquidistantes = do
  it "e1" $
    take 3 (primosEquidistantes 2) `shouldBe` [(3,5),(5,7),(11,13)]
  it "e2" $
    take 3 (primosEquidistantes 4) `shouldBe` [(7,11),(13,17),(19,23)]
  it "e3" $
    take 3 (primosEquidistantes 6) `shouldBe` [(23,29),(31,37),(47,53)]
  it "e4" $
    take 3 (primosEquidistantes 8) `shouldBe` [(89,97),(359,367),(389,397)]

spec :: Spec
spec = do
  describe "def. 1" $ specG primosEquidistantes1
  describe "def. 2" $ specG primosEquidistantes2
  describe "def. 3" $ specG primosEquidistantes3
  describe "def. 4" $ specG primosEquidistantes4
  describe "def. 5" $ specG primosEquidistantes5

-- La verificación es
--    λ> verifica
--    20 examples, 0 failures

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

-- La propiedad es
prop_primosEquidistantes :: Int -> Integer -> Bool
prop_primosEquidistantes n k =
  all (== take n (primosEquidistantes1 k))
      [take n (f k) | f <- [primosEquidistantes2,
                            primosEquidistantes3,
                            primosEquidistantes4,
                            primosEquidistantes5]]

-- La comprobación es
--    λ> prop_primosEquidistantes 100 4
--    True

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

-- La comparación es
--    λ> primosEquidistantes1 4 !! 200
--    (9829,9833)
--    (2.60 secs, 1,126,458,272 bytes)
--    λ> primosEquidistantes2 4 !! 200
--    (9829,9833)
--    (0.44 secs, 249,622,048 bytes)
--    λ> primosEquidistantes3 4 !! 200
--    (9829,9833)
--    (0.36 secs, 207,549,592 bytes)
--    λ> primosEquidistantes4 4 !! 200
--    (9829,9833)
--    (0.02 secs, 4,012,848 bytes)
--    λ> primosEquidistantes5 4 !! 200
--    (9829,9833)
--    (0.01 secs, 7,085,072 bytes)
--
--    λ> primosEquidistantes2 4 !! 600
--    (41617,41621)
--    (5.67 secs, 3,340,313,480 bytes)
--    λ> primosEquidistantes3 4 !! 600
--    (41617,41621)
--    (5.43 secs, 3,090,994,096 bytes)
--    λ> primosEquidistantes4 4 !! 600
--    (41617,41621)
--    (0.03 secs, 15,465,824 bytes)
--    λ> primosEquidistantes5 4 !! 600
--    (41617,41621)
--    (0.04 secs, 28,858,232 bytes)
--
--    λ> primosEquidistantes4 4 !! (10^5)
--    (18467047,18467051)
--    (3.99 secs, 9,565,715,488 bytes)
--    λ> primosEquidistantes5 4 !! (10^5)
--    (18467047,18467051)
--    (7.95 secs, 18,712,469,144 bytes)

from itertools import chain, count, islice, tee
from timeit import Timer, default_timer
from typing import Iterator

from sympy import isprime

# 1ª solución
# ===========

# primo(x) se verifica si x es primo. Por ejemplo,
#    primo(7)  ==  True
#    primo(8)  ==  False
def primo(x: int) -> bool:
    return [y for y in range(1,x+1) if x % y == 0] == [1,x]

# primos() es la lista de los números primos. Por ejemplo,
#    >>> list(islice(primos(), 10))
#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def primos() -> Iterator[int]:
    return chain([2], (x for x in count(3, 2) if primo(x)))

def primosEquidistantes1(k: int) -> Iterator[tuple[int,int]]:
    a, b = tee(primos())
    next(b, None)
    return ((x,y) for (x,y) in zip(a, b) if y - x == k)

# 2ª solución
# ===========

def primos2() -> Iterator[int]:
    return (n for n in count() if isprime(n))

def primosEquidistantes2(k: int) -> Iterator[tuple[int,int]]:
    a, b = tee(primos2())
    next(b, None)
    return ((x,y) for (x,y) in zip(a, b) if y - x == k)

# Verificación
# ============

def test_primosEquidestantes() -> None:
    for primosEquidistantes in [primosEquidistantes1,
                                primosEquidistantes2]:
        assert list(islice(primosEquidistantes(2), 3)) == \
            [(3, 5), (5, 7), (11, 13)]
        assert list(islice(primosEquidistantes(4), 3)) == \
            [(7, 11), (13, 17), (19, 23)]
        assert list(islice(primosEquidistantes(6), 3)) == \
            [(23, 29), (31, 37), (47, 53)]
        assert list(islice(primosEquidistantes(8), 3)) == \
            [(89, 97), (359, 367), (389, 397)]
    print("Verificado")

# La verificación es
#    >>> test_primosEquidestantes()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
def primosEquidistantes_equiv(n: int, k: int) -> bool:
    return list(islice(primosEquidistantes1(k), n)) == \
           list(islice(primosEquidistantes2(k), n))

# La comprobación es
#    >>> primosEquidistantes_equiv(100, 4)
#    True

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('list(islice(primosEquidistantes1(4), 300))')
#    3.19 segundos
#    >>> tiempo('list(islice(primosEquidistantes2(4), 300))')
#    0.01 segundos

   (0,0,0),
   (0,0,1),(0,1,0),(1,0,0),
   (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),
   (0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...
   ...

   posicion :: (Int,Int,Int) -> Int

   posicion (0,1,0)  ==  2
   posicion (0,0,2)  ==  4
   posicion (0,1,1)  ==  5

import Data.List (elemIndex)
import Data.Maybe (fromJust)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

posicion1 :: (Int,Int,Int) -> Int
posicion1 t = aux 0 ternas
  where aux n (t':ts) | t' == t   = n
                      | otherwise = aux (n+1) ts

-- ternas es la lista ordenada de las ternas de números naturales. Por ejemplo,
--    λ> take 9 ternas
--    [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)]
ternas :: [(Int,Int,Int)]
ternas = [(x,y,n-x-y) | n <- [0..], x <- [0..n], y <- [0..n-x]]

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

posicion2 :: (Int,Int,Int) -> Int
posicion2 t =
  head [n | (n,t') <- zip [0..] ternas, t' == t]

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

posicion3 :: (Int,Int,Int) -> Int
posicion3 t = indice t ternas

-- (indice x ys) es el índice de x en ys. Por ejemplo,
--    indice 5 [0..]  ==  5
indice :: Eq a => a -> [a] -> Int
indice x ys = length (takeWhile (/= x) ys)

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

posicion4 :: (Int,Int,Int) -> Int
posicion4 t = fromJust (elemIndex t ternas)

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

posicion5 :: (Int,Int,Int) -> Int
posicion5 = fromJust . (`elemIndex` ternas)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ((Int,Int,Int) -> Int) -> Spec
specG posicion = do
  it "e1" $
    posicion (0,1,0)  `shouldBe`  2
  it "e2" $
    posicion (0,0,2)  `shouldBe`  4
  it "e3" $
    posicion (0,1,1)  `shouldBe`  5

spec :: Spec
spec = do
  describe "def. 1" $ specG posicion1
  describe "def. 2" $ specG posicion2
  describe "def. 3" $ specG posicion3
  describe "def. 4" $ specG posicion4
  describe "def. 5" $ specG posicion5

-- La verificación es
--    λ> verifica
--    15 examples, 0 failures

-- Equivalencia
-- ============

-- La propiedad es
prop_posicion_equiv :: NonNegative Int
                    -> NonNegative Int
                    -> NonNegative Int
                    -> Bool
prop_posicion_equiv (NonNegative x) (NonNegative y) (NonNegative z) =
  all (== posicion1 (x,y,z))
      [f (x,y,z) | f <- [ posicion2
                        , posicion3
                        , posicion4
                        , posicion5 ]]

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

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

-- La comparación es
--    λ> posicion1 (147,46,116)
--    5000000
--    (5.84 secs, 2,621,428,184 bytes)
--    λ> posicion2 (147,46,116)
--    5000000
--    (3.63 secs, 2,173,230,200 bytes)
--    λ> posicion3 (147,46,116)
--    5000000
--    (2.48 secs, 1,453,229,880 bytes)
--    λ> posicion4 (147,46,116)
--    5000000
--    (1.91 secs, 1,173,229,840 bytes)
--    λ> posicion5 (147,46,116)
--    5000000
--    (1.94 secs, 1,173,229,960 bytes)

-- Propiedades
-- ===========

-- La 1ª propiedad es
prop_posicion1 :: NonNegative Int -> Bool
prop_posicion1 (NonNegative x) =
  posicion5 (x,0,0) == x * (x^2 + 6*x + 11) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion1
--    +++ OK, passed 100 tests.

-- La 2ª propiedad es
prop_posicion2 :: NonNegative Int -> Bool
prop_posicion2 (NonNegative y) =
  posicion5 (0,y,0) == y * (y^2 + 3*y + 8) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion2
--    +++ OK, passed 100 tests.

-- La 3ª propiedad es
prop_posicion3 :: NonNegative Int -> Bool
prop_posicion3 (NonNegative z) =
  posicion5 (0,0,z) == z * (z^2 + 3*z + 2) `div` 6

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion3
--    +++ OK, passed 100 tests.

-- La 4ª propiedad es
prop_posicion4 :: NonNegative Int -> Bool
prop_posicion4 (NonNegative x) =
  posicion5 (x,x,x) == x * (9 * x^2 + 14 * x + 7) `div` 2

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_posicion4
--    +++ OK, passed 100 tests.

from itertools import count, islice, takewhile
from timeit import Timer, default_timer
from typing import Iterator

from hypothesis import given
from hypothesis import strategies as st

# 1ª solución
# ===========

# ternas es la lista ordenada de las ternas de números naturales. Por ejemplo,
#    >>> list(islice(ternas(), 9))
#    [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)]
def ternas() -> Iterator[tuple[int, int, int]]:
    return ((x, y, n-x-y)
            for n in count()
            for x in range(n+1)
            for y in range(n-x+1))

def posicion1(t: tuple[int,int,int]) -> int:
    r = 0
    for t1 in ternas():
        if t == t1:
            return r
        r = r + 1
    return -1

# 2ª solución
# ===========

def posicion2(t: tuple[int,int,int]) -> int:
    for (n,t1) in enumerate(ternas()):
        if t1 == t:
            return n
    return -1

# 3ª solución
# ===========

def posicion3(t: tuple[int,int,int]) -> int:
    return len(list(takewhile(lambda t1 : t1 != t, ternas())))

# Verificación
# ============

def test_posicion() -> None:
    assert list(islice(ternas(), 9)) == \
        [(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0)]
    for posicion in [posicion1, posicion2, posicion3]:
        assert posicion((0,1,0)) == 2
        assert posicion((0,0,2)) == 4
        assert posicion((0,1,1)) == 5
    print("Verificado")

# La verificación es
#    >>> test_posicion()
#    Verificado

# Equivalencia
# ============

@given(st.integers(min_value=1, max_value=10),
       st.integers(min_value=1, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_posicion_equiv(x: int, y: int, z: int) -> None:
    r = posicion1((x, y, z))
    assert posicion2((x, y, z)) == r
    assert posicion3((x, y, z)) == r

# La comprobación es
#    >>> test_posicion_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")


# La comparación es
#    >>> tiempo('posicion1((147,46,116))')
#    0.72 segundos
#    >>> tiempo('posicion2((147,46,116))')
#    0.68 segundos
#    >>> tiempo('posicion3((147,46,116))')
#    0.93 segundos

# Propiedades
# ===========

# La 1ª propiedad es
@given(st.integers(min_value=1, max_value=100))
def prop_posicion1(x: int) -> None:
    assert posicion1((x,0,0)) == x * (x**2 + 6*x + 11) // 6

# Su comprobación es
#    >>> prop_posicion1()
#    >>>

# La 2ª propiedad es
@given(st.integers(min_value=1, max_value=100))
def prop_posicion2(y: int) -> None:
    assert posicion1((0,y,0)) == y * (y**2 + 3*y + 8) // 6

# Su comprobación es
#    >>> prop_posicion2()
#    >>>

# La 3ª propiedad es
@given(st.integers(min_value=1, max_value=100))
def prop_posicion3(z: int) -> None:
    assert posicion1((0,0,z)) == z * (z**2 + 3*z + 2) // 6

# Su comprobación es
#    >>> prop_posicion3()
#    >>>

# La 4ª propiedad es
@given(st.integers(min_value=1, max_value=10))
def prop_posicion4(x: int) -> None:
    assert posicion1((x,x,x)) == x * (9 * x**2 + 14 * x + 7) // 2

# Su comprobación es
#    >>> prop_posicion4()
#    >>>

   *     *      *
        * *    * *
              * * *
   1     3      6

    1 = 1
    3 = 1 + 2
    6 = 1 + 2 + 3
   10 = 1 + 2 + 3 + 4
   15 = 1 + 2 + 3 + 4 + 5

   triangularesConCifras :: Int -> [Integer]

   take 6 (triangularesConCifras 1)   ==  [1,3,6,55,66,666]
   take 6 (triangularesConCifras 2)   ==  [10,15,21,28,36,45]
   take 6 (triangularesConCifras 3)   ==  [105,120,136,153,190,210]
   take 5 (triangularesConCifras 4)   ==  [1035,1275,1326,1378,1485]
   take 2 (triangularesConCifras 10)  ==  [1062489753,1239845706]

import Data.List (nub)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

triangularesConCifras1 :: Int -> [Integer]
triangularesConCifras1 n =
  [x | x <- triangulares1,
       nCifras x == n]

-- triangulares1 es la lista de los números triangulares. Por ejemplo,
--    take 10 triangulares1 == [1,3,6,10,15,21,28,36,45,55]
triangulares1 :: [Integer]
triangulares1 = map triangular [1..]

triangular :: Integer -> Integer
triangular 1 = 1
triangular n = triangular (n-1) + n

-- (nCifras x) es el número de cifras distintas del número x. Por
-- ejemplo,
--    nCifras 325275  ==  4
nCifras :: Integer -> Int
nCifras = length . nub . show

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

triangularesConCifras2 :: Int -> [Integer]
triangularesConCifras2 n =
  [x | x <- triangulares2,
       nCifras x == n]

triangulares2 :: [Integer]
triangulares2 = [(n*(n+1)) `div` 2 | n <- [1..]]

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

triangularesConCifras3 :: Int -> [Integer]
triangularesConCifras3 n =
  [x | x <- triangulares3,
       nCifras x == n]

triangulares3 :: [Integer]
triangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares3]

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

triangularesConCifras4 :: Int -> [Integer]
triangularesConCifras4 n =
  [x | x <- triangulares4,
       nCifras x == n]

triangulares4 :: [Integer]
triangulares4 = 1 : zipWith (+) [2..] triangulares4

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

triangularesConCifras5 :: Int -> [Integer]
triangularesConCifras5 n =
  [x | x <- triangulares5,
       nCifras x == n]

triangulares5 :: [Integer]
triangulares5 = scanl (+) 1 [2..]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Int -> [Integer]) -> Spec
specG triangularesConCifras = do
  it "e1" $
    take 6 (triangularesConCifras 1) `shouldBe` [1,3,6,55,66,666]
  it "e2" $
    take 6 (triangularesConCifras 2) `shouldBe` [10,15,21,28,36,45]
  it "e3" $
    take 6 (triangularesConCifras 3) `shouldBe` [105,120,136,153,190,210]
  it "e4" $
    take 5 (triangularesConCifras 4) `shouldBe` [1035,1275,1326,1378,1485]

spec :: Spec
spec = do
  describe "def. 1" $ specG triangularesConCifras1
  describe "def. 2" $ specG triangularesConCifras2
  describe "def. 3" $ specG triangularesConCifras3
  describe "def. 4" $ specG triangularesConCifras4
  describe "def. 5" $ specG triangularesConCifras5

-- La verificación es
--    λ> verifica
--    20 examples, 0 failures

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

-- La 1ª propiedad es
prop_triangularesConCifras1 :: Bool
prop_triangularesConCifras1 =
  [take 2 (triangularesConCifras1 n) | n <- [1..7]] ==
  [take 2 (triangularesConCifras2 n) | n <- [1..7]]

-- La comprobación es
--    λ> prop_triangularesConCifras1
--    True

-- La 2ª propiedad es
prop_triangularesConCifras2 :: Int -> Bool
prop_triangularesConCifras2 n =
  all (== take 5 (triangularesConCifras2 n'))
      [take 5 (triangularesConCifras3 n'),
       take 5 (triangularesConCifras4 n'),
       take 5 (triangularesConCifras5 n')]
  where n' = 1 + n `mod` 9

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

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

-- La comparación es
--    λ> (triangularesConCifras1 3) !! 220
--    5456556
--    (2.48 secs, 1,228,690,120 bytes)
--    λ> (triangularesConCifras2 3) !! 220
--    5456556
--    (0.01 secs, 4,667,288 bytes)
--
--    λ> (triangularesConCifras2 3) !! 600
--    500010500055
--    (1.76 secs, 1,659,299,872 bytes)
--    λ> (triangularesConCifras3 3) !! 600
--    500010500055
--    (1.67 secs, 1,603,298,648 bytes)
--    λ> (triangularesConCifras4 3) !! 600
--    500010500055
--    (1.20 secs, 1,507,298,248 bytes)
--    λ> (triangularesConCifras5 3) !! 600
--    500010500055
--    (1.15 secs, 1,507,298,256 bytes)