Ir al contenido principal

Ternas pitagóricas con suma dada

Una terna pitagórica es una terna de números naturales \((a,b,c)\) tal que \(a<b<c\) y \(a^2+b^2=c^2\). Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

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

tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

ternasPitagoricas 12     == [(3,4,5)]
ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Leer más…

Suma de múltiplos de 3 o de 5

Los números naturales menores que 10 que son múltiplos de 3 ó 5 son 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Definir la función

sumaMultiplos :: Integer -> Integer

tal que (sumaMultiplos n) es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

sumaMultiplos 10      ==  23
sumaMultiplos (10^2)  ==  2318
sumaMultiplos (10^3)  ==  233168
sumaMultiplos (10^4)  ==  23331668
sumaMultiplos (10^5)  ==  2333316668
sumaMultiplos (10^6)  ==  233333166668
sumaMultiplos (10^7)  ==  23333331666668

Leer más…

Exponente en la factorización

Definir la función

   exponente :: Integer -> Integer -> Int

tal que (exponente x n) es el exponente de x en la factorización prima de n (se supone que x > 1 y n > 0). Por ejemplo,

   exponente 2 24  ==  3
   exponente 3 24  ==  1
   exponente 6 24  ==  0
   exponente 7 24  ==  0

Leer más…

Número de ocurrencias de elementos

Definir la función

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

tal que (ocurrencias xs) es el conjunto de los elementos de xs junto con sus números de ocurrencias. Por ejemplo,

   ocurrenciasElementos [3,2,3,1,2,3,5,3] == [(3,4),(2,2),(1,1),(5,1)]
   ocurrenciasElementos "tictac"          == [('t',2),('i',1),('c',2),('a',1)]

Leer más…

Reconocimiento de potencias de 4

Definir la función

   esPotenciaDe4 :: Integral a => a -> Bool

tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,

   esPotenciaDe4 16                ==  True
   esPotenciaDe4 17                ==  False
   esPotenciaDe4 (4^(4*10^5))      ==  True
   esPotenciaDe4 (1 + 4^(4*10^5))  ==  False

Leer más…

Producto de los elementos de la diagonal principal

Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

   productoDiagonalPrincipal :: Num a => [[a]] -> a

tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,

   productoDiagonal [[3,5,2],[4,7,1],[6,9,8]]  ==  168
   productoDiagonal (replicate 5 [1..5])       ==  120
   length (show (productoDiagonal (replicate 30000 [1..30000])))  ==  121288

Leer más…

Reiteración de suma de consecutivos

La reiteración de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama

   1 + 5 = 6
             \
              ==> 14
             /
   5 + 3 = 8

y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama

   1 + 5 = 6
             \
              ==> 14
             /       \
   5 + 3 = 8          ==> 29
             \       /
              ==> 15
             /
   3 + 4 = 7

Definir la función

   sumaReiterada :: Num a => [a] -> a

tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vacía xs. Por ejemplo,

   sumaReiterada [1,5,3]    ==  14
   sumaReiterada [1,5,3,4]  ==  29

Leer más…

Anagramas


Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, "mora" y "roma" son anagramas de "amor".

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.


Leer más…

Suma fila del triángulo de los impares

Se considera el siguiente triángulo de números impares

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29
...

Definir la función

   sumaFilaTrianguloImpares :: Integer -> Integer

tal que (sumaFilaTrianguloImpares n) es la suma de la n-ésima fila del triángulo de los números impares. Por ejemplo,

   sumaFilaTrianguloImpares 1  ==  1
   sumaFilaTrianguloImpares 2  ==  8
   length (show (sumaFilaTrianguloImpares (10^500)))    ==  1501
   length (show (sumaFilaTrianguloImpares (10^5000)))   ==  15001
   length (show (sumaFilaTrianguloImpares (10^50000)))  ==  150001

Leer más…

Duplicación de cada elemento


Definir la función

duplicaElementos :: [a] -> [a]

tal que (duplicaElementos xs) es la lista obtenida duplicando cada elemento de xs. Por ejemplo,

duplicaElementos [3,2,5]    ==  [3,3,2,2,5,5]
duplicaElementos "Haskell"  ==  "HHaasskkeellll"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Sistema factorádico de numeración


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

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

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

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

Definir las funciones

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

tales que

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

Comprobar con QuickCheck que, para cualquier entero positivo n,

factoradicoAdecimal (decimalAfactoradico n) == n

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Suma de cadenas


Definir la función

sumaCadenas :: String -> String -> String

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

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

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Cuadrado más cercano


Definir la función

cuadradoCercano :: Integer -> Integer

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

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

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Sucesiones conteniendo al producto de consecutivos

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

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

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

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

Definir la función

   sucesion :: Integer -> [Integer]

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

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

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


Leer más…

Números superabundantes

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

Sea n un número entero positivo. Sea σ(n) la suma de los divisores positivos de n (incluyendo al 1 y al n). Se dice que un entero m ≥ 1 es superabundante (P. Erdös, 1944) si ∀k ∈ {1, 2, ..., m-1}, σ(m)/m > σ(k)/k. Demostrar que esisten infinitos números superabundantes.

Definir la lista

   superabundantes :: [Integer]

cuyos elementos son los números superabundantes. Por ejemplo,

   take 7 superabundantes == [1,2,4,6,12,24,36]
   superabundantes !! 25  ==  166320

Leer más…

Máximo valor de permutaciones

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

Calcular una permutación (a(1),...,a(n)) de {1,2,...,n} que maximice el valor de

a(1)a(2) + a(2)a(3) + ··· + a(n)a(1)

Definir la función

   maximoValorPermutaciones :: Integer -> Integer

tal que (maximoValorPermutaciones n) es el máximo valor de

   a(1)a(2) + a(2)a(3) + ··· + a(n)a(1)

para todas las permutaciones (a(1),...,a(n)) de {1,2,...,n}. Por ejemplo,

   maximoValorPermutaciones 4       ==  25
   maximoValorPermutaciones (10^7)  ==  333333383333315000003
   maximoValorPermutaciones (10^8)  ==  333333338333333150000003
   maximoValorPermutaciones (10^9)  ==  333333333833333331500000003
   length (show (maximoValorPermutaciones (10^1000)))  ==  3000
   length (show (maximoValorPermutaciones (10^2000)))  ==  6000
   length (show (maximoValorPermutaciones (10^3000)))  ==  9000

Comprobar con QuickCheck que, para todo entero positivo n y toda permutación (a(1),...,a(n)) de {1,2,...,n},

   maximoValorPermutaciones n >= a(1)a(2) + a(2)a(3) + ··· + a(n)a(1)

Leer más…

Máxima suma de dos cuadrados condicionados

El enunciado del problema 3 de la IMO (Olimpiada Internacional de Matemáticas) de 1981 es

Calcular el máximo valor de m² + n² donde m y n son números enteros tales que m, n ∈ {1, 2, ..., 1981} y (n² - mn - m²)² = 1.

Definir la función

   maximoValor :: Integer -> Integer

tal que (maximoValor k) es el máximo valor de m² + n² donde m y n son números enteros tales que m, n ∈ {1, 2, ..., k} y (n² - mn - m²)² = 1. Por ejemplo,

   maximoValor 10       ==  89
   maximoValor (10^20)  ==  9663391306290450775010025392525829059713
   length (show (maximoValor (10^(4*10^4))))  ==  80000

Usando la función maximoValor, calcular la respuesta del problema.


Leer más…

Productos de sumas de progresiones aritméticas

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

Para cada número entero d ≥ 1, sea M(d) el conjunto de todos enteros positivos que no se pueden escribir como una suma de una progresión aritmética de diferencia d, teniendo al menos dos sumandos y formadas por enteros positivos. Sean A = M(1), B = M(2)-{2} y C = M(3). Demostrar que todo c ∈ C se puede escribir de una única manera como c = ab con a ∈ A, b ∈ B.

Definir las funciones

   conjuntoA   :: [Integer]
   conjuntoB   :: [Integer]
   conjuntoC   :: [Integer]
   productosAB :: Integer -> [(Integer,Integer)]

tales que

  • conjuntoA es la lista de los elementos del conjunto A; es decir, de los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia uno, con al menos dos términos, de números enteros positivos. Por ejemplo,
     conjuntoA !! 2                      ==  4
     length (show (conjuntoA !! (10^7))) == 3010300
  • conjuntoB es la lista de los elementos del conjunto B; es decir, los números (distintos de dos) que no se pueden escribir como sumas de progresiones aritméticas de diferencia dos, con al menos dos términos, de números enteros positivos. Por ejemplo,
     conjuntoB !! 3       ==  5
     conjuntoB !! (10^6)  ==  15485863
  • conjuntoC es la lista de los elementos del conjunto C; es decir, los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia tres, con al menos dos términos, de números enteros positivos. Por ejemplo,
     conjuntoC !! 4  ==  6
  • (productosAB x) es la lista de los pares (a,b) tales que a es un elementos del conjunto A, b es un elemento del conjunto B y su producto es x. Por ejemplo,
     productosAB 10  ==  [(2,5)]
     productosAB 15  ==  []

Comprobar con QuickCheck la propiedad del problema de la Olimpiada; es decir, para todo c ∈ C la lista (productosAB c) tiene exactamente un elemento.


Leer más…

Números que no son sumas de progresiones aritméticas de diferencia dada

El número 5 es la suma de números enteros positivos en progresión aritmética de diferencia tres (ya que es 1+4) y también lo es el 7 (ya que es 2+5) y el 12 (ya que es (1+4+7), pero el 6 no lo es.

Definir la función

   noSonSumasDePADeDiferencia :: Integer -> [Integer]

tal que (noSonSumasDePADeDiferencia d) es la lista de los números no se pueden escribir como sumas de progresiones aritméticas de diferencia d, con al menos términos, de números enteros positivos. Por ejemplo,

   (noSonSumasDePADeDiferencia 3) !! 4    ==  6
   (noSonSumasDePADeDiferencia 3) !! 100  ==  6848
   (noSonSumasDePADeDiferencia 9) !! 200  ==  6752

Leer más…

Números que no son sumas de progresiones aritméticas de diferencia dos

El número 4 es la suma de números enteros positivos en progresión aritmética de diferencia dos (ya que es 1+3) y también lo es el 6 (ya que es 2+4) y el 9 (ya que es (1+3+5), pero el 5 no lo es.

Definir la función

   noSonSumasDePADeDiferenciaDos :: [Integer]

cuyos elementos son los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia dos, con al menos dos términos, de números enteros positivos. Por ejemplo,

   noSonSumasDePADeDiferenciaDos !! 3  ==  5
   noSonSumasDePADeDiferenciaDos !! (10^6)  ==  15485863

Leer más…

Números que no son sumas de progresiones aritméticas de diferencia uno

El número 3 es la suma de números enteros positivos en progresión aritmética de diferencia uno (ya que es 1+2) y también lo es el 5 (ya que es 2+3) y el 6 (ya que es (1+2+3), pero el 4 no lo es.

Definir la función

   noSonSumasDePADeDiferenciaUno :: [Integer]

cuyos elementos son los números que no se pueden escribir como de progresiones aritméticas de diferencia uno, con al menos dos términos, de números enteros positivos. Por ejemplo,

   noSonSumasDePADeDiferenciaUno !! 2  ==  4
   length (show (noSonSumasDePADeDiferenciaUno !! (10^7))) == 3010300

Leer más…

Productos de elementos de dos conjuntos

Definir la función

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

tal que (productos as bs c) es la lista de pares (a,b) tales que a un elementos de as, b es un elemento de bs y su producto es x, donde as y bs son listas (posiblemente infinitas) ordenadas crecientes. Por ejemplo,

   productos [3,5..] [2,4..] 2000  ==  [(5,400),(25,80),(125,16)]
   productos [3,5..] [2,4..] 2001  ==  []
   length (productos [3,5..] [2,4..] (product [1..11]))  ==  59

Leer más…

Potencias con mismos finales

El enunciado del primer problema de la IMO (Olimpiada Internacional de Matemáticas) de 1978 es

Sean n > m ≥ 1 números naturales tales que los 3 últimos dígitos de 1978^m y 1978^n coinciden. Calcular el par (m,n) de dichos pares para el que m+n es mínimo.

Definir la función

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

tal que (potenciasMismoFinales x) es la lista de los pares de naturales (m,n) tales que n > m ≥ 1 y los 3 últimos dígitos de x^m y x^n coinciden (además, la lista está ordenada por la suma de las componentes de sus elementos). Por ejemplo,

   take 3 (potenciasMismoFinales 1001) == [(1,2),(1,3),(1,4)]
   take 3 (potenciasMismoFinales 1002) == [(3,103),(4,104),(5,105)]
   take 3 (potenciasMismoFinales 1003) == [(1,101),(2,102),(3,103)]
   take 3 (potenciasMismoFinales 1004) == [(2,52),(3,53),(4,54)]
   take 3 (potenciasMismoFinales 1005) == [(3,5),(3,7),(4,6)]
   take 3 (potenciasMismoFinales 1006) == [(3,28),(4,29),(5,30)]
   take 3 (potenciasMismoFinales 1007) == [(1,21),(2,22),(3,23)]
   take 3 (potenciasMismoFinales 1008) == [(1,101),(2,102),(3,103)]
   take 3 (potenciasMismoFinales 1009) == [(1,51),(2,52),(3,53)]

Usando la función potenciasMismoFinales, calcular la respuesta al problema de la Olimpiada.


Leer más…

Mayor producto con sumandos de la descomposición

El enunciado del 4º problema para la IMO (Olimpiada Internacional de Matemáticas) de 1976 es

Calcular el mayor número que se puede obtener multiplicando los enteros positivos cuya suma es 1976.

Definir la función

   mayorProductoSumandos :: Integer -> Integer

tal que (mayorProductoSumandos n) el mayor número que se puede obtener multiplicando los enteros positivos cuya suma es n. Por ejemplo,

   mayorProductoSumandos 5 == 6

ya que los posibles listas de sumandos con suma 5 son

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

sus productos son

   5,   6,     4,     4,       3,       2,         1

y el mayor de dichos productos es 6.

Otros ejemplos son

   mayorProductoSumandos 10   ==  36
   mayorProductoSumandos 100  ==  7412080755407364
   length (show (mayorProductoSumandos (10^8)))  ==  15904042

Usando la función mayorProductoSumandos, calcular la respuesta al problema de la Olimpiada.


Leer más…

Multiplos sin ceros

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

Demostrar que cada n ≢ 0 (mod 10) posee algún múltiplo sin el dígito 0.

Definir la función

   multiplosSinCeros :: Integer -> [Integer]

tal que (multiplosSinCeros n) es la lista de los múltiplos de n sin el dígito 0. Por ejemplo,

   λ> take 10 (multiplosSinCeros 101)
   [1111,1212,1313,1414,1515,1616,1717,1818,1919,2121]

Comprobar con QuickCheck que si n es un número entero positivo no divisible por 10, entonces n posee algún múltiplo sin el dígito 0.


Leer más…

Sumas con signos

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

Sean x1, x2, x3, x4, x5, x6 enteros no divisibles por 7. Demostrar que alguna de las sumas ±x1 ± x2 ± x3 ± x4 ± x5 ± x6 es divisible por 7, donde los signos se seleccionan de todas las manera posibles. (Generalizar la propiedad para todos los primos).

Definir la función

   sumas :: [Integer] -> [Integer]

tal que (sumas xs) es la lista de los valores de las sumas

   ±x(1) ± x(2) ± ··· ± x(n)

donde [x(1),x(2),...,x(n)] = xs y los signos se seleccionan de todas las manera posibles. Por ejemplo,

   sort (sumas [3])      ==  [-3,3]
   sort (sumas [2,3])    ==  [-5,-1,1,5]
   sort (sumas [1,2,3])  ==  [-6,-4,-2,0,2,4,6]

Comprobar con QuickCheck que para todo número primo impar p y toda lista xs de longitud (p-1) de elementos no divisibles por p se verifica que la lista (sumas xs) tiene algún elemento divisible por p.


Leer más…

Números divisibles respecto de una sucesión

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

Sean a(0), a(1), ..., a(n) (con n ≥ 1) números enteros positivos. Encontrar todos los números enteros y tales que

a(0) | y; (a(0)+a(1)) | (y+a(1)); ... ; (a(0)+a(n)) | (y+a(n)).

donde "x | y" significa que "y es divisible por x".

Se dice que un número y es divisible respecto de la sucesión a(0), a(1), ..., a(n) si verifica la propiedad anterior; es decir,

      a(0) | y; (a(0)+a(1)) | (y+a(1)); ... ; (a(0)+a(n)) | (y+a(n)).

Definir la función

   divisiblesSucesion :: [Integer] -> [Integer]

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

   take 6 (divisiblesSucesion [2,5,3])     ==  [2,72,142,212,282,352]
   divisiblesSucesion [3,5..30] !! (10^5)  ==  144144000003
   divisiblesSucesion [3,5..30] !! (10^6)  ==  1441440000003
   divisiblesSucesion [3,5..30] !! (10^7)  ==  14414400000003

Leer más…

Descomposiciones como sumas de consecutivos

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

  • (a) Calcular el número de maneras de expresar 500 como suma de números naturales consecutivos.
  • (b) Calcular el número de tales representaciones para n = 2^x·3^y·5^z, con x, y, z ∈ ℕ. ¿Cuántas de ellas están formadas por un único elemento?
  • (c) Calcular el número de tales representaciones para un número natural n.

Definir las funciones

   consecutivosConSuma    :: Integer -> [(Integer,Integer)]
   nDeConsecutivosConSuma :: Integer -> Integer

tales que

  • (consecutivosConSuma n) es la lista de los extremos de las sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
     consecutivosConSuma 3  ==  [(0,2),(1,2),(3,3)]
     consecutivosConSuma 4  ==  [(4,4)]
     consecutivosConSuma 5  ==  [(2,3),(5,5)]
     consecutivosConSuma 6  ==  [(0,3),(1,3),(6,6)]
     consecutivosConSuma 15 ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
     maximum [length (consecutivosConSuma n) | n <- [1..1000]] == 16
  • (nDeConsecutivosConSuma n) es la cantidad de sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
     nDeConsecutivosConSuma 3  ==  3
     nDeConsecutivosConSuma 4  ==  1
     nDeConsecutivosConSuma 5  ==  2
     nDeConsecutivosConSuma 6  ==  3
     nDeConsecutivosConSuma 15 ==  5
     maximum [nDeConsecutivosConSuma n | n <- [1..10^5]] == 49
     nDeConsecutivosConSuma (product [1..17])            == 672

Usando las funciones anteriores, calcular las respuestas del problema de la Olimpiada.


Leer más…

El cociente por 11 es igual a la suma de los cuadrados de sus cifras

El enunciado del problema 1 de la Olimpiada Internacional de Matemáticas de 1960 es el siguiente

Encontrar todos los números de tres cifras para los que al dividir el número entre 11 se obtiene la suma de los cuadrados de las cifras del número inicial.

Diremos que un número x es especial si al dividir x entre 11 se obtiene la suma de los cuadrados de las cifras de x.

Definir la función

   esEspecial :: Integer -> Bool

tal que (esEspecial x) se verifica si x es especial. Por ejemplo,

   esEspecial 550          ==  True
   esEspecial 22           ==  False
   esEspecial 241          ==  False
   esEspecial (11^(10^8))  ==  False

Usando la función esEspecial, calcular la respuesta al problema de la Olimpiada.

Calculando los números especiales menores que 10⁶, conjeturar que el conjunto de los números especiales es finito y comprobar la conjetura con QuickCheck.


Leer más…

Últimos dígitos de una sucesión

El enunciado del problema 1 de la Fase Local de la Olimpiada Matemática Española del 2000 es

Considérese la sucesión definida como a(1) = 3, y a(n+1) = a(n) + a(n)². Determínense las dos últimas cifras de a(2000).

Definir las sucesiones

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

tales que

  • sucesionA es la lista de los términos de la sucesión a(n). Por ejemplo,
     take 4 sucesionA  ==  [3,12,156,24492]
  • sucesionB es la lista de los dos últimos dígitos de los término de la sucesión a(n). Por ejemplo,
     take 4 sucesionB     ==  [3,12,56,92]
     sucesionB !! (10^6)  ==  56

Usando la sucesionB, calcular la respuesta a la pregunta del problema de la Olimpiada.


Leer más…

Sumas y productos de dígitos

El enunciado de un problema 3 de la Fase Local de la Olimpiada Matemática Española del 2000 es

¿Cuántos números, comprendidos entre 1.000 y 9.999, verifican que la suma de sus cuatro dígitos es mayor o igual que el producto de los mismos? ¿Para cuántos de ellos se verifica la igualdad?

Definir las funciones

   conMayorSumaQueProducto :: Int -> Int -> [Int]
   conIgualSumaQueProducto :: Int -> Int -> [Int]

tales que

  • (conMayorSumaQueProducto a b) es la lista de los números del intervalo [a,b] tales que la suma de sus dígitos es mayor o igual que el producto de los mismos. Por ejemplo,
     λ> conMayorSumaQueProducto 20 99
     [20,21,30,31,40,41,50,51,60,61,70,71,80,81,90,91]
     λ> conMayorSumaQueProducto 120 199
     [120,121,122,130,131,140,141,150,151,160,161,170,171,180,181,190,191]
     λ> conMayorSumaQueProducto 220 299
     [220,221,230,240,250,260,270,280,290]
  • (conIgualSumaQueProducto a b) es la lista de los números del intervalo [a,b] tales que la suma de sus dígitos es igual que el producto de los mismos. Por ejemplo,
     λ> conIgualSumaQueProducto 10 99
     [22]
     λ> conIgualSumaQueProducto 100 999
     [123,132,213,231,312,321]

Usando las funciones anteriores, calcular las respuestas a las preguntas del problema de la Olimpiada.


Leer más…

Números suma de dos cuadrados

El enunciado de un problema 3.3 de la Fase Local de la Olimpiada Matemática Española del 2004 es

Hallad todas las posibles formas de escribir 2003 como suma de dos cuadrados de números enteros positivos.

Definir la sucesión

   sonSumaDosCuadrados :: [Integer]

cuyos elementos son los números que se pueden expresar como suma de los cuadrados de dos números naturales. Por ejemplo,

   take 6 sonSumaDosCuadrados      ==  [0,1,2,4,5,8]
   sonSumaDosCuadrados !! (10^4)   ==  39593

Comprobar con QuickCheck las siguientes propiedades:

  • La sucesión sonSumaDosCuadrados es infinita.
  • Los elementos de sonSumaDosCuadrados no son congruentes con 3 módulo 4 (es decir, sus restos al dividirlo por 4 son distintos de 3).

Usando sonSumaDosCuadrados, resolver el problema propuesto; es decir, calcular todas las posibles formas de escribir 2003 como suma de dos cuadrados de números enteros positivos.


Leer más…

Ternas aditivas

El enunciado del problema C6 de la Fase Local de la Olimpiada Matemática Española del 2006 es

Decimos que tres números naturales distintos forman una terna aditiva si la suma de los dos primeros de ellos es igual al tercero. Hallar, razonadamente, el máximo número de ternas aditivas que puede haber en un conjunto dado de 20 números naturales.

Definir las funciones

   ternasAditivas  :: Integer -> [(Integer,Integer,Integer)]
   nTernasAditivas :: Integer -> Integer

tales que

  • (ternasAditivas n) es la lista de las ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     λ> ternasAditivas 7
     [(1,2,3),(1,3,4),(1,4,5),(1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7),(3,4,7)]
     λ> length (ternasAditivas (10^4))
     24995000
  • (nTernasAditivas n) es el número de ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     nTernasAditivas 7                            ==  9
     length (show (nTernasAditivas (10^(10^5))))  ==  200000
     length (show (nTernasAditivas (10^(10^6))))  ==  2000000
     length (show (nTernasAditivas (10^(10^7))))  ==  20000000

Leer más…

Cuadrado más primo

El enunciado del problema C2 de la Fase Local de la Olimpiada Matemática Española del 2006 es

¿Existe un conjunto infinito de números naturales que NO se pueden representar en la forma n³+p, siendo n natural y p primo? Razónese la contestación.

Definir la lista

   noSonCuadradoMasPrimo :: [Integer]

cuyos elementos son los números que no se pueden escribir como un cuadrado más un primo. Por ejemplo,

   λ> take 15 noSonCuadradoMasPrimo
   [1,10,25,34,58,64,85,91,121,130,169,196,214,226,289]
   λ> noSonCuadradoMasPrimo2 !! 200
   78961

En la lista no está el 2 (porque 2 = 0²+2), el 3 (porque 3 = 1²+2), el 4 (porque 4 = 0²+4) ni el 11 (porque 11 = 3²+2).

Comprobar con QuickCheck que noSonCuadradoMasPrimo es infinita.


Leer más…

Números consecutivos con factorización con exponentes impares

El enunciado del problema B.5 de la Fase Local de la Olimpiada Matemática Española del 2006 es

Los números naturales 22, 23, y 24 tienen la siguiente propiedad: los exponentes de los factores primos de su descomposición son todos impares (22 = 2¹·11¹, 23 = 23¹, 24 = 2³·3¹)

¿Cuál es el mayor número de naturales consecutivos que pueden tener esa propiedad?. Razónese la contestación.

Definir la lista

   consecutivosExponentesImpares :: [[Integer]]

cuyos elementos sean las sucesiones maximales de números enteros positivos tales que los exponentes de los factores primos de su descomposición son todos impares. Por ejemplo,

   λ> take 7 consecutivosExponentesImpares
   [[1,2,3],[5,6,7,8],[10,11],[13,14,15],[17],[19],[21,22,23,24]]
   λ> consecutivosExponentesImpares !! (10^4)
   [43030,43031,43032,43033,43034,43035]

Usando la función consecutivosExponentesImpares conjeturar la respuesta a la pregunta del problema y comprobarla con QuickCheck.


Leer más…

Sucesión de mcd de consecutivos

El enunciado de un problema B3 de la Fase Local de la Olimpiada Matemática Española del 2007 es

Sea a(n) = 1 + n³ la sucesión {2,9,28,65,...} y b(n) = mcd(a(n),a(n+1)). Hallar el máximo valor que puede tomar b(n).

Definir las listas

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

tales que

  • los elementos de sucesionA son los términos de la sucesión a(n). Por ejemplo,
     take 12 sucesionA  ==  [2,9,28,65,126,217,344,513,730,1001,1332,1729]
  • los elementos de sucesionAB son los términos de la sucesión b(n). Por ejemplo,
   sucesionB !! 0       ==  1
   sucesionB !! 4       ==  7
   sucesionB !! (10^9)  ==  1

Usando sucesionB, conjeturar la respuesta del problema y comprobarla con QuickCheck.


Leer más…

Biparticiones con la misma suma

El enunciado de un problema 1 de la Fase Local de la Olimpiada Matemática Española del 2010 es

Sea I(n) el conjunto de los n primeros números naturales impares. Por ejemplo: I(3) = {1,3,5}, I(6) = {1,3,5,7,9,11}, etc.

¿Para qué números n el conjunto I(n) se puede descomponer en dos partes (disjuntas) de forma que coincidan las sumas de los números en cada una de ellas?

Definir las funciones

   biparticiones :: Integer -> [([Integer],[Integer])]
   tieneBiparticiones :: Integer -> Bool
   biparticionD :: Integer -> Maybe ([Integer],[Integer])

tales que

  • (biparticiones n) es la lista de las biparticiones de I(n) con igual suma; es decir, la lista de los pares (xs,ys) tales que xs e ys son subconjuntos disjuntos de I(n) cuya unión es I(n) y la suma de los elementos de xs es igual que la de los de ys. Por ejemplo,
     λ> biparticiones 4
     [([1,7],[3,5])]
     λ> biparticiones 5
     []
     λ> biparticiones 8
     [([1,3,13,15],[5,7,9,11]),([1,5,11,15],[3,7,9,13]),([1,7,9,15],[3,5,11,13]),([1,7,11,13],[3,5,9,15])]
  • (tieneBiparticiones n) se verifica si I(n) tiene alguna bipartición con igual suma. Por ejemplo,
     tieneBiparticiones 4  ==  True
     tieneBiparticiones 5  ==  False
     tieneBiparticiones (10^(10^7))  ==  True
  • (biparticionD n) es una de las biparticiones de I(n) con igual suma, si tiene alguna y Nothing, en caso contrario. Por ejemplo,
     λ> biparticionD 6
     Just ([7,11],[1,3,5,9])
     λ> biparticionD 7
     Nothing
     λ> biparticionD 8
     Just ([1,7,9,15],[3,5,11,13])
     λ> biparticionD 10
     Just ([7,11,13,19],[1,3,5,9,15,17])
     λ> biparticionD 12
     Just ([1,7,9,15,17,23],[3,5,11,13,19,21])
     λ> biparticionD 30
     Just ([7,11,13,19,21,27,29,35,37,43,45,51,53,59],[1,3,5,9,15,17,23,25,31,33,39,41,47,49,55,57])
     λ> length (show (biparticionD (2*10^4)))
     114455

Usando tieneBiparticiones calcular los 10 primeros valores buscados (es decir, los 10 valores de n para los que I(n) se puede descomponer en dos partes (disjuntas) de forma que coincidan las sumas de los números en cada una de ellas) y generalizar.


Leer más…

Diferencias de potencias congruentes con 5 módulo 7

El enunciado de un problema 5 de la Fase Local de la Olimpiada Matemática Española del 2012 es

Consideremos el número entero positivo

[latex]n = 2^r - 16^s[/latex] donde r y s son también enteros positivos. Hallar las condiciones que deben cumplir r y s para que el resto de la división de n por 7 sea 5. Hallar el menor número que cumple esta condición.

Definir la lista

   exponentes :: [(Integer,Integer)]

tal que sus elementos son los pares de enteros positivos (r,s) tales que [latex]2^r - 16^s[/latex] es un número entero positivo cuyo resto al dividirlo por 7 es 5. Por ejemplo,

   head exponentes       ==  (10,2)
   exponentes !! 23      ==  (43,8)
   exponentes !! (10^7)  ==  (26836,1826)

Usando la función exponentes, calcular la respuesta a la pregunta del problema; es decir, hallar el menor número que cumple la condición.


Leer más…

Suma de no múltiplos

El enunciado de un problema 1 de la Fase Local de la Olimpiada Matemática Española del 2011 es

Dado un entero positivo n, hallar la suma de todos los enteros positivos inferiores a 10n que no son múltiplos de 2 ni de 5.

Definir la función

   suma :: Integer -> Integer

tal que (suma n) es la suma de todos los enteros positivos inferiores a 10n que no son múltiplos de 2 ni de 5. Por ejemplo,

   suma 7  ==  980
   length (show (suma (10^(10^5))))  ==  200002
   length (show (suma (10^(10^6))))  ==  2000002
   length (show (suma (10^(10^7))))  ==  20000002

Leer más…

Suma de serie racional

El enunciado del problema 6 de la Fase Local de la Olimpiada Matemática Española del 2020 es

Sea n un entero positivo. Calcular la siguiente suma

         3           4           5                    n+2
     --------- + --------- + --------- + ··· + ---------------------
      1·2·4·5     2·3·5·6     3·4·6·7           n·(n+1)·(n+3)·(n+4)

Definir la función

   sumaSerie :: Integer -> Rational

tal que para cada entero positivo n, (sumaSerie n) es el valor de la siguiente sumaSerie

      3           4           5                    n+2
  --------- + --------- + --------- + ··· + ---------------------
   1·2·4·5     2·3·5·6     3·4·6·7           n·(n+1)·(n+3)·(n+4)

Por ejemplo,

   sumaSerie 1        ==  3 % 40
   sumaSerie 2        ==  7 % 72
   sumaSerie 3        ==  3 % 28
   sumaSerie (10^10)  ==  3125000001562500000 % 25000000012500000001

   length (show (sumaSerie (10^10)))      ==  42
   length (show (sumaSerie (10^(10^2))))  ==  402
   length (show (sumaSerie (10^(10^3))))  ==  4002
   length (show (sumaSerie (10^(10^4))))  ==  40002
   length (show (sumaSerie (10^(10^5))))  ==  400002
   length (show (sumaSerie (10^(10^6))))  ==  4000002

Leer más…

Múltiplos persistentes de siete

El enunciado del problema 1 de la Fase Local de la Olimpiada Matemática Española del 2021 es

Determinar todos los números de cuatro cifras tales que al insertar un dígito 0 en cualquier posición se obtiene un múltiplo de 7.

Un número n se dice que es un múltiplo persistente de 7 si al insertar el dígito 0 en cualquier posición de n se obtiene un múltiplo de 7.

Definir las funciones

   esMultiploPersistente :: Integer -> Bool
   multiplosPersistentes :: Int -> [Integer]

tales que

  • (esMultiploPersistente n) se verifica si n es un múltiplo persistente de n. Por ejemplo,
     esMultiploPersistente 7007  ==  True
     esMultiploPersistente 7107  ==  False
  • (multiplosPersistentes k) es la lista de los números con k dígitos que son múltiplos persistentes de 7. Por ejemplo,
     take 2 (multiplosPersistentes 4)   ==  [7000,7007]
     length (multiplosPersistentes 20)  ==  524288

Usando la función multiplosPersistentes, calcular la respuesta al problema de la Olimpiada.


Leer más…

Múltiplos repitunos

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.


Leer más…

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

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

Leer más…

Ordenación de los pares de enteros

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

Leer más…

Órbita con raíz entera

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]

Leer más…

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

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.


Leer más…

Máximos de una función recursiva

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.


Leer más…

Productos de cuatro consecutivos

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.


Leer más…

Mayores potencias de 5 que dividen a la sucesión

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.


Leer más…

Permutaciones divisibles

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

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.


Leer más…

Cuadriseguidos y números encadenados

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.


Leer más…

Árbol de cadenas

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

Leer más…

Sucesión de cubos perfectos

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.


Leer más…

Enlaces primos

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

Leer más…

Raíces digitales de sucesiones de raíces digitales

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

Leer más…

Sucesiones de raices digitales

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.


Leer más…

Raíces digitales de los números de Fibonacci

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

Leer más…

Persistencia aditiva

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

Leer más…

Raíces digitales de potencias de dos

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

Leer más…

Raíz digital

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.

Leer más…

Antiimágenes de funciones crecientes bidimensionales

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

Leer más…

Antiimagen de función creciente

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

Leer más…

Reducción de consecutivos relacionados

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]

Leer más…

Lista muy decreciente

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

Leer más…

Menor prefijo con suma positiva

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

Leer más…

Autonúmeros

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

Leer más…

Sucesiones de sumas digitales

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]

Leer más…

Coste del recorrido ordenado

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

Leer más…

Mínima profundidad

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

Leer más…

Árbol de las divisiones por 2, 3 ó 5

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

Leer más…

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

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 Cálculo de pi mediante la fórmula de Beeler

Leer más…

Números ordenados con cuadrados ordenados

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

Leer más…

Números con cuadrados con dígitos pares

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.


Leer más…

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

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 Bauer

Leer más…

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

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


Leer más…

Representaciones de un número como potencia

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

Leer más…

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

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 fórmula de Brouncker

Leer más…

Cálculo de pi mediante la serie de Madhava

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 Cálculo de pi mediante la serie de Madhava

Leer más…

Sucesión de Rowland

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.


Leer más…

Sumas parciales

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

Leer más…

Siguiente equidigital

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

Leer más…

Suma de la lista reducida

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

Leer más…

Espirales

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]

Leer más…

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

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

Leer más…

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

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

Leer más…

Eliminaciones anotadas

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

Leer más…

Máximo de las rotaciones

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

Leer más…

Particiones por un elemento

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

Leer más…

Sumas de potencias que son cuadrados perfectos

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

Leer más…

Números balanceados

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.


Leer más…

Máximos locales y sus posiciones

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]  ==  []

Leer más…

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

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

Leer más…

Cantidad de números oblongos en un intervalo

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

Leer más…

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

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

Leer más…

Descomposición de N en K sumandos pares distintos

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

Leer más…