Misceláneas

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1993 es

> Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111......1 (escrito sólo con unos).

Definir la función

   multiplosRepitunos :: Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111...1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

   take 2 (multiplosRepitunos 7) == [111111,111111111111]
   head (multiplosRepitunos 19)  == 111111111111111111
   length (show (head (multiplosRepitunos (primes !! (10^5))))) == 43324

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

Ecuación diofántica con primos (OME1995 P4)

José A. Alonso

04-05-2021

Misceláneas

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1995 es

Siendo p un número primo, halla las soluciones enteras de la ecuación:

p.(x + y) = x.y

Definir la función

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

tal que (soluciones p) es la lista de los pares de enteros (x,y) tales que p.(x + y) = x.y. Por ejemplo,

   λ> take 3 (soluciones 7)
   [(0,0),(14,14),(-42,6)]
   λ> sum [x+y | (x,y) <- take 6 (soluciones (primes !! (10^6)))]
   185830404

Ordenación de los pares de enteros

José A. Alonso

03-05-2021

Misceláneas

Los pares de números enteros se pueden ordenar por la suma de los valores absolutos de sus componentes. Los primeros pares en dicha ordenación son

   (0,0),
   (-1,0),(0,-1),(0,1),(1,0),
   (-2,0),(-1,-1),(-1,1),(0,-2),(0,2),(1,-1),(1,1),(2,0), ...

Definir la lista

   pares :: [(Integer, Integer)]

cuyos elementos son los pares de números enteros con la ordenación anterior. Por ejemplo,

   λ> take 38 pares
   [(0,0),(-1,0),(0,-1),(0,1),(1,0),(-2,0),(-1,-1),(-1,1),(0,-2),
    (0,2),(1,-1),(1,1),(2,0),(-3,0),(-2,-1),(-2,1),(-1,-2),(-1,2),
    (0,-3),(0,3),(1,-2),(1,2),(2,-1),(2,1),(3,0),(-4,0),(-3,-1),
    (-3,1),(-2,-2),(-2,2),(-1,-3),(-1,3),(0,-4),(0,4),(1,-3),(1,3),
    (2,-2),(2,2)]

Números potencias perfectas de la suma de sus dígitos

José A. Alonso

30-04-2021

Misceláneas

El número 2401 es una potencia de la suma de sus dígitos, ya que dicha suma es 7 y 7^4 = 2401.

Definir la lista

   potenciaSumaDigitos :: [Integer]

cuyos elementos son los números que son potencias de las sumas de sus dígitos. Por ejemplo,

   λ> take 17 potenciaSumaDigitos
   [0,1,2,3,4,5,6,7,8,9,81,512,2401,4913,5832,17576,19683]

Órbita con raíz entera

José A. Alonso

29-04-2021

Misceláneas

El enunciado del problema 2 de la OME (Olimpiada Matemática Española) del 1998 es

Sea p un número primo. Determinar todos los enteros k tales que sqrt(k² - k*p) es natural.

Definir las funciones

   orbita        :: Integer -> [Integer]
   orbitaDePrimo :: Integer -> [Integer]

tales que

(orbita n) es la lista de todos los enteros k tales que sqrt(k² - k*n) es natural. Por ejemplo,

     take 4  (orbita 6)   == [0,-2,6,8]
     take 5  (orbita 36)  == [0,-12,36,48,-64]
     take 6  (orbita 9)   == [0,-3,9,12,-16,25]
     take 8  (orbita 27)  == [0,-9,27,36,-48,75,-169,196]
     take 10 (orbita 111) == [0,-37,111,148,-289,400,-972,1083,-3025,3136]

(orbitaDePrimo p) es la lista de todos los enteros k tales que sqrt(k² - k*p) es natural, suponiendo que p es un número primo. Por ejemplo,

     orbitaDePrimo 5                  == [0,-4,5,9]
     orbitaDePrimo (primes !! (10^6)) == [0,15485867,-59953011442489,59953026928356]

Números iguales a potencias de las sumas de sus cifras

José A. Alonso

28-04-2021

Misceláneas

El enunciado del problema 2 de la OME (Olimpiada Matemática Española) del 1998 es

Hallar todos los números naturales de 4 cifras, escritos en base 10, que sean iguales al cubo de la suma de sus cifras.

Definir la función

   especiales :: Integer -> Integer -> [Integer]

tal que (especiales a b) es la lista de los números de a cifras que son iguales la suma de sus cifras elevada a b. Por ejemplo,

   especiales 5 3  ==  [17576,19683]
   especiales 6 4  ==  [234256,390625,614656]

Usando la función anterior, calcular las soluciones del problema de la Olimpiada.

Máximos de una función recursiva

José A. Alonso

27-04-2021

Misceláneas

El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2002 es

La función g se define sobre los números naturales y satisface las condiciones:

g(1) = 1

g(2n) = g(n)

g(2n + 1) = g(2n) + 1

Sea n un número natural tal que 1 ≤ n ≤ 2002. Calcula el valor máximo M de g(n). Calcula también cuántos valores de n satisfacen g(n) = M.

Los valores de la función g para n de 1 a 30 son

   1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4

Definir la función

   maximoG :: Integer -> Integer

tal que (maximoG m) es el máximo de los valores de g(n) para n en {1, 2,..., m}. Por ejemplo,

   maximoG 30           ==  4
   maximoG (10^(10^5))  ==  332192

Usando la función maximoG, calcular los valores pedidos en el problema.

Productos de cuatro consecutivos

José A. Alonso

26-04-2021

Misceláneas

El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2006 es

Probar que el producto de cuatro naturales consecutivos no puede ser ni cuadrado ni cubo perfecto.

Definir la lista

   productos :: [Integer]

cuyos elementos son los productos de cuatro enteros positivos consecutivos. Por ejemplo,

   λ> take 12 productos
   [24,120,360,840,1680,3024,5040,7920,11880,17160,24024,32760]

Comprobar con QuickCheck que los elementos de la lista anterior no son ni cuadrados ni cubos perfectos.

Mayores potencias de 5 que dividen a la sucesión

José A. Alonso

23-04-2021

Misceláneas

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 2014 es

Sea {x(n)} la sucesión de enteros positivos definida por x(1) = 2 y x(n+1) = 2*x(n)^3+x(n) para todo n >= 1. Determinar la mayor potencia de 5 que divide al número x(2014)^2+1.

Definir la función

   mayorExponente :: Integer -> Integer

tal que (mayorExponente n) es el mayor m tal que 5^m divide al número x(n)^2+1.

Permutaciones divisibles

José A. Alonso

22-04-2021

Misceláneas

El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2016 es

De entre todas las permutaciones (a(1), a(2),..., a(n)) del conjunto {1, 2,..., n},(n ≥ 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +···+ a(m)) es divisible por m, para cada m = 1, 2,..., n. Calcular el número total de estas permutaciones.

Llamaremos permutaciones divisibles a las que cumplen la propiedad anterior. Por ejemplo, [2,3,4,1] es una permutación divisible de {1,2,3,4} ya que es una permutación del conjunto y se cumplen las condiciones:

2*2 = 4 es divisible por 1,
2*(2+3) = 10 es divisible por 2
2*(2+3+4) = 18 es divisible por 3.
2*(2+3+4+1) = 20 es divisible por 4.

Definir las siguientes funciones:

   permutacionesDivisibles  :: Integer -> [[Integer]]
   nPermutacionesDivisibles :: Integer -> Integer

tales que

(permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,...,n}. Por ejemplo,

     λ> permutacionesDivisibles 2
     [[1,2],[2,1]]
     λ> permutacionesDivisibles 3
     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     λ> permutacionesDivisibles 4
     [[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1],
      [3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]]
     λ> length (permutacionesDivisibles 20)
     786432
 ~~~
+ (nPermutacionesDivisibles n) es el número de permutaciones divisibles de {1,2,...,n}. Por ejemplo,

 nPermutacionesDivisibles 4  ==  12
 nPermutacionesDivisibles (10^8) `mod` (10^9)  ==  340332032

------------------------------------------------------------------------
<!-- TEASER_END -->
## Soluciones

~~~haskell
import Data.List (genericLength, permutations, sort)

-- 1ª definición de permutacionesDivisibles
-- ========================================

permutacionesDivisibles :: Integer -> [[Integer]]
permutacionesDivisibles n =
  sort (filter aux (permutations [1..n]))
  where
    aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]]

-- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo,
--    sumasParciales [1..9]  ==  [1,3,6,10,15,21,28,36,45]
sumasParciales :: [Integer] -> [Integer]
sumasParciales = scanl1 (+)

-- 2ª definición de permutacionesDivisibles
-- ========================================

permutacionesDivisibles2 :: Integer -> [[Integer]]
permutacionesDivisibles2 = sort . aux
  where aux n
          | n < 4     = permutations [1..n]
          | otherwise = [xs ++ [n] | xs <- xss] ++
                        [map (+1) xs ++ [1] | xs <- xss]
          where xss = aux (n-1)

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

-- La comprobación para los n primeros valores es
--    λ> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]]
--    True

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

-- La comparación es
--    λ> length (permutacionesDivisibles 10)
--    768
--    (8.42 secs, 10,420,281,776 bytes)
--    λ> length (permutacionesDivisibles2 10)
--    768
--    (0.02 secs, 2,250,152 bytes)
--
--    λ> length (permutacionesDivisibles2 20)
--    786432
--    (14.33 secs, 4,458,839,736 bytes)

-- 1ª definición de nPermutacionesDivisibles
-- =========================================

--    nPermutacionesDivisibles 5  ==  24
nPermutacionesDivisibles :: Integer -> Integer
nPermutacionesDivisibles =
  genericLength . permutacionesDivisibles

-- 2ª definición de nPermutacionesDivisibles
-- =========================================

nPermutacionesDivisibles2 :: Integer -> Integer
nPermutacionesDivisibles2 =
  genericLength . permutacionesDivisibles2

-- 3ª definición de nPermutacionesDivisibles
-- =========================================

-- Observando los siguientes cálculos:
--    λ> [nPermutacionesDivisibles2 n | n <- [1..12]]
--    [1,2,6,12,24,48,96,192,384,768,1536,3072]
--    λ> 1 : 2 : [3*2^(n-2) | n <- [3..12]]
--    [1,2,6,12,24,48,96,192,384,768,1536,3072]

nPermutacionesDivisibles3 :: Integer -> Integer
nPermutacionesDivisibles3 n
  | n < 3     = n
  | otherwise = 3*2^(n-2)

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

-- La comparación es
--    λ> nPermutacionesDivisibles 10
--    768
--    (7.95 secs, 10,704,422,592 bytes)
--    λ> nPermutacionesDivisibles2 10
--    768
--    (0.01 secs, 2,269,872 bytes)
--    λ> nPermutacionesDivisibles3 10
--    768
--    (0.01 secs, 102,560 bytes)
--
--    λ> nPermutacionesDivisibles2 20
--    786432
--    (13.00 secs, 4,477,717,968 bytes)
--    λ> nPermutacionesDivisibles3 20
--    786432
--    (0.01 secs, 106,848 bytes)

Números fibonaccianos

José A. Alonso

21-04-2021

Misceláneas

El enunciado del segundo problema de este mes de la RSME es el siguiente:

Un número de al menos tres cifras se denomina fibonacciano si sus cifras, a partir de la tercera, son iguales a la suma de las dos cifras anteriores. Por ejemplo, 5279 es un número fibonacciano, pues su tercera cifra, 7, es suma de las dos anteriores (5+2) y su cuarta cifra, 9, también (2+7).

Te daremos el problema por válido si respondes bien a estas dos cuestiones: a) ¿cuántas cifras como máximo puede tener un número fibonacciano? b) ¿cuántos números fibonaccianos hay?

En la definición de fibonacciano la suma de las cifras tiene que menor que 10, pero podemos generalizarlo sustituyendo 10 por número n. Dichos números de llaman fibonaccianos generalizados acotados por n. Por ejemplo, 571219315081 es un fibonacciano generalizado acotado por 100 ya que la sucesión de sus dígitos es 5, 7, 12 (= 5+7), 19 (= 7+12), 31 (= 12+19) 50 (=19+31) y 81 (=31+50).

Definir las funciones

   esFibonacciano :: Integer -> Bool
   fibonaccianos  :: [Integer]
   fibonaccianosG :: Integer -> [Integer]

tales que

(esFibonacciano n) se verifica si n es un número fibonacciano. Por ejemplo,

     esFibonacciano 5279    ==  True
     esFibonacciano 527916  ==  False

fibonaccianos es la lista de los números fibonaccianos. Por ejemplo,

     λ> take 60 fibonaccianos
     [101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268,
      279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516,
      527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123,
      1235,1347,1459,2022,2134,2246,2358,3033,3145,3257,3369,4044,4156]

(fibonaccianosG n) es la lista de los números fibonaccianos generalizados acotados por n. Por ejemplo,

     λ> take 60 (fibonaccianosG 100)
     [101,112,123,134,145,156,167,178,189,202,213,224,235,246,257,268,
      279,303,314,325,336,347,358,369,404,415,426,437,448,459,505,516,
      527,538,549,606,617,628,639,707,718,729,808,819,909,1011,1123,
      1235,1347,1459,1910,2022,2134,2246,2358,2810,2911,3033,3145,3257]
     λ> take 12 (drop 60 (fibonaccianosG 10))
     [4268,5055,5167,5279,6066,6178,7077,7189,8088,9099,10112,11235]
     λ> take 12 (drop 60 (fibonaccianosG 100))
     [3369,3710,3811,3912,4044,4156,4268,4610,4711,4812,4913,5055]
     λ> length (fibonaccianosG (10^40))
     16888
     λ> length (show (last (fibonaccianosG (10^40))))
     3943

Usando las funciones anteriores, calcular cuántas cifras como máximo puede tener un número fibonacciano y cuántos números fibonaccianos hay.

Cuadriseguidos y números encadenados

José A. Alonso

20-04-2021

Misceláneas

El enunciado del primer problema de este mes de la RSME es el siguiente:

Un entero positivo de dos o más cifras se denomina cuadriseguido si cada par de dígitos consecutivos que tenga es un cuadrado perfecto. Por ejemplo, + 364 es cuadriseguido, pues 36 = 6^2 y 64 = 8^2 + 3642 no lo es porque 42 no es un cuadrado perfecto. Obtén todos los números cuadriseguidos posibles.

El concepto de cuadriseguido se puede generalizar como sigue: Un entero positivo n de dos o más cifras se denomina encadenado respecto de una lista de números de dos dígitos xs si cada par de dígitos consecutivos que tenga es un elemento distinto de xs. Por ejemplo,

364 es encadenado respecto de xs = [36,64,15], porque 36 y 64 pertenecen a xs
3642 no es encadenado respecto de xs = [36,64,15], porque 42 no pertenece a xs

Definir la función

   encadenados :: [Integer] -> [Integer]

tal que (encadenados xs) es la lista de los números encadenados respecto de xs. Por ejemplo,

   λ> encadenados [12,23,31]
   [12,23,31,123,231,312,1231,2312,3123]
   λ> encadenados [12,22,31]
   [12,22,31,122,312,3122]
   λ> take 14 (encadenados [n^2 | n <- [4..9]])
   [16,25,36,49,64,81,164,364,649,816,1649,3649,8164,81649]
   λ> length (encadenados [10..42])
   911208

Calcular todos los números cuadriseguidos posibles usando la función encadenados.

Árbol de cadenas

José A. Alonso

19-04-2021

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Una cadena con un conjunto de pares ps es una lista xs de elementos distintos de ps tales que la segunda componente de cada elemento de xs es igual a la primera componente de su siguiente elemento. Por ejemplo, si ps = [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)] entonces [(6,4)], [(8,1),(1,6)] y [(8,1),(1,6),(6,4),(4,9)] son cadenas con ps.

Definir la función

arbolCadenas :: Eq a => [(a,a)] -> Tree [(a,a)]

tal que (arbolCadenas ps) es el árbol de las cadenas formadas con los elementos de ps. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,2),(2,3),(3,1)])))
[]
|
+- [(1,2)]
|  |
|  `- [(3,1),(1,2)]
|     |
|     `- [(2,3),(3,1),(1,2)]
|
+- [(2,3)]
|  |
|  `- [(1,2),(2,3)]
|     |
|     `- [(3,1),(1,2),(2,3)]
|
`- [(3,1)]
   |
   `- [(2,3),(3,1)]
      |
      `- [(1,2),(2,3),(3,1)]

λ> putStrLn (drawTree (fmap show (arbolCadenas [(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)])))
[]
|
+- [(1,6)]
|  |
|  `- [(8,1),(1,6)]
|
+- [(2,5)]
|
+- [(3,6)]
|
+- [(4,9)]
|  |
|  `- [(6,4),(4,9)]
|     |
|     +- [(1,6),(6,4),(4,9)]
|     |  |
|     |  `- [(8,1),(1,6),(6,4),(4,9)]
|     |
|     `- [(3,6),(6,4),(4,9)]
|
+- [(6,4)]
|  |
|  +- [(1,6),(6,4)]
|  |  |
|  |  `- [(8,1),(1,6),(6,4)]
|  |
|  `- [(3,6),(6,4)]
|
`- [(8,1)]

Sucesión de cubos perfectos

José A. Alonso

16-04-2021

Misceláneas

Definir la lista

   sucesion :: [Integer]

cuyos elementos son los términos de la sucesión

   107811/3, 110778111/3, 111077781111/3, 111107777811111/3, ...

Por ejemplo,

   λ> take 5 sucesion
   [35937,36926037,37025927037,37035925937037,37036925926037037]
   λ> length (show (sucesion2 !! (3*10^6)))
   9000005

Comprobar con QuickCheck que todos los términos de la sucesión son cubos perfectos.

Enlaces primos

José A. Alonso

15-04-2021

Misceláneas

Un enlace primo de longitud n es una permutación de 1, 2, ..., n comienza con 1 y termina con n, tal que la suma de cada par de términos adyacentes es primo. Por ejemplo, para n = 6 la lista [1,4,3,2,5,6] es un enlace primo ua que las sumas de los pares de términos adyacentes son los números primos 5, 7, 5, 7, 11.

Definir la función

   enlacesPrimos :: Int -> [[Int]]

tal que (enlacesPrimos n) es la lista de los enlaces primos de longitud n. Por ejemplo,

   λ> enlacesPrimos 6
   [[1,4,3,2,5,6]]
   λ> enlacesPrimos 7
   [[1,4,3,2,5,6,7],[1,6,5,2,3,4,7]]
   λ> enlacesPrimos 8
   [[1,2,5,6,7,4,3,8],[1,4,7,6,5,2,3,8],[1,2,3,4,7,6,5,8],[1,6,7,4,3,2,5,8]]
   λ> length (enlacesPrimos 10)
   24
   λ> length (head (enlacesPrimos (5*10^4)))
   50000

Raíces digitales de sucesiones de raíces digitales

José A. Alonso

14-04-2021

Misceláneas

La raíz digital de un número entero positivo n es el dígito que resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 2345 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La sucesión de las raices digitales definida por un número a es la sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y la raíz dígital de a(n). Por ejemplo, los primeros términos de la sucesión de las raíces digitales definida por 1 son

   1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89,...

Definir la función

   raicesDigitalesSucesionRaicesDigitales :: Integer -> [Integer]

tal que (raicesDigitalesSucesionRaicesDigitales a) es la lista de las raíces digitales de los elementos de la sucesión de raíces digitales definidas por a. Por ejemplo,

   λ> take 20 (raicesDigitalesSucesionRaicesDigitales 1)
   [1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2]
   λ> take 20 (raicesDigitalesSucesionRaicesDigitales 2021)
   [5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1]
   λ> raicesDigitalesSucesionRaicesDigitales (9^100) !! (10^9)
   9

Sucesiones de raices digitales

José A. Alonso

13-04-2021

Misceláneas

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La sucesión de las raices digitales definida por un número a es la sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y la raíz dígital de a(n). Por ejemplo, los primeros términos de la sucesión de las raíces digitales definida por 1 son

   1,2,4,8,16,23,28,29,31,35,43,50,55,56,58,62,70,77,82,83,85,89,...

Se observa que el menor número que no pertenece a la sucesión anterior es 3. Los primeros términos de la sucesión de las raíces digitales definida por 3 son

   3,6,12,15,21,24,30,33,39,42,48,51,57,60,66,69,75,78,84,87,93,96,...

Se observa que el menor número que no pertenece a las 2 sucesiones anteriores es 5. Los primeros términos de la sucesión de las raíces digitales definida por 5 son

   5,10,11,13,17,25,32,37,38,40,44,52,59,64,65,67,71,79,86,91,92,94,...

Definir la función

   sucesionSucesionesRaicesDigitales :: [[Integer]]

tal que sus elementos son las sucesiones de raíces digitales tal el primer elemento de cada sucesión es el menor elemento que no pertenece a las sucesiones anteriores. Por ejemplo,

   λ> map (take 5) (take 4 sucesionSucesionesRaicesDigitales)
   [[1,2,4,8,16],[3,6,12,15,21],[5,10,11,13,17],[7,14,19,20,22]]

Comprobar con QuickCheck que sucesionSucesionesRaicesDigitales tiene exactamente 5 elementos.

Raíces digitales de los números de Fibonacci

José A. Alonso

12-04-2021

Misceláneas

La sucesión Fibonacci es la siguiente sucesión infinita de números naturales:

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

La sucesión comienza con los números 1 y 1 y, a partir de estos, cada término es la suma de los dos anteriores.

Definir la función

   raizDigitalFibonacci :: Integer -> Integer

tal que (raizDigitalFibonacci n) es la raíz digital del n-ésimo número de Fibonacci. Por ejemplo,

   raizDigitalFibonacci 6         ==  4
   raizDigitalFibonacci 7         ==  3
   raizDigitalFibonacci (3*10^7)  ==  1

Raíces digitales de los números de Fermat

José A. Alonso

09-04-2021

Misceláneas

Los números de Fermat son los número de la forma F(n) = 2^(2^n) + 1, donde n esun número natural.

Definir la función

   raizDigitalFermat :: Integer -> Integer

tal que (raizDigitalFermat n) es la raíz digital del n-ésimo número de Fermat. Por ejemplo,

   raizDigitalFermat 3          ==  5
   raizDigitalFermat (10^2021)  ==  8

Persistencia aditiva

José A. Alonso

08-04-2021

Misceláneas

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La persistencia aditiva de un número entero positivo es el número de veces que hay sumar sus dígitos para llegar a su raíz digital. Por ejemplo, la persistencia aditiva de 2718 es 2: primero encontramos que 2+7+1+8 = 18, luego que 1+8 = 9.

Definir la función

   persistencia :: Integer -> Integer

tal que (persistencia n) es la persistencia del número entero positivo n. Por ejemplo,

   persistencia 2718                     ==  2
   persistencia 199                      ==  3
   persistencia 19999999999999999999999  ==  4

Raíces digitales de potencias de dos

José A. Alonso

07-04-2021

Misceláneas

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa por D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

Definir la función

   raizDigitalPotencia :: Integer -> Integer

tal que (raizDigitalPotencia n) es la raíz digital de 2^n. Por ejemplo,

   raizDigitalPotencia 6            ==  1
   raizDigitalPotencia (10^(10^8))  ==  7

Raíz digital

José A. Alonso

06-04-2021

Misceláneas

La raíz digital de un número entero positivo n es el dígito que resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

Definir la función

   raizDigital :: Integer -> Integer

tal que (raizDigital n) es la raíz digital del entero positivo n. Por ejemplo,

   raizDigital 23451  ==  6

Comprobar con QuickCheck las siguientes propiedades de la raíz digital:

D(m + n) = D(D(m) + D(n)).
D(mn) = D(D(m)D(n)).
D(m^n) = D(D(m)^n).
D(D(n)) = D(n).
D(n + 9) = D(n).
D(9n) = 9.

Antiimágenes de funciones crecientes bidimensionales

José A. Alonso

05-04-2021

Misceláneas

Una función f de pares de números naturales en números naturales es estrictamente creciente en ambos argumentos si

para x1 < x2, se tiene f(x1,y) < f(x1,y), para todo y y
para y1 < y2, se tiene f(x,y1) < f(x,y2), para todo x.

Por ejemplo, la función f definida por f(x,y) = x^2+3^y escreciente en ambos argumentos.

Las antiimágenes por f de t son los pares (x,y) tales que f(x,y) = t. Por ejemplo, las antimágenes por f(x,y) = x^2+3^y de 82 son los pares (1,4) y (9,0).

Definir la función

   antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

tal que (antiimagenes f t) es la lista de las antiimágenes por f de t, donde se supone que f es una función de pares de números naturales en números naturales que es estrictamente creciente en ambos argumentos. Por ejemplo,

   antiimagenes (\(x,y) -> x^2+3^y) 82        ==  [(1,4),(9,0)]
   antiimagenes (\(x,y) -> x^2+3^y) 387421785 == [(36,18)]

Antiimagen de función creciente

José A. Alonso

02-04-2021

Misceláneas

Una función f de los números naturales en los números naturales es estrictamente creciente si para cualquier par de números x, y tales que x < y se verifica que f(x) < f(y). La antiimagen por f de un número natural t es el número natural x tal que f(x) = t. No todos los números tienen antiimiagen por f, pero en caso de tenerla es única.

Definir la función

   antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer

tal que, suponiendo que f es una función creciente de los naturales en los naturales, (antiimagen f t) es justamente la antiimagen por f de t, si existe y es Nothing, en caso contrario. Por ejemplo,

   antiimagen (\x -> 2*x^2-3) 47  ==  Just 5
   antiimagen (\x -> 2*x^2-3) 48  ==  Nothing
   antiimagen (\x -> 2^x) 1024    ==  Just 10
   antiimagen (2^) 1024           ==  Just 10
   antiimagen (2^) (2^(10^7))     ==  Just 10000000
   antiimagen (2^) (1+2^(10^7))   ==  Nothing

Reducción de consecutivos relacionados

José A. Alonso

01-04-2021

Misceláneas

Definir la función

   reducida :: (a -> a -> Bool) -> [a] -> [a]

tal que (reducida r xs) obtenida elimando en xs las repeticiones de elementos consecutivos queverifican la relación r. Por ejemplo,

   reducida (==) [4,4,2,1,1,1,2,5]  ==  [4,2,1,2,5]
   reducida (<)  [4,4,2,1,1,1,2,5]  ==  [4,4,2,1,1,1]
   reducida (>=) [4,4,2,1,1,1,2,5]  ==  [4,5]
   reducida (>)  [4,4,2,1,1,1,2,5]  ==  [4,4,5]
   reducida (/=) [4,4,2,1,1,1,2,5]  ==  [4,4]

Lista muy decreciente

José A. Alonso

31-03-2021

Misceláneas

Una lista de números es muy decreciente si cada elemento es menor que la suma de los restantes. Por ejemplo, [19,9,6,2] es muy decreciente ya que

19 > 9 + 6 + 2,
9 > 6 + 2 y
6 > 2

En cambio, [19,8,6,2] no lo es ya que 8 = 6 + 2.

Definir la función

   muyDecreciente :: [Integer] -> Bool

tal que (muyDecreciente xs) se verifica si xs es muy decreciente. Por ejemplo,

   muyDecreciente [19,9,6,2]  ==  True
   muyDecreciente [19,8,6,2]  ==  False
   muyDecreciente [2^k | k <- [60000,59999..0]]  ==  True

Menor prefijo con suma positiva

José A. Alonso

30-03-2021

Misceláneas

Definir la función

   menorPrefijoSumaPositiva1 :: [[Int]] -> Maybe [[Int]]

tal que (menorPrefijoSumaPositiva1 xss) es justamente el menor prejijo de xss tal que la suma de lsas sumas de sus elementos es positivo y es Nothing si tal prefijo no existe. Por ejemplo,

   menorPrefijoSumaPositiva [[1],[-3],[2,4]]     == Just [[1]]
   menorPrefijoSumaPositiva [[-2,1],[-3],[2,4]]  == Just [[-2,1],[-3],[2,4]]
   menorPrefijoSumaPositiva [[-2,1],[3],[2,4]]   == Just [[-2,1],[3]]
   menorPrefijoSumaPositiva [[-2,1],[-3],[2,-4]] == Nothing
   menorPrefijoSumaPositiva [[-k..k] | k <- [1..5000]]              == Nothing
   fmap length (menorPrefijoSumaPositiva [[-3000..k] | k <- [0..]]) == Just 5198

Autonúmeros

José A. Alonso

29-03-2021

Misceláneas

Un autonúmero es un número entero n tal que no existe ningún número entero positivo k tal que n sea igual a la suma de k y los dígitos de k. Por ejemplo, 5 es un autonúmero pero 21 no lo es ya que 21=15+1+5.

Definir la lista

   autonumeros :: [Integer]

cuyos elementos son los autonúmeros. Por ejemplo,

   λ> take 20 autonumeros
   [1,3,5,7,9,20,31,42,53,64,75,86,97,108,110,121,132,143,154,165]
   λ> autonumeros !! 1200
   12236

Sucesiones de sumas digitales

José A. Alonso

26-03-2021

Misceláneas

La sucesión de las sumas digitales definida por un número a es sucesión a(n) tal que a(0) = a y a(n+1) es la suma de a(n) y los dígitos de a(n). Por ejemplo, los primeros términos de la sucesión de las sumas digitales definida por 1 son

   1,2,4,8,16,23,28,38,49,62,70,77,91,101,103,107,...

Se observa que el menor número que no pertenece a la sucesión anterior es 3. Los primeros términos de la sucesión de las sumas digitales definida por 3 son

   3,6,12,15,21,24,30,33,39,51,57,69,84,96,111,114,...

Se observa que el menor número que no pertenece a las 2 anteriores es 5. Los primeros términos de la sucesión de las sumas digitales definida por 5 son

   5,10,11,13,17,25,32,37,47,58,71,79,95,109,119,130,...

Se observa que el menor número que no pertenece a las 3 sucesiones anteriores es 7. Los primeros términos de la sucesión de las sumas digitales definida por 7 son

   7,14,19,29,40,44,52,59,73,83,94,107,115,122,127,137,...

Se observa que el menor número que no pertenece a las 4 anteriores es 9. Los primeros términos de la sucesión de las sumas digitales definida por 9 son

   9,18,27,36,45,54,63,72,81,90,99,117,126,135,144,153,...

Se observa que el menor número que no pertenece a las 5 sucesiones anteriores es 20. Los primeros términos de la sucesión de las sumas digitales definida por 20 son

   20,22,26,34,41,46,56,67,80,88,104,109,119,130,134,142,...

Definir la función

   sucesionSucesionesSumasDigitales :: [[Integer]]

tal que sus elementos son las sucesiones de sumas parciales tal que el primer elemento de cada sucesión es el menor elemento que no pertenece a las sucesiones anteriores. Por ejemplo,

   λ> map (take 4) (take 8 sucesionSucesionesSumasDigitales)
   [[1,2,4,8],[3,6,12,15],[5,10,11,13],[7,14,19,29],
    [9,18,27,36],[20,22,26,34],[31,35,43,50],[42,48,60,66]]
   λ> take 10 (sucesionSucesionesSumasDigitales3 !! 1000)
   [10199,10219,10232,10240,10247,10261,10271,10282,10295,10312]

Coste del recorrido ordenado

José A. Alonso

25-03-2021

Misceláneas

El coste de visitar los elementos de la lista [4,3,2,5,1] de manera creciente empezando en el primer elemento y siendo el coste de dada paso el valor absoluto de la diferencia de las posiciones se calcula de la siguiente manera

Coste de 4 a 1 = |0-4| = 4
Coste de 1 a 2 = |4-2| = 2
Coste de 2 a 3 = |2-1| = 1
Coste de 3 a 4 = |1-0| = 1
Coste de 4 a 5 = |0-3| = 3

Por tanto, el coste del recorrido es 4+2+1+1+3 = 11.

Definir la función coste :: Ord a => [a] -> Int tal que (coste xs) es el coste de visitar los elementos de xs de manera creciente empezando en el primer elemento y siendo el coste de dada paso el valor absoluto de la diferencia de las posiciones (se supone que los elementos de xs son distintos). Por ejemplo,

   coste [4,3,2,5,1] ==  11
   coste "betis"     ==  6

Mínimo número de divisiones para igualar

José A. Alonso

24-03-2021

Misceláneas

Mínima profundidad

José A. Alonso

23-03-2021

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Por ejemplo, los árboles

     1               3
    / \             /|\
   6   3           / | \
       |          5  4  7
       1          |     /\
                  3    6  5

se representan por

   ej1, ej2 :: Tree Int
   ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]]
   ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]]

Definir la función

    minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int

tal que (minimaProfundidad x ns) es justamente la mínima donde aparece x en el árbol ns, si aparece y Nothing, en caso contrario. Por ejemplo,

    minimaProfundidad 1 ej1  ==  Just 0
    minimaProfundidad 3 ej1  ==  Just 1
    minimaProfundidad 2 ej1  ==  Nothing
    minimaProfundidad 3 ej2  ==  Just 0
    minimaProfundidad 4 ej2  ==  Just 1
    minimaProfundidad 6 ej2  ==  Just 2
    minimaProfundidad 9 ej2  ==  Nothing

Árbol de las divisiones por 2, 3 ó 5

José A. Alonso

22-03-2021

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

Definir la función

   arbolDivisiones :: Int -> Tree Int

tal que (arbolDivisiones x) es el árbol de las divisiones enteras de x entre 2, 3 ó 5. Por ejemplo,

   λ> putStrLn (drawTree (fmap show (arbolDivisiones 20)))
   20
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 4
      |
      `- 2
         |
         `- 1

   λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))
   30
   |
   +- 15
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 3
   |     |
   |     `- 1
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 6
      |
      +- 3
      |  |
      |  `- 1
      |
      `- 2
         |
         `- 1

Cálculo de pi mediante la fórmula de Beeler

José A. Alonso

19-03-2021

Misceláneas

El pasado 12 de marzo se publicó en Twitter un mensaje con una fórmula de Beeler para el cálculo de pi: Cálculo de pi mediante la fórmula de Beeler

Los primeros valores son

   λ> 2*1
   2
   λ> 2*(1+1/3)
   2.6666666666666665
   λ> 2*(1+1/3+(1*2)/(3*5))
   2.933333333333333
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7))
   3.0476190476190474
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7)+(1*2*3*4)/(3*5*7*9))
   3.098412698412698

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Beeler. Por ejemplo,

     aproximacionPi 0    ==  2.0
     aproximacionPi 1    ==  2.6666666666666665
     aproximacionPi 2    ==  2.933333333333333
     aproximacionPi 3    ==  3.0476190476190474
     aproximacionPi 4    ==  3.098412698412698
     aproximacionPi 10   ==  3.141106021601377
     aproximacionPi 100  ==  3.1415926535897922
     pi                  ==  3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [0..99]) dibuja

Números ordenados con cuadrados ordenados

José A. Alonso

18-03-2021

Misceláneas

Un número es ordenado si cada uno de sus dígitos es menor o igual el siguiente dígito. Por ejemplo, 116 es un número creciente cuadrado es 13456 que también es ordenado. En cambio, 115 es ordenado pero su cuadrado es 13225 que no es ordenado.

Definir la lista

   numerosOrdenadosConCuadradosOrdenados :: [Integer]

cuyos elementos son los números ordenados cuyos cuadrados también lo son. Por ejemplo,

   λ> take 20 numerosOrdenadosConCuadradosOrdenados
   [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117]
   λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (10^6)))
   1411
   λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (5*10^6)))
   3159

Números con cuadrados con dígitos pares

José A. Alonso

17-03-2021

Misceláneas

Definir la lista

   numerosConCuadradosConDigitosPares :: [Integer]

cuyos elementos son los números cuyos cuadrados tienen todos sus dígitos pares. Por ejemplo,

   λ> take 20 numerosConCuadradosConDigitosPares
   [0,2,8,20,22,68,78,80,92,162,168,200,202,220,262,298,478,492,498,668]

Comprobar con QuickCheck que numerosConCuadradosConDigitosPares es infinita; es decir, para cualquier n posee algún elemento mayor que n.

Cálculo de pi mediante la fórmula de Bauer

José A. Alonso

16-03-2021

Misceláneas

El pasado 10 de marzo se publicó en Twitter un mensaje con una [fórmula de Bauer}(https://en.wikipedia.org/wiki/Gustav_Conrad_Bauer#Footnotes_in_the_history_of_mathematics) para el cálculo de pi Cálculo de pi mediante la fórmula de Bauer

Los primeros valores son

   λ> 2/1
   2.0
   λ> 2/(1 - 5*(1/2)^3)
   5.333333333333333
   λ> 2/(1 - 5*(1/2)^3 + 9*((1*3)/(2*4))^3)
   2.354022988505747
   λ> 2/(1 - 5*(1/2)^3 + 9*((1*3)/(2*4))^3 - 13*((1*3*5)/(2*4*6))^3)
   4.416172506738545

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Bauer. Por ejemplo,

     aproximacionPi 0         ==  2.0
     aproximacionPi 1         ==  5.333333333333333
     aproximacionPi 2         ==  2.354022988505747
     aproximacionPi 3         ==  4.416172506738545
     aproximacionPi (10^2)    ==  2.974407762733626
     aproximacionPi (10^2+1)  ==  3.3277148010019233
     aproximacionPi (10^3)    ==  3.0865454975585744
     aproximacionPi (10^3+1)  ==  3.1986099487445463
     aproximacionPi (10^4)    ==  3.1239682112773868
     aproximacionPi (10^4+1)  ==  3.1594161911246594
     aproximacionPi (10^5)    ==  3.135997665507836
     aproximacionPi (10^5+1)  ==  3.147207613460776
     pi                       ==  3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [0..99]) dibuja

Cálculo de pi mediante la fórmula de Euler

José A. Alonso

15-03-2021

Misceláneas

El pasado 6 de marzo se publicó en Twitter un mensaje con la siguiente fórmula de Euler para el cálculo de pi

Cálculo de pi mediante la fórmula de Euler

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Euler. Por ejemplo,

     aproximacionPi 1        ==  2.449489742783178
     aproximacionPi 10       ==  3.04936163598207
     aproximacionPi 100      ==  3.1320765318091053
     aproximacionPi 1000     ==  3.1406380562059946
     aproximacionPi 10000    ==  3.1414971639472147
     aproximacionPi 100000   ==  3.141583104326456
     aproximacionPi 1000000  ==  3.1415916986605086
     pi                      ==  3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [1..100]) dibuja

Cálculo de pi mediante la fórmula de Euler

Representaciones de un número como potencia

José A. Alonso

12-03-2021

Misceláneas

El número 512 se puede escribir de tres maneras como potencias:

   512 = 2⁹ = 8³ = 512¹

Definir las funciones

   potencias       :: Integer -> [(Integer,Integer)]
   numeroPotencias :: Integer -> Int

tales que

(potencias x) es la lista de las representaciones de x como potencias de números enteros positivos. Por ejemplo,

     potencias 7      ==  [(7,1)]
     potencias 8      ==  [(2,3),(8,1)]
     potencias 512    ==  [(2,9),(8,3),(512,1)]
     potencias 16384  ==  [(2,14),(4,7),(128,2),(16384,1)]
     potencias 65536  ==  [(2,16),(4,8),(16,4),(256,2),(65536,1)]

(numeroPotencias x) de las representaciones de x como potencias de números enteros positivos. Por ejemplo,

     numeroPotencias 7          ==  1
     numeroPotencias 8          ==  2
     numeroPotencias 512        ==  3
     numeroPotencias 16384      ==  4
     numeroPotencias 65536      ==  5
     numeroPotencias (2^(10^5)) ==  36

Cálculo de pi mediante la fórmula de Brouncker

José A. Alonso

11-03-2021

Misceláneas

El mes de marzo es el mes de pi, ya que el 14 de marzo (3/14) es el día de pi. Con ese motivo, el pasado 3 de marzo se publicó en Twitter un mensaje con la fórmula de Brouncker para el cálculo de pi Cálculo de pi mediante la fórmula de Brouncker

La primeras aproximaciones son

     a(1) = 4                                  =  4
     a(2) = 4/(1+1^2)                          =  2.0
     a(3) = 4/(1+1^2/(2+3^2))                  =  3.666666666666667
     a(4) = 4/(1+1^2/(2+3^2/(2+5^2)))          =  2.8
     a(5) = 4/(1+1^2/(2+3^2/(2+5^2/(2+7^2))))  =  3.395238095238095

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Brouncker. Por ejemplo,

     aproximacionPi 1      ==  4.0
     aproximacionPi 2      ==  2.0
     aproximacionPi 3      ==  3.666666666666667
     aproximacionPi 4      ==  2.8
     aproximacionPi 5      ==  3.395238095238095
     aproximacionPi 10     ==  3.0301437124966535
     aproximacionPi 1000   ==  3.1405916523380406
     aproximacionPi 1001   ==  3.142592653839793
     aproximacionPi 10000  ==  3.141492643588543
     aproximacionPi 10001  ==  3.1416926535900433
     pi                    ==  3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [10..100]) dibuja

Cálculo de pi mediante la serie de Madhava

José A. Alonso

10-03-2021

Misceláneas

El mes de marzo es el mes de pi, ya que el 14 de marzo (3/14) es el día de pi. Con ese motivo, el pasado 1 de marzo se publicó en Twitter un mensaje con la fórmula de Madhava para el cálculo de pi Cálculo de pi mediante la serie de Madhava

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: Int -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Madhava. Por ejemplo,

     aproximacionPi 0   ==  3.4641016151377544
     aproximacionPi 1   ==  3.0792014356780038
     aproximacionPi 2   ==  3.156181471569954
     aproximacionPi 10  ==  3.1415933045030813
     aproximacionPi 21  ==  3.1415926535879337
     pi                 ==  3.141592653589793

(grafica n) dibuja la gráfica de las k-ésimas aproximaciones de pi para k desde 0 a n. Por ejemplo, (grafica 30) dibuja

Sucesión de Rowland

José A. Alonso

09-03-2021

Misceláneas

Definir las siguientes sucesiones

   sucesionA       :: [Integer]
   sucesionB       :: [Integer]
   sucesionRowland :: [Integer]

tales que

el término n-ésimo de la sucesionA es a(n) definido por a(1) = 7 y a(n) = a(n-1) + mcd(n, a(n-1)), para n > 1. Por ejemplo,

     λ> take 20 sucesionA
     [7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44]

los términos de la sucesionB son las diferencias de los términos consecutivos de la sucesionA. Por ejemplo,

     λ> take 30 sucesionB
     [1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3,1,1,1,1,1,1,1]

los términos de la sucesionRowland son los términos de la sucesionB distintos de 1. Por ejemplo,\0

      λ> take 20 sucesionRowland
      [5,3,11,3,23,3,47,3,5,3,101,3,7,11,3,13,233,3,467,3]
      λ> sucesionRowland !! 92
      15567089

Comprobar con QuickCheck que los elementos de la sucesionRowland son números primos.

Nota: Eric S. Rowland demostró en A natural prime-generating recurrence que los elementos de la sucesionRowland son números primos.

Sumas parciales

José A. Alonso

08-03-2021

Misceláneas

Los sufijos de la lista [3,7,2,5,4,6] son

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

y la lista de sus sumas es [27,24,17,15,10,6,0].

Definir la función

   sumasParciales :: [Integer] -> [Integer]

tal que (sumasParciales xs) es la suma de los sufijos de xs. Por ejemplo,

   sumasParciales [3,7,2,5,4,6]  ==  [27,24,17,15,10,6,0]
   sumasParciales [1..10]        ==  [55,54,52,49,45,40,34,27,19,10,0]
   sum (sumasParciales [1..5*10^6])  ==  41666679166667500000

Siguiente equidigital

José A. Alonso

05-03-2021

Misceláneas

Dos números son equidigitales si tienen el mismo multiconjunto de dígitos. Por ejemplo, 2021 y 2120 son equidigitales ya que ambos tiene a {0,1,2,2} como su multiconjunto de dígitos.

Definir la función

   siguienteEquidigital :: Integer -> Maybe Integer

tal que (siguienteEquidigital n) es precisamente el menor número equidigital con n que es mayor que n (es decir, (Just x) si x es dicho número o Nothing si no hay ningún número equidigital con n que sea mayor que n). Por ejemplo,

   siguienteEquidigital 12    ==  Just 21
   siguienteEquidigital 21    ==  Nothing
   siguienteEquidigital 513   ==  Just 531
   siguienteEquidigital 531   ==  Nothing
   siguienteEquidigital 2021  ==  Just 2102
   siguienteEquidigital 2102  ==  Just 2120
   siguienteEquidigital 2120  ==  Just 2201
   siguienteEquidigital 2201  ==  Just 2210
   siguienteEquidigital 2210  ==  Nothing
   fmap (`mod` 1000) (siguienteEquidigital (2^(10^5)))  ==  Just 637

Suma de la lista reducida

José A. Alonso

04-03-2021

Misceláneas

Definir las siguientes funciones

   transformada :: Integral a => [a] -> [a]
   reducida     :: Integral a => [a] -> [a]
   sumaReducida :: Integral a => [a] -> a

tales que

(transformada xs) es la lista obtenida sustituyendo en el primer de elementos consecutivos de xs el mayor por su diferencia, donde se supone que xs es una lista de enteros positivos. Por ejemplo,

     transformada [7,2,6]  ==  [5,2,6]
     transformada [2,7,6]  ==  [2,5,6]
     transformada [2,2,6]  ==  [2,2,4]
     transformada [2,2,2]  ==  [2,2,2]

(reducida xs) es la lista obtenida aplicando la transformación anterior mientras sea posible (es decir, mientras tenga elementos distintos), donde se supone que xs es una lista de enteros positivos. Por ejemplo,

     reducida [7,2,6]   ==  [1,1,1]
     reducida [6,9,21]  ==  [3,3,3]

(sumaReducida xs) es la suma de la reducida de la lista xs. Por ejemplo,

     sumaReducida1 [7,2,6]   ==  3
     sumaReducida1 [6,9,21]  ==  9

Espirales

José A. Alonso

03-03-2021

Misceláneas

Definir la función

   espiral :: Int -> [[Int]]

tal que (espiral n) es la espiral de orden n (es decir, con n filas y n columnas). Por ejemplo,

   λ> mapM_ print (espiral 5)
   [1,1,1,1,1]
   [0,0,0,0,1]
   [1,1,1,0,1]
   [1,0,0,0,1]
   [1,1,1,1,1]
   λ> mapM_ print (espiral 6)
   [1,1,1,1,1,1]
   [0,0,0,0,0,1]
   [1,1,1,1,0,1]
   [1,0,0,1,0,1]
   [1,0,0,0,0,1]
   [1,1,1,1,1,1]
   λ> mapM_ print (espiral 7)
   [1,1,1,1,1,1,1]
   [0,0,0,0,0,0,1]
   [1,1,1,1,1,0,1]
   [1,0,0,0,1,0,1]
   [1,0,1,1,1,0,1]
   [1,0,0,0,0,0,1]
   [1,1,1,1,1,1,1]
   λ> mapM_ print (espiral 8)
   [1,1,1,1,1,1,1,1]
   [0,0,0,0,0,0,0,1]
   [1,1,1,1,1,1,0,1]
   [1,0,0,0,0,1,0,1]
   [1,0,1,0,0,1,0,1]
   [1,0,1,1,1,1,0,1]
   [1,0,0,0,0,0,0,1]
   [1,1,1,1,1,1,1,1]

Mínima diferencia de las sumas de las biparticiones de las N primeras potencias de dos

José A. Alonso

02-03-2021

Misceláneas

Se consideran las N primeras potencias de 2 (donde N es un número par). Por ejemplo, para N = 4, las potencias de 2 son 1, 2, 4 y 8. Las biparticiones de dichas potencias en dos conjuntos de igual tamaño son

   ([1,2],[4,8]), ([1,4],[2,8]), ([1,8],[2,4])

Las sumas de los elementos de las biparticiones son

   (3,12), (5,10), (9,6)

Los valores absolutos de las diferencias de dichas sumas son

   9, 5, 3

El mínimo de dichas diferencias es 3.

Definir la función

  minimaDiferencia :: Integer -> Integer

tal que (minimaDiferencia n) es la mínima diferencia de las sumas las biparticiones de las n (donde n es un número par) primeras potencias de dos conjuntos con igual número de elementos. Por ejemplo,

   minimaDiferencia 4  ==  3
   minimaDiferencia 6  ==  7
   minimaDiferencia (10^9) `mod` (10^9)  ==  787109375

Índice del menor elemento a eliminar para que la suma sea divisible por k

José A. Alonso

01-03-2021

Misceláneas

Definir la función

   indice :: [Int] -> Int -> Maybe Int

tal que (indice xs k) es el índice del menor elemento a eliminar de la lista de enteros positivos xs para que la suma de los restantes sea divisible por k o Nothing, si no existe dicho elemento. Por ejemplo,

   indice [1,8,4,1] 2         ==  Just 2
   indice [4,6,7,5,7] 11      ==  Just 2
   indice [4,6,7,5,7] 12      ==  Just 3
   indice [4,6,7,5,7] 13      ==  Nothing
   indice [1..10^7] 7         ==  Just 5
   indice [10^7,10^7-1..1] 7  ==  Just 9999994

Eliminaciones anotadas

José A. Alonso

26-02-2021

Misceláneas

Definir la función

eliminaciones :: [a] -> [(a,Int,[a])]

tal que (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un elemento de xs, i es la posición de x en xs y zs es la lista de los restantes elementos de xs. Por ejemplo,

λ> eliminaciones [5,7,6,5]
[(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])]

Ternas crecientes de primos con el mayor igual a la suma de los menores

José A. Alonso

25-02-2021

Misceláneas

Definir la función

ternasPrimas :: [(Integer,Integer,Integer)]

tal que sus elementos son las ternas crecientes de primos con el mayor igual a la suma de los menores. Por ejemplo,

ternasPrimas  ==  (2,3,5)
ternasPrimas !! 34567  ==  (2,5393909,5393911)

Máximo de las rotaciones

José A. Alonso

24-02-2021

Misceláneas

Las rotaciones del número 3252 son [3252,2523,5232,2325] y el mayor de dichos números es 5232.

Definir la función

maximoRotaciones :: Integer -> Integer

tal que (maximoRotaciones n) es el mayor número obtenido rotando los dígitos de n. Por ejemplo,

maximoRotaciones 3252    ==  5232
maximoRotaciones 913942  ==  942913
maximoRotaciones (234 + 10^(10^6)) `div` (10^(10^6))  ==  4

Particiones por un elemento

José A. Alonso

23-02-2021

Misceláneas

Definir la función

particiones :: Eq a => [a] -> a -> [([a],[a])]

tal que (particiones xs y) es lalista delas particiones de xs en dos partes tales que el primer elemento de la segunda parte es y. Por ejemplo,

particiones [2,9,1,3,9,4] 9   == [([2],[9,1,3,9,4]),([2,9,1,3],[9,4])]
particiones [2,9,1,3,9,4] 3   == [([2,9,1],[3,9,4])]
particiones [2,9,1,3,9,4] 7   == []
particiones "Particiones" 'i' == [("Part","iciones"),("Partic","iones")]

Sumas de potencias que son cuadrados perfectos

José A. Alonso

22-02-2021

Misceláneas

El 2º problema de la ONEM (Olimpíada Nacional Escolar de Matemática) de Mayo del 2020 dice

Determinar si existen enteros positivos a, b y c, no necesariamente distintos, tales que [latex]a+b+c=2020[/latex] y [latex]2^a + 2^b + 2^c[/latex] es un cuadrado perfecto.

Definir la función

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

tales que (soluciones k n) es la lista de las ternas no decrecientes (a,b,c) tales que que a+b+c=n y k^a + k^b + k^c es un cuadrado perfecto. Por ejemplo,

soluciones 2 19  ==  [(2,6,11),(2,7,10),(4,7,8),(5,5,9),(6,6,7)]
soluciones 3 19  ==  []
take 2 (soluciones 2 2020)  ==  [(2,674,1344),(4,674,1342)]

Números balanceados

José A. Alonso

19-02-2021

Misceláneas

Un número está balanceado si tiene un número par de divisores primos (contados con su multiplicidad). Por ejemplo, 60 es balanceado porque tiene 4 divisores primos (2, 2, 3 y 5).

Un balanceador del entero positivo k es par de enteros positivos (a,b) tales que a es menor que b y, para todo x entre 1 y k, el valor del polinomio P(x) = (x+a)*(x+b) es un número balanceado. Por ejemplo, (2,4) es un balanceador de 3 ya que

P(1) = (1+2)*(1+4) = 15 = 3*5     es balanceado
P(2) = (2+2)*(2+4) = 24 = 2*2*2*3 es balanceado
P(3) = (3+2)*(3+4) = 35 = 5*7     es balanceado

Definir la función

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

tal que (balanceadores k) es el conjunto de los balanceadores de k. Por ejemplo,

λ> take 7 (balanceadores 3)
[(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)]
λ> take 7 (balanceadores 5)
[(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)]
λ> take 7 (balanceadores 3)
[(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)]
λ> take 7 (balanceadores 4)
[(6,11),(8,14),(9,15),(10,17),(6,18),(11,18),(7,19)]
λ> take 7 (balanceadores 5)
[(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)]
λ> head (balanceadores 19)
(1325,2827)

Nota: Este ejercicio está basado en el problema N2 de la Olimpíada Internacional de Matemáticas (IMO) del 2009.

Máximos locales y sus posiciones

José A. Alonso

18-02-2021

Misceláneas

Los máximos locales de [7,2,3,4,4,4,0,1,1,0,1,4,9] son el 4 (que se encuentra en la posicón 3 (empezando a contar en 0)) y el 1 que se encuentra en la posición 7. En cada meseta, por ejemplo la formada por los tres 4 en las posiciones 3, 4 y 5, sólo se considera el primer elemento (en este caso, el de la posición 3) y se compara con el primero después de la meseta (en este caso, el 0 de la posición 6).

Los extremos de la lista no se consideran máximos locales. Por ejmplo, la listas [1,2,2,2,3] y [1,2,2,2,2] no tienen máximos locales.

Definir la función

maximosLocales :: Ord a => [a] -> [(a,Int)]

tal que (maximosLocales xs) es la lista de los máximos locales de xs junto con sus posiciones. Por ejemplo,

maximosLocales [7,2,3,4,4,4,0,1,1,0,1,4,9]  ==  [(4,3),(1,7)]
maximosLocales [1,2,2,2,3]  ==  []
maximosLocales [1,2,2,2,2]  ==  []

Mínimo número de saltos para alcanzar el final

José A. Alonso

17-02-2021

Misceláneas

Dada una lista de enteros positivos, se interpreta cada elemento el máximo número de pasos que se puede avanzar desde dicho elemento. Por ejemplo, para la lista [1,3,5,8,9,2,6,7,6,8,9], desde sólo se puede avanzar un paso (hasta el 3), desde el 3 se puede avanzar 3 pasos (hasta el 5, 8 ó 9), y así sucesivamente. En dicha lista, el mínimo número de saltos que hay que dar para alcanzar el final es 3 (el recorrido es 1, 3, 8, 9).

Definir la función

minimoSaltos :: [Int] -> Int

tal que (minimoSaltosxs) es el mínimo número de saltos que hay que dar en la lista xs para alcanzar el final. Por ejemplo,

minimoSaltos [1,3,5,8,9,2,6,7,6,8,9]  ==  3
minimoSaltos (replicate 10 1)         ==  9
minimoSaltos [1..25]                  ==  5

Cantidad de números oblongos en un intervalo

José A. Alonso

16-02-2021

Misceláneas

Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.

La sucesión de los números oblongos es

0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, ...

En el intervalo [10,30] hay 3 números oblongos (el 12, el 20 y el 30).

Definir las funciones

oblongos            :: [Integer]
oblongosEnIntervalo :: Integer -> Integer -> Int

tales que

oblongos es la sucesión de los números oblongos. Por ejemplo,

take 15 oblongos   == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]
oblongos !! 50     == 2550
oblongos !! (10^5) == 10000100000
oblongos !! (10^6) == 1000001000000
oblongos !! (10^7) == 100000010000000

(oblongosEnIntervalo a b) es la cantidad de números oblongos en el intervalo [a,b]. Por ejemplo,

oblongosEnIntervalo 10 30           ==  3
oblongosEnIntervalo (10^3) (10^10)  ==  99968
oblongosEnIntervalo (10^3) (10^12)  ==  999968
oblongosEnIntervalo (10^3) (10^14)  ==  9999968

Mínima suma borrando todas las ocurrencias de un dígito

José A. Alonso

15-02-2021

Misceláneas

Para la lista [23,12,77,82], las sumas obtenidas eliminando todas las ocurrencias de uno de sus dígitos son

+ Eliminando el 1: 23 +  2 + 77 + 82 = 184
+ Eliminando el 2:  3 + 1  + 77 + 8  =  89
+ Eliminando el 3: 2  + 12 + 77 + 82 = 173
+ Eliminando el 7: 23 + 12      + 82 = 117
+ Eliminando el 8: 23 + 12 + 77 +  2 = 114

El mínimo de las sumas es 89 (que se obtiene eliminando todas las ocurrencias del dígito 2).

Definir la función

minimaSumaEliminandoDigito :: [Integer] -> Integer

tal que (minimaSumaEliminandoDigito xs) es el mínimo de las sumas obtenidas eliminando todas las ocurrencias de uno de los dígitos de xs. Por ejemplo,

minimaSumaEliminandoDigito [23,12,77,82]  ==  89
minimaSumaEliminandoDigito [2312,7,4,82]  ==  50

Descomposición de N en K sumandos pares distintos

José A. Alonso

12-02-2021

Misceláneas

Definir las funciones

sumas  :: Integer -> Integer -> [[Integer]]
esSuma :: Integer -> Integer -> Bool

tales que

(sumas n k) es la lista de las descomposiones de n en k sumandos pares y distintos. Por ejemplo,

sumas 16 3  ==  [[2,4,10],[2,6,8]]
sumas 18 4  ==  []

(esSuma n k) se verifica si n se puede escribir como suma de k sumandos pares y distintos. Por ejemplo,

esSuma 16 3  ==  True
esSuma 18 4  ==  False
esSuma (10^5000) (10^7)  ==  True
esSuma (11^5000) (10^7)  ==  False

Menor número con una cantidad dada de divisores

José A. Alonso

11-02-2021

Misceláneas

El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

Definir la función

menor :: Integer -> Integer

tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,

menor 1  ==  2
menor 2  ==  6
menor 3  ==  24
menor 4  ==  120
length (show (menor (4*10^4)))  ==  207945

Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.

Ternas potencias de dos

José A. Alonso

10-02-2021

Misceláneas

Una terna (a,b,c) de números enteros positivos es especial si se verifica que ab-c, bc-a y ca-b son potencias de 2. Por ejemplo, (3,5,7) es especial ya que

3 * 5 - 7 =  8 = 2^3
5 * 7 - 3 = 32 = 2^5
7 * 3 - 5 = 16 = 2^4

Definir las funciones

esEspecial       :: (Integer,Integer,Integer) -> Bool
ternasEspeciales :: [(Integer,Integer,Integer)]

tales que

(esEspecial t) se verifica si t es una terna especial. Por ejemplo,

esEspecial (3,5,7)  ==  True
esEspecial (5,7,9)  ==  False

ternasEspeciales es la lista de las ternasEspeciales ordenadas según su suma y las de la misma suma por orden lexicográfico. Por ejemplo,

λ> take 16 ternasEspeciales
[(2,2,2),
 (2,2,3),(2,3,2),(3,2,2),
 (3,5,7),(3,7,5),(5,3,7),(5,7,3),(7,3,5),(7,5,3),
 (2,6,11),(2,11,6),(6,2,11),(6,11,2),(11,2,6),(11,6,2)]

Comprobar con QuickCheck que sólo hay 16 ternas especiales; es decir, para toda terna t de enteros positivos, t pertenece a la lista de los 16 primeros elementos de ternasEspeciales o no es una terna especial.

Nota: Este ejercicio está basado en el problema N5 de la Olimpíada Internacional de Matemáticas (IMO) del 2015.

Ordenación de ternas de enteros

José A. Alonso

09-02-2021

Misceláneas

Las ternas de números enteros positivos se pueden ordenar por su suma y las de la misma suma por orden lexicográfico. Por ejemplo,

ternas de suma 3:

(1,1,1)

ternas de suma 4:

(1,1,2),(1,2,1),(2,1,1)

ternas de suma 5:

(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)

ternas de suma 6

(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)

y así sucesivamente.

Definir la función

ternas :: [(integer,integer,integer)]

tal que ternas es la lista de las ternas de enteros positivos con el orden descrito anteriormente. por ejemplo,

λ> take 20 ternas
[(1,1,1),
 (1,1,2),(1,2,1),(2,1,1),
 (1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1),
 (1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)]

Mayor número borrando k dígitos

José A. Alonso

08-02-2021

Misceláneas

Definir la función

mayorBorrando :: Int -> Integer -> Integer

tal que (mayorBorrando k n) es el mayor número obtenido borrando k dígitos de n (se supone que n tiene más de k dígitos). Por ejemplo,

mayorBorrando 1 6782334  ==  782334
mayorBorrando 3 6782334  ==  8334
mayorBorrando 3 10020    ==  20
mayorBorrando 1000000 (4256 + 10^1000004) == 14256

Listas obtenidas borrando k elementos

José A. Alonso

05-02-2021

Misceláneas

Definir la función

borra :: Int -> [a] -> [[a]]

tal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo,

borra 0 "abcd"  ==  ["abcd"]
borra 1 "abcd"  ==  ["abc","abd","acd","bcd"]
borra 2 "abcd"  ==  ["ab","ac","ad","bc","bd","cd"]
borra 3 "abcd"  ==  ["a","b","c","d"]
borra 4 "abcd"  ==  [""]
borra 5 "abcd"  ==  []
borra 6 "abcd"  ==  []
length (borra 2 [1..300])  ==  44850

Pares con múltiplos con igual número de divisores

José A. Alonso

04-02-2021

Misceláneas

Definir la función

paresNoDivisible :: [(Integer, Integer)]

tal que paresNoDivisible es la lista de los pares (n,k) tales que n < k y k no es divisible por n. Por ejemplo,

λ> take 10 paresNoDivisible
[(2,3),(3,4),(2,5),(3,5),(4,5),(4,6),(5,6),(2,7),(3,7),(4,7)]

Se observa que en el resultado los pares se ordenan primero según su segundo elemento y los que tienen el mismo segundo elemento se ordenan por el primer elemento.

Un par especial es un par de enteros positivos (n,k) tales que existe algún s tal que \(s \times n\) y \(s \times k\) tienen el mismo número de divisores. Por ejemplo, (3,4) es un par especial ya que \(2 \times 3\) y \(2 \times 4\) tienen 4 divisores.

Comprobar con QuickCheck todos los elementos de paresNoDivisible son pares especiales.

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2018.

Los números armónicos no son enteros

José A. Alonso

03-02-2021

Misceláneas

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.

Partición por suma

José A. Alonso

02-02-2021

Misceláneas

Definir la función

particion :: Int -> [Int] -> [[Int]]

tal que (particion n xs) es la lista de los elementos de xs, en el mismo orden, agrupados en listas con sumas menores o iguales que n. Por ejemplo,

particion 6 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1,3],[2,2,2],[1,2,2],[3]]
particion 5 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3,2],[2,2,1],[2,2],[3]]
particion 4 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2,2],[2,1],[2,2],[3]]
particion 3 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2],[2],[2,1],[2],[2],[3]]
particion 2 [1,1,1,3,2,2,2,1,2,2,3] == []

Con algún nueve

José A. Alonso

01-02-2021

Misceláneas

Definir las funciones

numerosConNueve :: [Integer]
conNueve :: Integer -> Integer

tales que

numerosConNueve es la lista de los números con algún dígito igual a 9. Por ejemplo,

λ> take 20 numerosConNueve
[9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109]

(conNueve n) es la cantidad de números enteros no negativos menores o iguales que n con algún dígito igual a 9. Por ejemplo,

conNueve 1   ==  0
conNueve 10  ==  1
conNueve 90  ==  10
length (show (conNueve (10^3)))      ==  3
length (show (conNueve (10^30)))     ==  30
length (show (conNueve (10^300)))    ==  300
length (show (conNueve (10^3000)))   ==  3000
length (show (conNueve (10^30000)))  ==  30000

Terna pitagórica en la que el perímetro es múltiplo de uno de los catetos

José A. Alonso

29-01-2021

Misceláneas

La terna (n,a,b) es una terna pitagórica si n² = a²+b² y b < a < n. Por ejemplo, (5,4,3) y (10,8,6) son ternas pitagóricas.

Una terna pitagórica es primitiva si sus tres componentes son primos entre sí. Por ejemplo, (5,4,3) es una terna pitagórica primitiva y (10,8,6) es una terna pitagórica no primitiva (ya que sus tres lados son divisibles por 2).

Los elementos (n,a,b) de una terna pitagórica son las longitudes de los lados de un triágulo rectángulo; concretamente n es la longitud de la hipotenusa, a la del cateto mayor y b la del cateto menor. Su perímetro es n+a+b.

Definir la función

ternasPPPDC :: [(Integer,Integer,Integer)]

tal que ternasPPPDC es la lista de las ternas pitagóricas primitivas tales que su perímetro es divisibe por alguno de los catetos. Por ejemplo,

λ> take 5 ternasPPPDC
[(5,4,3),(13,12,5),(17,15,8),(25,24,7),(37,35,12)]
λ> [n | (n,a,b) <- take 15 ternasPPPDC]
[5,13,17,25,37,41,61,65,85,101,113,145,145,181,197]
λ> ternasPPPDC !! 80
(4705,4704,97)

Comprobar con QuickCheck que existen infinitas ternas pitagóricas primitivas tales que su perímetro es divisibe por alguno de los catetos; es decir, para todo x existe alguna terna (n,a,b) en ternasPPPDC tal que n es mayor que x.

Referencia: Este ejercicio está basado en el artículo Terna pitagórica en la que el perímetro es múltiplo de uno de los catetos publicado por Antonio Roldán en "Números y hoja de cálculo" el 21 de enero de 2021.

El número de Dottie

José A. Alonso

28-01-2021

Misceláneas

La sucesión de Dottie correspondiente a un número x se obtiene a partir de x aplicándole la función coseno al término anterior. Por ejemplo, empezando en el 2021 los términos de la sucesión de Dottie son

d(0) = 2021
d(1) = cos(2021)                = -0.5768544484396986
d(2) = cos(-0.5768544484396986) = 0.8381823464377144
d(3) = cos(0.8381823464377144)  = 0.6688152257126013
d(4) = cos(0.6688152257126013)  = 0.7845568438177061
d(5) = cos(0.7845568438177061)  = 0.7077014336446841
d(6) = cos(0.7077014336446841)  = 0.7598581544800473
d(7) = cos(0.7598581544800473)  = 0.7249337238692606
d(8) = cos(0.7249337238692606)  = 0.7485433703735275

Definir las funciones

sucesionDottie :: Double -> [Double]
limite :: [Double] -> Double -> Int -> Double

tales que

(sucesionDottie x) es la lista de los términos de la sucesión de Dottie correspondiente a x. Por ejemplo,

λ> mapM_ print (take 10 (sucesionDottie 2021))
2021.0
-0.5768544484396986
0.8381823464377144
0.6688152257126013
0.7845568438177061
0.7077014336446841
0.7598581544800473
0.7249337238692606
0.7485433703735275
0.7326809874975466
λ> mapM_ print (take 10 (drop 85 (sucesionDottie 2021)))
0.7390851332151601
0.739085133215161
0.7390851332151605
0.7390851332151608
0.7390851332151606
0.7390851332151607
0.7390851332151607
0.7390851332151607
0.7390851332151607
0.7390851332151607

(limite xs a n) es el límite de xs con aproximación a y amplitud n; es decir, el primer término x de la sucesión tal que el valor absoluto de x y cualquiera de sus n siguentes elementos es menor que a. Por ejemplo,

λ> limite [(2*n+1)/(n+5) | n <- [1..]] 0.001 300
1.993991989319092
λ> limite [(2*n+1)/(n+5) | n <- [1..]] 1e-6 300
1.9998260062637745
λ> limite [(1+1/n)**n | n <- [1..]] 0.001 300
2.7155953364173175
λ> limite (sucesionDottie 2021) 1e-16 100
0.7390851332151607
λ> limite (sucesionDottie 27) 1e-16 100
0.7390851332151607

Comprobar con QuickCheck que, para todo número x, el límite de la sucesión de Dottie generada por x es mismo; es decir, si x e y son dos números cualesquiera, entonces

limite (sucesionDottie x) 1e-16 100 ==
limite (sucesionDottie y) 1e-16 100

Dicho límite es el número de Dottie.

Referencia: Este ejercicio está basado en el artículo El número de Dottie publicado por Miguel Ángel Morales en Gaussianos el 20 de enero de 2021.

Árboles con valores acotados

José A. Alonso

27-01-2021

Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show

Por ejemplo, el árbol

      7
     / \
    /   \
   /     \
  4       9
 / \     / \
1   3   5   6

se puede representar por

N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

Un árbol está acotado por un conjunto ys si todos los valores de sus hojas y sus nodos pertenecen a ys. Por ejemplo, el árbol anterior está acotado por [1..10] pero no lo está por [1..7].

Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros

  5          9           5          9
 / \        / \         / \        / \
5   5      9   9       5   6      9   7
              / \                    / \
             9   9                  9   9

Definir las funciones

acotado :: Eq a => Arbol a -> [a] -> Bool
monovalorados :: Arbol -> [Arbol]

tales que

(acotado a ys) se verifica si a está acotado por ys. Por ejemplo,

acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True
acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7]  == False

(monovalorado a) se verifica si a es monovalorado. Por ejemplo,

monovalorado (N 5 (H 5) (H 5))              ==  True
monovalorado (N 5 (H 5) (H 6))              ==  False
monovalorado (N 9 (H 9) (N 9 (H 9) (H 9)))  ==  True
monovalorado (N 9 (H 9) (N 7 (H 9) (H 9)))  ==  False
monovalorado (N 9 (H 9) (N 9 (H 7) (H 9)))  ==  False

Limitación del número de repeticiones

José A. Alonso

26-01-2021

Misceláneas

Definir la función

conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a]

tal que (conRepeticionesAcotadas xs n) es una lista que contiene cada elemento de xs como máximo n veces sin reordenar (se supone que n es un número positivo).. Por ejemplo,

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 1  ==  [1,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 2  ==  [1,2,3,1,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 3  ==  [1,2,3,1,2,1,3,2,3,5]
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 4  ==  [1,2,3,1,2,1,3,2,3,5]

Potencias de dos más cercanas

José A. Alonso

25-01-2021

Misceláneas

Definir la función

potenciasDeDosMasCercanas :: [Integer] -> [Integer]

tal que (potenciasDeDosMasCercanas xs) es la lista sustituyendo cada elemento de xs por su potencia de dos más cercana (en el caso de que haya dos equidistantes se elige la menor). Por ejemplo,

potenciasDeDosMasCercanas2 [6,7,8,9,2021]  ==  [4,8,8,8,2048]

La serie 1 - 2 + 3 - 4 + ···

José A. Alonso

22-01-2021

Misceláneas

En este ejercicio se considerará la serie

1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 10 + ···

Definir las funciones

serie     :: [Integer]
sumaSerie :: Integer -> Integer

tales que

serie es lalista de los términos de la serie anterior; es decir,

take 7 serie  ==  [1,-2,3,-4,5,-6,7]

(sumaSerie n) es la suma de los n primeros términos de la serie. Por ejemplo,

sumaSerie 5     ==  3
sumaSerie 6     ==  -3
sumaSerie 2021  ==  1011
length (show (sumaSerie (10^1000)))  ==  1001

Comprobar con QuickCheck que

la suma de la serie se puede hacer tan grande como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es mayor que a;
la suma de la serie se puede hacer tan pequeña como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es menor que a.

Clausura respecto del valor absoluto de las diferencias

José A. Alonso

21-01-2021

Misceláneas

Dado un conjunto de números enteros positivos S su clausura del valor absoluto de la diferencia de pares es el menor conjunto T tal que T contiene a S y para cualquier par de elementos x e y de T (con x distinto de y) el valor absoluto de (x-y) también es un elemento de T. Por ejemplo, si S = {12, 30}, entonces

12 ∈ T, porque 12 ∈ S
30 ∈ T, porque 20 ∈ S
18 = |12 - 30| ∈ T
6 = |18 - 12| ∈ T
24 = |30 - 6| ∈ T

Por tanto, T = {12, 30, 18, 6, 24}.

Definir las funciones

clausura :: [Int] -> [Int]
longitudClausura :: [Int] -> Int

tales que

(clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

clausura [12,30]  ==  [12,30,18,6,24]
clausura [3,5,2]  ==  [3,5,2,1,4]

(longitudClausura xs) es el número de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

longitudClausura [12,30]        ==  5
longitudClausura [3,5,2]        ==  5
longitudClausura [3,23..10^6]   ==  999983

Números en potencias de dos

José A. Alonso

20-01-2021

Misceláneas

Las potencias de dos son

1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...

Se observa que la primera potencia de dos que contiene al 638 es la 14 ya que 2^14 = 16384.

Definir la función

potenciasContenedoras :: Integer -> [Integer]

tal que (potenciasContenedoras x) es la lista de las potencias de 2 que contienen a x. Por ejemplo,

λ> head (potenciasContenedoras 638)
14
λ> head (potenciasContenedoras 2021)
452
λ> take 20 (potenciasContenedoras 4)
[2,6,10,11,12,14,18,19,20,22,25,26,27,28,30,31,32,33,34,35]
λ> [head (potenciasContenedoras n) | n <- [0..20]]
[10,4,1,5,2,8,4,15,3,12,10,40,7,17,18,21,4,27,30,13,11]

Comprobar con QuickCheck si todos los números naturales están contenenidos en alguna potencia de 2.

Buenos primos

José A. Alonso

19-01-2021

Misceláneas

La sucesión de los números primos es

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

Las parejas de primos equidistantes de 5 en dicha sucesión son (3, 7) y (2, 11). Se observa que el cuadrado de 5 es mayor que el producto de los elementos de dichas parejas; es decir,

5^2 = 25 > 21 = 3 x 7
5^2 = 25 > 22 = 2 x 11

En cambio, el 7 tiene una pareja de primos equidistantes (la (5, 11)) cuyo producto es mayor que el cuadrado de 7.

7^2 = 49 < 55 = 5 x 11

Un buen primo es un número primo cuyo cuadrado es mayor que el producto de dos primos cualesquiera equidistantes de él en la sucesión de primos. Por ejemplo, 5 es un buen primo pero 7 no lo es.

Definir las funciones

esBuenPrimo  :: Integer -> Bool
buenosPrimos :: [Integer]

tales que

(esBuenPrimo n) se verifica si n es un buen primo. Por ejemplo,

esBuenPrimo 5        ==  True
esBuenPrimo 7        ==  False
esBuenPrimo 8746811  ==  True

buenosPrimos es la lista de los buenos primos. Por ejemplo,

λ> take 12 buenosPrimos
[2,5,11,17,29,37,41,53,59,67,71,97]

Comprobar con QuickCheck que la lista de los buenos primos es infinita; es decir, para cualquier entero positivo n existe un número mayor que n que es un buen primo.

Números equidigitales

José A. Alonso

18-01-2021

Misceláneas

Un número equidigital es un número natural que tiene el mismo número de dígitos que el número de dígitos en su factorización prima, incluidos los exponentes mayores que 1. Por ejemplo,

10 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (2 x 5).
25 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (5^2).
121 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (11^2).
175 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (5^2 x 7).
1125 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3^2 x 5^3).
2021 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (43 x 47).
3072 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3 x 2^10).

Definir las funciones

esEquidigital :: Int -> Bool
equidigitales :: [Int]

tal que

(esEquidigital x) se verifica si x es un número equidigital. Por ejemplo.

esEquidigital 10    ==  True
esEquidigital 11    ==  True
esEquidigital 2021  ==  True
esEquidigital 2022  ==  False

equidigitales es la lista de los números equidigitales. Por ejemplo,

λ> take 20 equidigitales
[2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]
λ> equidigitales !! 755
2021
λ> equidigitales !! 100000
405341

Comprobar con QuickChek que el conjunto de los números equidigitales es infinito; es decir, para cada entero n existe un equidigital mayor que n.

Números compuestos persistentes

José A. Alonso

15-01-2021

Misceláneas

Un número compuesto persistente es un número compuesto que no se puede transformar en un número primo cambiando sólo uno de sus dígitos. Por ejemplo,

20 no es un compuesto persistente porque cambiando su último dígito por un 3 se transforma en 23 que es primo.
25 no es un compuesto persistente porque cambiando su primer dígito por un 0 se transforma en 5 que es primo.
200 es un compuesto persistente ya que al cambiar su útimo dígito por un impar se obtienen los números 201, 203, 207, 205 y 209 que no son primos y todos sus demás transformados son pares y, por tanto, tampoco son primos.

Definir las funciones

esCompuestoPersistente :: Integer -> Bool
compuestosPersistentes :: [Integer]

tales que

(esCompuestoPersistente n) se verifica si n es un número compuesto persistente. Por ejemplo,

esCompuestoPersistente 20    ==  False
esCompuestoPersistente 200   ==  True
esCompuestoPersistente 2021  ==  False

compuestosPersistentes es la lista de los números compuestos persistentes. Por ejemplo,

λ> take 10 compuestoPersistentes
[200,204,206,208,320,322,324,325,326,328]

Comprobar con QuickCheck que todos los números de la forma 510+2310*k son números compuestos persistentes.

Números bigenerados

José A. Alonso

14-01-2021

Misceláneas

Se dice que y es un generador de x si x es igual a la suma de y los dígitos de y. Por ejemplo, 1996 y 2014 son generadores de 2021 ya que

2021 = 1996 + 1 + 9 + 9 + 6
2021 = 2014 + 2 + 0 + 1 + 4

Un número bigenerado es un número que tiene exactamente 2 generadores. Por ejemplo,

2021 es un número bigenerados y sus generadores son 1996 y 2014
20 no es bigenerador porque no tiene ningún generador
21 no es bigenerador porque tiene sólo un generador (el 15).
101 es el menor número bigenerado y sus generadores son 91 y 100.

Definir las funciones

esBigenerado :: Integer -> Bool
bigenerados  :: [Integer]

tales que

(esBigenerado x) se verifica si x es bigenerado. Por ejemplo,

esBigenerado 2021  ==  True
esBigenerado 20    ==  False
esBigenerado 21    ==  False
esBigenerado 101   ==  True

bigenerados es la lista de los números bigenerados. Por ejemplo,

λ> take 12 bigenerados
[101,103,105,107,109,111,113,115,117,202,204,206]

Comprobar con QuickCheck que la lista de los números bigenerados es infinita; es decir, para cualquier número positivo n existe un y mayor que x que es bigenerado.

Números cíclicos

José A. Alonso

13-01-2021

Misceláneas

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,

φ(15) = 8 ya que los números menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.
φ(21) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.

Un número n es un número cíclico si n y φ(n) no tiene ningún divisor primo común. Por ejemplo, el número 15 es cíclico ya que 15 y 8 (que es φ(15)) no tiene ningún divisor primo común; en cambio, el número 21 no es cíclico ya 21 y 12 (que es φ(21)) son divisibles por 3.

Definir las funciones

esCiclico :: Integer -> Bool
ciclicos  :: [Integer]

tales que

(esCiclico n) se verifica si n es un número cíclico. Por ejemplo,

esCiclico 15    ==  True
esCiclico 16    ==  False
esCiclico 2021  ==  True
esCiclico (product [1..10^4])  ==  False

ciclicos es la lista de los números cíclicos. Por ejemplo,

λ> take 20 ciclicos
[2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]
λ> ciclicos !! (10^5)
336059

Comprobar con QuickCheck que todos los números primos mayores que 2 son cíclicos.

Números duffinianos

José A. Alonso

12-01-2021

Misceláneas

Los números duffinianos, llamados así por Richard Duffy, son los números compuestos n que son coprimos con la suma de sus divisores; es decir, n y la suma de los divisores de n no tienen ningún factor primo común.

Por ejemplo, 35 es un número duffiniano ya que la suma de sus divisores es 1 + 5 + 7 + 35 = 48 que es coprimo con 35.

Definir las funciones

esDuffiniano :: Integer -> Bool
duffinianos :: [Integer]

tales que

(esDuffiniano n) se verifica si n es duffiniano. Por ejemplo,

esDuffiniano 35    ==  True
esDuffiniano 2021  ==  True
esDuffiniano 11    ==  False
esDuffiniano 12    ==  False
esDuffiniano (product [1..2*10^4])  ==  False

duffinianos es la sucesión de los números duffinianos. Por ejemplo,

take 12 duffinianos  ==  [4,8,9,16,21,25,27,32,35,36,39,49]
length (takeWhile (<10^5) duffinianos)  ==  24434

Comprobar con QuickCheck que los números de la forma p^k, con p un primo mayor que 2 y k un entero mayor que 1, son duffinianos.

Caminos reducidos

José A. Alonso

05-06-2020

Misceláneas

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Subexpresiones aritméticas

José A. Alonso

04-06-2020

Misceláneas

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Número como suma de sus dígitos

José A. Alonso

03-06-2020

Misceláneas

El número 23 se puede escribir de 4 formas como suma de sus dígitos

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

minimoSumandosDigitos        :: Integer -> Integer
graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

(minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

minimoSumandosDigitos 23    ==  8
minimoSumandosDigitos 232   ==  78
minimoSumandosDigitos 2323  ==  775
map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

(graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Número como suma de sus dígitos

Cambio con el menor número de monedas

José A. Alonso

02-06-2020

Misceláneas

La sucesión ECG

José A. Alonso

01-06-2020

Misceláneas

La sucesión ECG estás definida por a(1) = 1, a(2) = 2 y, para n >= 3, a(n) es el menor natural que aún no está en la sucesión tal que a(n) tiene algún divisor común con a(n-1).

Los primeros términos de la sucesión son 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

Al dibujar su gráfica, se parece a la de los electrocardiogramas (abreviadamente, ECG). Por ello, la sucesión se conoce como la sucesión ECG.

Definir las funciones

sucECG :: [Integer]
graficaSucECG :: Int -> IO ()

tales que

sucECG es la lista de los términos de la sucesión ECG. Por ejemplo,

λ> take 20 sucECG
[1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11]
λ> sucECG !! 6000
6237

(graficaSucECG n) dibuja la gráfica de los n primeros términos de la sucesión ECG. Por ejemplo, (graficaSucECG 160) dibuja

La sucesión ECG

Operaciones con series de potencias

José A. Alonso

29-05-2020

Misceláneas

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Caminos en un grafo

José A. Alonso

28-05-2020

Misceláneas

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

(grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

(caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Sin ceros consecutivos

José A. Alonso

27-05-2020

Misceláneas

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

ghci> sinDobleCero 2
[[1,0],[1,1],[0,1]]
ghci> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
ghci> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

Sucesión duplicadora

José A. Alonso

26-05-2020

Misceláneas

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

 3 = 2*1 +1
 6 = 2*3
13 = 2*6 +1

Definir la función

duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

duplicadora 13                   ==  [1,3,6,13]
duplicadora 17                   ==  [1,2,4,8,17]
length (duplicadora (10^40000))  ==  132878

Cadenas de primos complementarios

José A. Alonso

25-05-2020

Misceláneas

El complemento de un número positivo x se calcula por el siguiente procedimiento:

si x es mayor que 9, se toma cada dígito por su valor posicional y se resta del mayor los otro dígitos. Por ejemplo, el complemento de 1448 es 1000 - 400 - 40 - 8 = 552. Para
si x es menor que 10, su complemento es x.

Definir las funciones

cadena    :: Integer -> [Integer]
conCadena :: Int -> [Integer]

tales que

(cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,

cadena 8         == []
cadena 7         == [7]
cadena 13        == [13,7]
cadena 643       == [643,557,443]
cadena 18127     == [18127,1873,127,73,67,53,47]
cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]

(conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,

take 6 (conCadena 3)                == [23,31,61,67,103,307]
[head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]

Las sucesiones de Loomis

José A. Alonso

22-05-2020

Misceláneas

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

f(0) es x
f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...
Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, ...
Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

la generada por 2 converge a 2
la generada por 3 converge a 26
la generada por 4 converge a 4
la generada por 5 converge a 26

Definir las siguientes funciones

omis           :: Integer -> [Integer]
rgencia        :: Integer -> Integer
caConvergencia :: [Integer] -> IO ()

 que

cLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

λ> take 15 (sucLoomis 1)
[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 2)
[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 3)
[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 4)
[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
λ> take 15 (sucLoomis 5)
[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 20)
[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
λ> take 15 (sucLoomis 100)
[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
λ> sucLoomis 1 !! (2*10^5)
235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

convergencia  2      ==  2
convergencia  3      ==  26
convergencia  4      ==  4
convergencia 17      ==  38
convergencia 19      ==  102
convergencia 43      ==  162
convergencia 27      ==  202
convergencia 58      ==  474
convergencia 63      ==  150056
convergencia 81      ==  150056
convergencia 89      ==  150056
convergencia (10^12) ==  1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Espacio de estados del problema de las N reinas

José A. Alonso

21-05-2020

Misceláneas

El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es

|---|---|---|---|
|   | R |   |   |
|---|---|---|---|
|   |   |   | R |
|---|---|---|---|
| R |   |   |   |
|---|---|---|---|
|   |   | R |   |
|---|---|---|---|

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

arbolReinas :: Int -> Tree [Int]
nEstados    :: Int -> Int
soluciones  :: Int -> [[Int]]
nSoluciones :: Int -> Int

tales que

(arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolReinas 4)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |
|  `- [4,1]
|     |
|     `- [2,4,1]
|
+- [2]
|  |
|  `- [4,2]
|     |
|     `- [1,4,2]
|        |
|        `- [3,1,4,2]
|
+- [3]
|  |
|  `- [1,3]
|     |
|     `- [4,1,3]
|        |
|        `- [2,4,1,3]
|
`- [4]
   |
   +- [1,4]
   |  |
   |  `- [3,1,4]
   |
   `- [2,4]

λ> putStrLn (drawTree (fmap show (arbolReinas 5)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |  |
|  |  `- [5,3,1]
|  |     |
|  |     `- [2,5,3,1]
|  |        |
|  |        `- [4,2,5,3,1]
|  |
|  +- [4,1]
|  |  |
|  |  `- [2,4,1]
|  |     |
|  |     `- [5,2,4,1]
|  |        |
|  |        `- [3,5,2,4,1]
|  |
|  `- [5,1]
|     |
|     `- [2,5,1]
|
+- [2]
|  |
|  +- [4,2]
|  |  |
|  |  `- [1,4,2]
|  |     |
|  |     `- [3,1,4,2]
|  |        |
|  |        `- [5,3,1,4,2]
|  |
|  `- [5,2]
|     |
|     +- [1,5,2]
|     |  |
|     |  `- [4,1,5,2]
|     |
|     `- [3,5,2]
|        |
|        `- [1,3,5,2]
|           |
|           `- [4,1,3,5,2]
|
+- [3]
|  |
|  +- [1,3]
|  |  |
|  |  `- [4,1,3]
|  |     |
|  |     `- [2,4,1,3]
|  |        |
|  |        `- [5,2,4,1,3]
|  |
|  `- [5,3]
|     |
|     `- [2,5,3]
|        |
|        `- [4,2,5,3]
|           |
|           `- [1,4,2,5,3]
|
+- [4]
|  |
|  +- [1,4]
|  |  |
|  |  +- [3,1,4]
|  |  |  |
|  |  |  `- [5,3,1,4]
|  |  |     |
|  |  |     `- [2,5,3,1,4]
|  |  |
|  |  `- [5,1,4]
|  |     |
|  |     `- [2,5,1,4]
|  |
|  `- [2,4]
|     |
|     `- [5,2,4]
|        |
|        `- [3,5,2,4]
|           |
|           `- [1,3,5,2,4]
|
`- [5]
   |
   +- [1,5]
   |  |
   |  `- [4,1,5]
   |
   +- [2,5]
   |  |
   |  `- [4,2,5]
   |     |
   |     `- [1,4,2,5]
   |        |
   |        `- [3,1,4,2,5]
   |
   `- [3,5]
      |
      `- [1,3,5]
         |
         `- [4,1,3,5]
            |
            `- [2,4,1,3,5]

(nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,

nEstados 4            ==  17
nEstados 5            ==  54
map nEstados [0..10]  ==  [1,2,3,6,17,54,153,552,2057,8394,35539]

(soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,

λ> soluciones 4
[[3,1,4,2],[2,4,1,3]]
λ> soluciones 5
[[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
 [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]

(nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,

nSoluciones 4            ==  2
nSoluciones 5            ==  10
map nSoluciones [0..10]  ==  [1,1,0,0,2,10,4,40,92,352,724]

Codificación de Fibonacci

José A. Alonso

20-05-2020

Misceláneas

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que

n = d(0)*F(2) + d(1)*F(3) +...+ d(k-1)*F(k+1)
d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y

1*F(2) + 0*F(3) + 1*F(4) = 1*1 + 0*2 + 1*3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

 1  = 1     = F(2)           ≡       11
 2  = 2     = F(3)           ≡      011
 3  = 3     = F(4)           ≡     0011
 4  = 1+3   = F(2)+F(4)      ≡     1011
 5  = 5     = F(5)           ≡    00011
 6  = 1+5   = F(2)+F(5)      ≡    10011
 7  = 2+5   = F(3)+F(5)      ≡    01011
 8  = 8     = F(6)           ≡   000011
 9  = 1+8   = F(2)+F(6)      ≡   100011
10  = 2+8   = F(3)+F(6)      ≡   010011
11  = 3+8   = F(4)+F(6)      ≡   001011
12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
13  = 13    = F(7)           ≡  0000011
14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

λ> codigoFib 65
"0100100011"
λ> [codigoFib n | n <- [1..7]]
["11","011","0011","1011","00011","10011","01011"]

Números de Perrin

José A. Alonso

19-05-2020

Misceláneas

Los números de Perrin se definen por la elación de recurrencia

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

con los valores iniciales

P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

sucPerrin :: [Integer]

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

λ> take 15 sucPerrin
[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
λ> length (show (sucPerrin !! (2*10^5)))
24425

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Diccionario de frecuencias

José A. Alonso

18-05-2020

Misceláneas

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

Operaciones con polinomios como diccionarios

José A. Alonso

15-05-2020

Misceláneas

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

3 + 7x - 5x^3
4 + 5x^3 + x^5

se definen por

ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

(sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]

(multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,

λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]

(multPol p q) es el producto de los polinomios p y q. Por ejemplo,

λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Cadenas de divisores

José A. Alonso

14-05-2020

Misceláneas

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

λ> cadenasDivisores 12
[[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
λ> length (cadenaDivisores 48)
48
λ> length (cadenaDivisores 120)
132

Sucesión fractal

José A. Alonso

13-05-2020

Misceláneas

La sucesión fractal

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2,
10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

los términos pares forman la sucesión de los números naturales

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

los términos impares forman la misma sucesión original

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

sucFractal     :: [Integer]
sumaSucFractal :: Integer -> Integer

tales que

sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
sucFractal !! 30     == 15
sucFractal !! (10^7) == 5000000

(sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

sumaSucFractal 10      == 13
sumaSucFractal (10^5)  == 1666617368
sumaSucFractal (10^10) == 16666666661668691669
sumaSucFractal (10^15) == 166666666666666166673722792954
sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
length (show (sumaSucFractal (10^15000))) == 30000
sumaSucFractal (10^15000) `mod` (10^9)    == 455972157