Menu Close

Sistema factorádico de numeración

El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número “341010” en el sistema factorádico es 463 en el sistema decimal ya que

   3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463

En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.

Con los dígitos del 0 al 9 el mayor número que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.

Definir las funciones

   factoradicoAdecimal :: String -> Integer
   decimalAfactoradico :: Integer -> String

tales que

  • (factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,
     λ> decimalAfactoradico 463
     "341010"
     λ> decimalAfactoradico 2022
     "2441000"
     λ> decimalAfactoradico 36288000
     "A0000000000"
     λ> map decimalAfactoradico [1..10]
     ["10","100","110","200","210","1000","1010","1100","1110","1200"]
     λ> decimalAfactoradico 37199332678990121746799944815083519999999
     "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"
  • (decimalAfactoradico n) es el número factorádico correpondiente al número decimal n. Por ejemplo,
     λ> factoradicoAdecimal "341010"
     463
     λ> factoradicoAdecimal "2441000"
     2022
     λ> factoradicoAdecimal "A0000000000"
     36288000
     λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"]
     [1,2,3,4,5,6,7,8,9,10]
     λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"
     37199332678990121746799944815083519999999

Comprobar con QuickCheck que, para cualquier entero positivo n,

   factoradicoAdecimal (decimalAfactoradico n) == n

Soluciones

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

Suma de cadenas

Definir la función

   sumaCadenas :: String -> String -> String

tal que (sumaCadenas xs ys) es la cadena formada por el número entero que es la suma de los números enteros cuyas cadenas que lo representan son xs e ys; además, se supone que la cadena vacía representa al cero. Por ejemplo,

   sumaCadenas "2"   "6"  == "8"
   sumaCadenas "14"  "2"  == "16"
   sumaCadenas "14"  "-5" == "9"
   sumaCadenas "-14" "-5" == "-19"
   sumaCadenas "5"   "-5" == "0"
   sumaCadenas ""    "5"  == "5"
   sumaCadenas "6"   ""   == "6"
   sumaCadenas ""    ""   == "0"

Soluciones

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

Cuadrado más cercano

Definir la función

   cuadradoCercano :: Integer -> Integer

tal que (cuadradoCercano n) es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,

   cuadradoCercano 2       == 1
   cuadradoCercano 6       == 4
   cuadradoCercano 8       == 9
   cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000

Soluciones

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

9º curso de Exercitium (2021-22)

Hoy (26 de enero de 2022) comienza el noveno curso de Exercitium con los mismos objetivos

También el procedimiento es el mismo que en los cursos anteriores:

  • diariamente se propone un nuevo ejercicio,
  • en los comentarios se pueden escribir distintas soluciones
  • a los siete días de la propuesta, se publican las soluciones seleccionadas.

Tanto la publicación del enunciado como la solución se anuncian en Twitter.

En cada curso, los contenidos de los ejercicios avanzan conforme se iban introduciendo en el curso.

En la siguiente tabla se resume los cursos anteriores, donde

  • en la 1ª columna hay un enlace al diario de clase del curso de (las entradas están en orden cronológico inverso),
  • en la 2ª un enlace al primer ejercicio del curso,
  • en la 3ª un enlace al último ejercicio del curso y
  • en la 4ª el número de ejercicios propuesto en el curso.

La tabla es

Curso Desde Hasta Ejercicios
2013-14 21-abril-2014 25-julio-2014 70
2014-15 30-octubre-2014 26-junio-2015 171
2015-16 21-octubre-2015 02-junio-2016 176
2016-17 03-noviembre-2016 09-junio-2017 149
2017-18 03-noviembre-2017 12-junio-2018 151
2018-19 09-noviembre-2018 10-junio-2019 143
2019-20 11-noviembre-2019 05-junio-2020 176
2020-21 12-enero-2021 24-junio-2021 110

En la tabla anterior el último enlace a los diarios de los cursos es el de 2019-10 ya que es el último curso que impartí antes de jubilarme. Por ello, aunque mantenga la misma dinámica, el número de soluciones de los alumnos de la asignatura sea menor.

Sucesiones conteniendo al producto de consecutivos

El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1984 es

Sea c un entero positivo. La sucesión f(n) está definida por

f(1) = 1, f(2) = c, f(n+1) = 2f(n) – f(n-1) + 2 (n ≥ 2).

Demostrar que para cada k ∈ N exist un r ∈ N tal que f(k)f(k+1) = f(r).

Definir la función

   sucesion :: Integer -> [Integer]

tal que los elementos de (sucesion c) son los términos de la suceción f(n) definida en el enunciado del problema. Por ejemplo,

   take 7 (sucesion 2)   ==  [1,2,5,10,17,26,37]
   take 7 (sucesion 3)   ==  [1,3,7,13,21,31,43]
   take 7 (sucesion 4)   ==  [1,4,9,16,25,36,49]
   sucesion 2 !! 30      ==  901
   sucesion 3 !! 30      ==  931
   sucesion 4 !! 30      ==  961
   sucesion 2 !! (10^2)  ==  10001
   sucesion 2 !! (10^3)  ==  1000001
   sucesion 2 !! (10^4)  ==  100000001
   sucesion 2 !! (10^5)  ==  10000000001
   sucesion 2 !! (10^6)  ==  1000000000001
   sucesion 2 !! (10^7)  ==  100000000000001
   sucesion 3 !! (10^7)  ==  100000010000001
   sucesion 4 !! (10^7)  ==  100000020000001
   sucesion 2 !! (10^8)  ==  10000000000000001
   sucesion 3 !! (10^8)  ==  10000000100000001
   sucesion 4 !! (10^8)  ==  10000000200000001
   sucesion 2 !! (10^9)  ==  1000000000000000001

Comprobar con QuickCheck que para cada k ∈ N existe un r ∈ N tal que f(k)f(k+1) = f(r).

Soluciones

import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
sucesion :: Integer -> [Integer]
sucesion c =
  map (termino c) [1..]
 
termino :: Integer -> Integer -> Integer
termino c 1 = 1
termino c 2 = c
termino c n = 2 * termino c (n-1) - termino c (n-2) + 2
 
-- 2ª solución
-- ===========
 
sucesion2 :: Integer -> [Integer]
sucesion2 c =
  1 : c : [2*y-x+2 | (x,y) <- zip (sucesion3 c) (tail (sucesion3 c))]
 
-- 2ª solución
-- ===========
 
sucesion3 :: Integer -> [Integer]
sucesion3 c =
  map (termino3 c) [1..]
 
termino3 :: Integer -> Integer -> Integer
termino3 c 1 = 1
termino3 c 2 = c
termino3 c n = n^2 + b*n - b
  where b = c - 4
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sucesion 2 !! 32
--    1025
--    (3.95 secs, 1,991,299,256 bytes)
--    λ> sucesion2 2 !! 32
--    1025
--    (0.01 secs, 119,856 bytes)
--    λ> sucesion3 2 !! 32
--    1025
--    (0.01 secs, 111,176 bytes)
--
--    λ> sucesion2 2 !! (10^7)
--    100000000000001
--    (2.26 secs, 5,200,111,128 bytes)
--    λ> sucesion3 2 !! (10^7)
--    100000000000001
--    (0.27 secs, 1,600,111,568 bytes)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_equivalencia :: Integer -> Int -> Property
prop_equivalencia c k =
  c > 0 && k >= 0 ==>
  take 20 (sucesion c) == take 20 (sucesion2 c) &&
  sucesion2 c !! k == sucesion3 c !! k
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_sucesion :: Integer -> Int -> Property
prop_sucesion c k =
  c > 0 && k >= 0 ==>
  (ys !! k) `elem` xs
  where xs = sucesion2 c
        ys = zipWith (*) xs (tail xs)
 
-- La comprobación es
--    λ> quickCheck prop_sucesion
--    +++ OK, passed 100 tests.

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="haskell"> y otra con </pre>