Suma de cuadrados menos cuadrado de la suma

Definir la función

   euler6 :: Integer -> Integer

1	euler6 :: Integer -> Integer

tal que euler6 n es la diferencia entre el cuadrado de la suma de los n primeros números y la suma de los cuadrados de los nprimeros números. Por ejemplo,

   euler6 10       ==  2640
   euler6 (10^10)  ==  2500000000166666666641666666665000000000

1 2	euler6 10 == 2640 euler6 (10^10) == 2500000000166666666641666666665000000000

Nota: Este ejercicio está basado en el problema 6 del proyecto Euler.

Soluciones

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

Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck

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

euler6a :: Integer -> Integer
euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,
--    suma 3  ==  6
suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los
-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
--    sumaDeCuadrados 3    ==  14
--    sumaDeCuadrados 100  ==  338350

sumaDeCuadrados1 :: Integer -> Integer
sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

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

euler6b :: Integer -> Integer
euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

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

euler6c :: Integer -> Integer
euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

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

sumaDeCuadrados3 :: Integer -> Integer
sumaDeCuadrados3 1 = 1
sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

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

euler6d :: Integer -> Integer
euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer
suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer
sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

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

euler6e :: Integer -> Integer
euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer
suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer
sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

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

-- La propiedad es
prop_euler6 :: Positive Integer -> Bool
prop_euler6 (Positive n) =
  all (== euler6a n)
      [euler6b n,
       euler6c n,
       euler6d n,
       euler6e n]

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

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

-- La comparación es
--    λ> euler6a (3*10^6)
--    20250004499997749999500000
--    (3.32 secs, 2,577,174,640 bytes)
--    λ> euler6b (3*10^6)
--    20250004499997749999500000
--    (0.01 secs, 569,288 bytes)
--    λ> euler6c (3*10^6)
--    20250004499997749999500000
--    (5.60 secs, 2,849,479,288 bytes)
--    λ> euler6d (3*10^6)
--    20250004499997749999500000
--    (2.52 secs, 2,457,175,248 bytes)
--    λ> euler6e (3*10^6)
--    20250004499997749999500000
--    (1.08 secs, 2,016,569,472 bytes)
--
--    λ> euler6a (10^7)
--    2500000166666641666665000000
--    (11.14 secs, 8,917,796,648 bytes)
--    λ> euler6b (10^7)
--    2500000166666641666665000000
--    (0.01 secs, 570,752 bytes)
--    λ> euler6c (10^7)
--    *** Exception: stack overflow
--    λ> euler6d (10^7)
--    2500000166666641666665000000
--    (9.47 secs, 8,517,796,760 bytes)
--    λ> euler6e (10^7)
--    2500000166666641666665000000
--    (3.78 secs, 7,049,100,104 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

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

euler6a :: Integer -> Integer

euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,

-- suma 3 == 6

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los

-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

-- sumaDeCuadrados 3 == 14

-- sumaDeCuadrados 100 == 338350

sumaDeCuadrados1 :: Integer -> Integer

sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución

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

euler6b :: Integer -> Integer

euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer

sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución

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

euler6c :: Integer -> Integer

euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

suma3 :: Integer -> Integer

suma3 1 = 1

suma3 n = n + suma3 (n-1)

sumaDeCuadrados3 :: Integer -> Integer

sumaDeCuadrados3 1 = 1

sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución

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

euler6d :: Integer -> Integer

euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer

suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer

sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución

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

euler6e :: Integer -> Integer

euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer

suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer

sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia

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

-- La propiedad es

prop_euler6 :: Positive Integer -> Bool

prop_euler6 (Positive n) =

all (== euler6a n)

[euler6b n,

euler6c n,

euler6d n,

euler6e n]

-- La comprobación es

-- λ> quickCheck prop_euler6

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

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

-- 20250004499997749999500000

-- (3.32 secs, 2,577,174,640 bytes)

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

-- 20250004499997749999500000

-- (0.01 secs, 569,288 bytes)

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

-- 20250004499997749999500000

-- (5.60 secs, 2,849,479,288 bytes)

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

-- 20250004499997749999500000

-- (2.52 secs, 2,457,175,248 bytes)

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

-- 20250004499997749999500000

-- (1.08 secs, 2,016,569,472 bytes)

-- λ> euler6a (10^7)

-- 2500000166666641666665000000

-- (11.14 secs, 8,917,796,648 bytes)

-- λ> euler6b (10^7)

-- 2500000166666641666665000000

-- (0.01 secs, 570,752 bytes)

-- λ> euler6c (10^7)

-- *** Exception: stack overflow

-- λ> euler6d (10^7)

-- 2500000166666641666665000000

-- (9.47 secs, 8,517,796,760 bytes)

-- λ> euler6e (10^7)

-- 2500000166666641666665000000

-- (3.78 secs, 7,049,100,104 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from operator import add
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**6)

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

def euler6a(n: int) -> int:
    return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,
#    suma(3)  ==  6
def suma1(n: int) -> int:
    return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los
# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
#    sumaDeCuadrados(3)    ==  14
#    sumaDeCuadrados(100)  ==  338350
def sumaDeCuadrados1(n: int) -> int:
    return sum(x**2 for x in range(1, n + 1))

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

def euler6b(n: int) -> int:
    return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:
    return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:
    return n * (n + 1) * (2 * n + 1) // 6

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

def euler6c(n: int) -> int:
    return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:
    if n == 1:
        return 1
    return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:
    if n == 1:
        return 1
    return n**2 + sumaDeCuadrados3(n - 1)

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

def euler6d(n: int) -> int:
    return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:
    return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:
    return reduce(add, (x**2 for x in range(1, n + 1)))

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

def euler6e(n: int) -> int:
    return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x
        x = x + 1
    return r

def sumaDeCuadrados5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x**2
        x = x + 1
    return r

# 6ª solución
# ===========

def euler6f(n: int) -> int:
    return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x
    return r

def sumaDeCuadrados6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x**2
    return r

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

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_euler6(n):
    r = euler6a(n)
    assert euler6b(n) == r
    assert euler6c(n) == r
    assert euler6d(n) == r
    assert euler6e(n) == r
    assert euler6f(n) == r

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

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

def tiempo(e):
    """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('euler6a(20000)')
#    0.02 segundos
#    >>> tiempo('euler6b(20000)')
#    0.00 segundos
#    >>> tiempo('euler6c(20000)')
#    0.02 segundos
#    >>> tiempo('euler6d(20000)')
#    0.01 segundos
#    >>> tiempo('euler6e(20000)')
#    0.01 segundos
#    >>> tiempo('euler6f(20000)')
#    0.01 segundos
#
#    >>> tiempo('euler6a(10**7)')
#    2.26 segundos
#    >>> tiempo('euler6b(10**7)')
#    0.00 segundos
#    >>> tiempo('euler6d(10**7)')
#    2.58 segundos
#    >>> tiempo('euler6e(10**7)')
#    2.89 segundos
#    >>> tiempo('euler6f(10**7)')
#    2.45 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

from functools import reduce

from operator import add

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def euler6a(n: int) -> int:

return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,

# suma(3) == 6

def suma1(n: int) -> int:

return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los

# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

# sumaDeCuadrados(3) == 14

# sumaDeCuadrados(100) == 338350

def sumaDeCuadrados1(n: int) -> int:

return sum(x**2 for x in range(1, n + 1))

# 2ª solución

# ===========

def euler6b(n: int) -> int:

return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:

return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:

return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución

# ===========

def euler6c(n: int) -> int:

return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:

if n == 1:

return 1

return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:

if n == 1:

return 1

return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución

# ===========

def euler6d(n: int) -> int:

return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:

return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:

return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución

# ===========

def euler6e(n: int) -> int:

return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x

x = x + 1

return r

def sumaDeCuadrados5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x**2

x = x + 1

return r

# 6ª solución

# ===========

def euler6f(n: int) -> int:

return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x

return r

def sumaDeCuadrados6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x**2

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_euler6(n):

r = euler6a(n)

assert euler6b(n) == r

assert euler6c(n) == r

assert euler6d(n) == r

assert euler6e(n) == r

assert euler6f(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_cuadrados_menos_cuadrado_de_la_suma.py

# 1 passed in 0.21s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('euler6a(20000)')

# 0.02 segundos

# >>> tiempo('euler6b(20000)')

# 0.00 segundos

# >>> tiempo('euler6c(20000)')

# 0.02 segundos

# >>> tiempo('euler6d(20000)')

# 0.01 segundos

# >>> tiempo('euler6e(20000)')

# 0.01 segundos

# >>> tiempo('euler6f(20000)')

# 0.01 segundos

# >>> tiempo('euler6a(10**7)')

# 2.26 segundos

# >>> tiempo('euler6b(10**7)')

# 0.00 segundos

# >>> tiempo('euler6d(10**7)')

# 2.58 segundos

# >>> tiempo('euler6e(10**7)')

# 2.89 segundos

# >>> tiempo('euler6f(10**7)')

# 2.45 segundos

El código se encuentra en GitHub.

Suma de cuadrados menos cuadrado de la suma

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico