Ir al contenido principal

Potencias perfectas

Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son

4 = 2², 8 = 2³, 9 = 3², 16 = 2, 25 = 5², 27 = 3³, 32 = 2,
36 = 6², 49 = 7², 64 = 2, ...

Definir la sucesión

potenciasPerfectas :: [Integer]

cuyos términos son las potencias perfectas. Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 3000  ==  7778521

Definir el procedimiento

grafica :: Int -> IO ()

tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja

Potencias perfectas


Leer más…

Sumas alternas de factoriales

Las primeras sumas alternas de los factoriales son números primos; en efecto,

3! - 2! + 1! = 5
4! - 3! + 2! - 1! = 19
5! - 4! + 3! - 2! + 1! = 101
6! - 5! + 4! - 3! + 2! - 1! = 619
7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899

son primos, pero

9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981

no es primo.

Definir las funciones

sumaAlterna         :: Integer -> Integer
sumasAlternas       :: [Integer]
conSumaAlternaPrima :: [Integer]

tales que

  • (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,
sumaAlterna 3  ==  5
sumaAlterna 4  ==  19
sumaAlterna 5  ==  101
sumaAlterna 6  ==  619
sumaAlterna 7  ==  4421
sumaAlterna 8  ==  35899
sumaAlterna 9  ==  326981
sumaAlterna (5*10^4) `mod` (10^6) == 577019
  • sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,
λ> take 10 sumasAlternas1
[0,1,1,5,19,101,619,4421,35899,326981]
  • conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,
λ> take 8 conSumaAlternaPrima
[3,4,5,6,7,8,10,15]

Leer más…

Primos con cubos

Un primo con cubo es un número primo p para el que existe algún entero positivo n tal que la expresión n^3 + n^2p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8^3 + 8^2×19 = 12^3.

Definir la sucesión

primosConCubos :: [Integer]

tal que sus elementos son los primos con cubo. Por ejemplo,

λ> take 6 primosConCubos
[7,19,37,61,127,271]
λ> length (takeWhile (<1000000) primosConCubos)
173

Leer más…

Primos cubanos

Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.

Definir la sucesión

cubanos :: [Integer]

tal que sus elementos son los números cubanos. Por ejemplo,

λ> take 15 cubanos
[7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]

Leer más…

Clausura transitiva de una relación binaria

La clausura transitiva de una relación binaria R es la relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S: sea

R = [(1,2),(2,5),(5,6)]

la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea

R1 = R  (R  R)
= [(1,2),(2,5),(5,6),(1,5),(2,6)]

la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea

R2 = R1  (R1  R1)
= [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]

La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.

Definir la función

clausuraTransitiva :: Ord a => [(a,a)] -> [(a,a)]

tal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,

λ> clausuraTransitiva [(1,2),(2,5),(5,6)]
[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]
[(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]
λ> length (clausuraTransitiva [(n,n+1) | n <- [1..100]])
5050

Leer más…

Transitividad de una relación

Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.

Definir la función

transitiva :: Ord a => [(a,a)] -> Bool

tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,

transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True
transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False
transitiva [(n,n) | n <- [1..10^4]]         ==  True

Leer más…

Composición de relaciones binarias

Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por

[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]

La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.

Definir la función

composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]

tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,

λ> composicion [(1,2)] [(2,3),(2,4)]
[(1,3),(1,4)]
λ> composicion [(1,2),(5,2)] [(2,3),(2,4)]
[(1,3),(1,4),(5,3),(5,4)]
λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]
[(1,3)]

Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.


Leer más…

Número de particiones en k subconjuntos

Definir la función

numeroParticiones :: Int -> Int -> Int

tal que (numeroParticiones n k) es el número de particiones de conjunto de n elementos en k subconjuntos disjuntos. Por ejemplo,

numeroParticiones 3 2    ==  3
numeroParticiones 3 3    ==  1
numeroParticiones 4 3    ==  6
numeroParticiones 4 1    ==  1
numeroParticiones 4 4    ==  1
numeroParticiones 91 89  ==  8139495

Leer más…

Particiones en k subconjuntos

Definir la función

particiones :: [a] -> Int -> [[[a]]]

tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,

λ> particiones [2,3,6] 2
[[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]]
λ> particiones [2,3,6] 3
[[[2],[3],[6]]]
λ> particiones [4,2,3,6] 3
[[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]],
[[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]]
λ> particiones [4,2,3,6] 1
[[[4,2,3,6]]]
λ> particiones [4,2,3,6] 4
[[[4],[2],[3],[6]]]

Leer más…

Mayor semiprimo menor que n

Un número semiprimo es un número natural es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2·13) y 49 también lo es (porque 49 = 7·7).

Definir la función

mayorSemiprimoMenor :: Integer -> Integer

tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,

mayorSemiprimoMenor 27      ==  26
mayorSemiprimoMenor 50      ==  49
mayorSemiprimoMenor 49      ==  46
mayorSemiprimoMenor (10^15) == 999999999999998

Leer más…