Menu Close

Día: 3 febrero, 2021

Los números armónicos no son enteros

Los números armónicos son las sumas de los inversos de de los primeros números enteros positivos; es decir, el n-ésimo número armónico es

   H(n) = 1 + 1/2 + 1/3 + ··· + 1/n

Los primeros números armónicos son

   1, 3/2, 11/6, 25/12, 137/60, ..

Definir, usando la librería de los números racionales (Data.Ratio), las funciones

   armonico  :: Integer -> Rational
   armonicos :: [Rational]
   esEntero  :: Rational -> Bool

tales que

  • (armonico n) es el n-ésimo número armónico. Por ejemplo,
     armonico 2  ==    3 % 2
     armonico 3  ==   11 % 6
     armonico 4  ==   25 % 12
     armonico 5  ==  137 % 60
  • armonicos es la lista de los números armónicos. Por ejemplo,
     take 5 armonicos  ==  [1 % 1,3 % 2,11 % 6,25 % 12,137 % 60]
  • (esEntero x) se verifica si x es un número entero. Por ejemplo,
     esEntero (1 % 7)           ==  False
     esEntero (1 % 7 + 20 % 7)  ==  True

Comprobar con QuickCheck que

  • nigún número armónico, excepto el primero, es un número entero y

  • la diferencia de dos números armónicos distintos nunca es un número entero.

Nota: Este ejercicio está basado en el artículo Sums of consecutive reciprocals publicado por John D. Cook en su blog el 23 de enero de 2021.

Soluciones

import Data.List (genericIndex)
import Data.Ratio ((%), denominator)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
armonico  :: Integer -> Rational
armonico 1 = 1
armonico n = 1 % n + armonico (n-1)
 
armonicos :: [Rational]
armonicos = map armonico [1..]
 
esEntero  :: Rational -> Bool
esEntero x = denominator x == 1
 
-- 2ª solución
-- ===========
 
armonicos2 :: [Rational]
armonicos2 = scanl1 (\ x y -> x + y) [1 % n | n <- [1..]]
 
armonico2  :: Integer -> Rational
armonico2 n = armonicos `genericIndex` n
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> fromRational (armonicos !! (10^4))
--    9.787706026045383
--    (9.17 secs, 29,293,137,856 bytes)
--    λ> fromRational (armonicos2 !! (10^4))
--    9.787706026045383
--    (9.42 secs, 29,292,225,904 bytes)
 
-- Propiedades
-- ===========
 
-- La 1ª propiedad es
prop_armonicos :: Integer -> Property
prop_armonicos n =
  n > 1 ==>
  not (esEntero (armonico n))
 
-- La comprobación de la 1ª propiedad es
--    λ> quickCheck prop_armonicos
--    +++ OK, passed 100 tests.
 
-- La 2ª propiedad es
prop_armonicos2 :: Integer -> Integer -> Property
prop_armonicos2 n m =
  n > 0 && m > 0 && n /= m ==>
  not (esEntero (armonico n - armonico m))
 
-- La comprobación de la segunda propiedad es
--   λ> quickCheck prop_armonicos2
--   +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>