El problema de la particiones óptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partición óptima de xs. Por ejemplo, la partición óptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) - 5| = 0. Una lista puede terner distintas particiones óptimas. Por ejemplo, [1,1,2,3] tiene dos particiones óptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|.

Definir la función

particionesOptimas :: [Int] -> ([Int],[Int])

tal que (particionesOptimas xs) es la lista de las particiones óptimas de xs. Por ejemplo,

particionesOptimas [2,3,5]    ==  [([2,3],[5])]
particionesOptimas [1,1,2,3]  ==  [([1,2],[1,3]),([1,1,2],[3])]
particionesOptimas [5,0,5]    ==  [([0,5],[5])]
particionesOptimas [5,5]      ==  [([5],[5])]
particionesOptimas [5]        ==  [([],[5])]

Leer más…

El teorema de Euclides afirma que existen infinitos números primos. En palabras de Euclides,

"Hay más números primos que cualquier cantidad propuesta de números primos." (Proposición 20 del Libro IX de "Los Elementos").

Su demostración se basa en que si p₁,...,pₙ son los primeros n números primos, entonces entre 1+pₙ y 1+p₁·p₂·...·pₙ hay algún número primo. La cantidad de dichos números primos se llama el n-ésimo hueco de Euclides. Por ejemplo, para n = 3 se tiene que p₁ = 2, p₂ = 3 y p₃ = 5 entre 1+p₃ = 6 y 1+p₁·p₂·p₃ = 31 hay 8 números primos (7, 11, 13, 17, 19, 23, 29 y 31), por lo que el valor del tercer hueco de Euclides es 8.

Definir la función

hueco :: Int -> Integer

tal que (hueco n) es el n-ésimo hueco de Eulides. Por ejemplo,

hueco 3                   ==  8
[hueco n | n <- [1..8]]   ==  [1,2,8,43,339,3242,42324,646021]

Leer más…

Un número de Carol es un número entero de la forma \(4^n-2^{n+1}-1\) o, equivalentemente, \((2^n-1)^2-2\). Los primeros números de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527.

Definir las funciones

carol        :: Integer -> Integer
carolBinario :: Integer -> Integer

tales que

• (carol n) es el n-ésimo número de Carol. Por ejemplo,

carol  3  ==  47
carol  4  ==  223
carol 25  ==  1125899839733759

• (carolBinario n) es la representación binaria del n-ésimo número de Carol. Por ejemplo,

carolBinario 3  ==  101111
carolBinario 4  ==  11011111
carolBinario 5  ==  1110111111

Comprobar con QuickCheck que, para n > 2, la representación binaria del n-ésimo número de Carol es el número formado por n-2 veces el dígito 1, seguido por un 0 y a continuación n+1 veces el dígito 1.

Leer más…

Se considera el siguiente par de operaciones sobre los números:

• multiplicar por dos
• restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

4 ------> 8 ------> 7
   (x2)      (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

2 ------> 4 ------> 3 ------> 6 ------> 5
   (x2)      (-1)      (x2)      (-1)

Definir las siguientes funciones

arbolOp :: Int -> Int -> Arbol
minNOp  :: Int -> Int -> Int

tales que

• (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))

• (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

minNOp 4 7  ==  2
minNOp 2 5  ==  4

Leer más…

Definir las siguientes funciones

potenciasDe2  :: Integer -> [Integer]
menorPotenciaDe2 :: Integer -> Integer

tales que

• (potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,

λ> take 5 (potenciasDe2 3)
[32,32768,33554432,34359738368,35184372088832]
λ> take 2 (potenciasDe2 102)
[1024,102844034832575377634685573909834406561420991602098741459288064]

• (menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,

λ> menorPotenciaDe2 10
1024
λ> menorPotenciaDe2 25
256
λ> menorPotenciaDe2 62
6277101735386680763835789423207666416102355444464034512896
λ> menorPotenciaDe2 425
42535295865117307932921825928971026432
λ> menorPotenciaDe2 967140655691
9671406556917033397649408
λ> [menorPotenciaDe2 a | a <- [1..10]]
[1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.

Leer más…

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
               deriving Show

Por ejemplo, los árboles

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

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]
ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

En el primer ejemplo la máxima ramificación es 2 (en el nodo 1 que tiene 2 hijos), la del segundo es 3 (en el nodo 3 que tiene 3 hijos) y la del tercero es 3 (en el nodo 3 que tiene 3 hijos).

Definir la función

maximaRamificacion :: Arbol a -> Int

tal que (maximaRamificacion a) es la máxima ramificación del árbol a. Por ejemplo,

maximaRamificacion ej1  ==  2
maximaRamificacion ej2  ==  3
maximaRamificacion ej3  ==  3

Leer más…

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

menorSerieCompuesta :: Integer -> (Integer,Integer)

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

menorSerieCompuesta 3    ==  (8,10)
menorSerieCompuesta 4    ==  (24,27)
menorSerieCompuesta 5    ==  (24,28)
menorSerieCompuesta 150  ==  (4652354,4652503)

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Leer más…

Una lista binaria es ondulante si sus elementos son alternativamente 0 y 1. Por ejemplo, las listas [0,1,0,1,0] y [1,0,1,0] son ondulantes.

Definir la función

minConmutacionesOndulante :: [Int] -> Int

tal que (minConmutacionesOndulante xs) es el mínimo número de conmutaciones (es decir, cambios de 0 a 1 o de 1 a 0) necesarias para transformar xs en una lista ondulante. Por ejemplo,

minConmutacionesOndulante [1,1,1]                ==  1
minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1]  ==  2

En el primer ejemplo basta conmutar el elemento en la posición 1 para obtener [1,0,1] y el segundo ejemplo los elementos en las posiciones 1 y 8 para obtener [0,1,0,1,0,1,0,1,0,1].

Leer más…

La semana pasada, Pepe Muñoz Santonja publicó en su blog Algo más que números el artículo Números de Dudeney en la base OEIS.

Un número de Dudeney es un número entero n tal que el cubo de la suma de sus dígitos es igual a n. Por ejemplo, 512 es un número de Dudeney ya que (5+1+2)^3 = 8^3 = 512.

Se puede generalizar variando el exponente: Un número de Dudeney de orden k es un número entero n tal que la potencia k-ésima de la suma de sus dígitos es igual a n. Por ejemplo, 2401 es un número de Dudeney de orden 4 ya que (2+4+0+1)^4 = 7^4 = 2401.

Definir la función

numerosDudeney :: Integer -> [Integer]

tal que (numerosDudeney k) es la lista de los números de Dudeney oe orden k. Por ejemplo,

take 6 (numerosDudeney 3)  == [1,512,4913,5832,17576,19683]
take 6 (numerosDudeney 4)  == [1,2401,234256,390625,614656,1679616]
take 2 (numerosDudeney 20) == [1,1215766545905692880100000000000000000000]

Comprobar con QuickCheck que 19683 es el mayor número de Dudeney de orden 3.

Leer más…

Un número es poderoso si es igual a la suma de sus dígitos elevados a sus respectivas posiciones. Por ejemplo, los números 89, 135 y 1306 son poderosos ya que

  89 = 8^1 + 9^2
 135 = 1^1 + 3^2 + 5^3.
1306 = 1^1 + 3^2 + 0^3 + 6^4

Definir la función

esPoderoso :: Integer -> Bool

tal que (esPoderoso n) se verifica si n es poderoso. Por ejemplo,

λ> esPoderoso 135
True
λ> esPoderoso 80
False
λ> esPoderoso 89
True
λ> esPoderoso 12157692622039623539
True
λ> [n | n <- [10..30000], esPoderoso n]
[89,135,175,518,598,1306,1676,2427]

Comprobar con QuickCheck que 12157692622039623539 es el mayor número poderoso.

Leer más…