La propiedad de la longitud de la parte periódica afirma que

Si p es un número primo distinto de 2 y de 5, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a [latex]10^n - 1[/latex].

El objetivo de este ejercicio es la verificación de dicha propiedad.

Las fracciones se representan por un par de enteros. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

type Fraccion = (Integer,Integer)

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

type Decimal = (Integer,[Integer],[Integer])

Definir, usando las funciones cocientesRestos y primerRepetido de los ejercicios anteriores, las funciones

decimal :: Fraccion -> Decimal
longitudPeriodo :: Fraccion -> Integer

tales que

• (decimal f) es la representación decimal de la fracción f. Por ejemplo,

decimal (6,2)          ==  (3,[],[])
decimal (3,4)          ==  (0,[7,5],[])
decimal (1,3)          ==  (0,[],[3])
decimal (23,14)        ==  (1,[6],[4,2,8,5,7,1])
decimal (247813,19980) ==  (12,[4,0],[3,0,5])
decimal (1,101)        ==  (0,[],[0,0,9,9])

• (longitudPeriodo f) es la longitud de la parte periódica de la representación decimal de la fracción f. Por ejemplo,

longitudPeriodo (6,2)           ==  0
longitudPeriodo (3,4)           ==  0
longitudPeriodo (1,3)           ==  1
longitudPeriodo (23,14)         ==  6
longitudPeriodo (247813,19980)  ==  3
longitudPeriodo (1,101)         ==  4
longitudPeriodo (1,1229)        ==  1228

Comprobar con QuickCheck la propiedad de la longitud de la parte periódica; es decir, k es un número natural distinto de 0 y 2 y p es el primo k-ésimo, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a [latex]10^n - 1[/latex]..

Leer más…

La transformación de una fracción en un número decimal se realiza mediante una sucesión de divisiones. Por ejemplo, para transformar a decimal la fracción

 247813    |19980
-19980     ---------------
-------     12.40305305...
  48013
 -39960
 ------
   80530
  -79920
  ------
     6100
    -   0
    -----
     61000
    -59940
    ------
      10600
     -    0
     ------
      106000
     - 99900
     -------
        61000
        -59940
        ------
         10600
        -    0
        ------
        106000
       - 99900
       -------
         61000

La transformación anterior se puede representar mediante la siguiente lista de cocientes y restos

[(12,8053),(4,610),(0,6100),(3,1060),(0,10600),(5,6100),
                            (3,1060),(0,10600),(5,6100)]

Definir la función

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

tal que (cocientesRestos (n,d)) es la lista de los cocientes y restos de la transformación decimal de la fracción n/d como se ha indicado anteriormente. Por ejemplo,

λ> take 9 (cocientesRestos (247813,19980))
[(12,8053),(4,610),(0,6100),(3,1060),(0,10600),(5,6100),
(3,1060),(0,10600),(5,6100)]
λ> take 10 (cocientesRestos (6,2))
[(3,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)]
λ> take 10 (cocientesRestos (1,2))
[(0,1),(5,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)]
λ> take 10 (cocientesRestos (1,3))
[(0,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1)]
λ> take 10 (cocientesRestos (23,14))
[(1,9),(6,6),(4,4),(2,12),(8,8),(5,10),(7,2),(1,6),(4,4),(2,12)]

Leer más…

Definir la función

primerRepetido :: Eq a => [a] -> Maybe a

tal que (primerRepetido xs) es justo el primer elemento repetido de la lista xs o Nothing si no tiene elementos repetidos. Por ejemplo,

primerRepetido [3,7,5,7,2]  ==  Just 7
primerRepetido [3,9,5,6,2]  ==  Nothing

Leer más…

Un número entero n es libre de cuadrados si no existe un número primo p tal que p² divide a n; es decir, los factores primos de n son todos distintos.

La función de Möbius μ(n) está definida para todos los enteros positivos como sigue:

• μ(n) = 1 si n es libre de cuadrados y tiene un número par de factores primos.
• μ(n) = -1 si n es libre de cuadrados y tiene un número impar de factores primos.
• μ(n) = 0 si n no es libre de cuadrados.

Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, ...

La función de Mertens M(n) está definida para todos los enteros positivos como la suma de μ(k) para 1 ≤ k ≤ n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, ...

La conjetura de Mertens afirma que

Para todo entero x mayor que 1, el valor absoluto de la función de Mertens en x es menor que la raíz cuadrada de x.

La conjetura fue planteada por Franz Mertens en 1897. Riele Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta más o menos a partir de \(10^{10^{64}}\), cifra que luego de algunos refinamientos se redujo a \(10^{10^{40}}\).

Definir las funciones

mobius :: Integer -> Integer
mertens :: Integer -> Integer
graficaMertens :: Integer -> IO ()

tales que

• (mobius n) es el valor de la función de Möbius en n. Por ejemplo,

mobius 6   ==  1
mobius 30  ==  -1
mobius 12  ==  0

• (mertens n) es el valor de la función de Mertens en n. Por ejemplo,

mertens 1     ==  1
mertens 2     ==  0
mertens 3     ==  -1
mertens 5     ==  -2
mertens 661   ==  -11
mertens 1403  ==  11

• (graficaMertens n) dibuja la gráfica de la función de Mertens, la raíz cuadrada y el opuestos de la raíz cuadrada para los n primeros n enteros positivos. Por ejemplo, (graficaMertens 1000) dibuja

Comprobar con QuickCheck la conjetura de Mertens.

Nota: El ejercicio está basado en La conjetura de Merterns y su relación con un número tan raro como extremada y colosalmente grande publicado por @Alvy la semana pasada en Microsiervos.

Leer más…

Definir la función

productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a

tal que (productoSuma4Cuadrados as bs cs ds) es el producto de las sumas de los cuadrados de cada una de las listas que ocupan la misma posición (hasta que alguna se acaba). Por ejemplo,

productoSuma4Cuadrados [2,3] [1,5] [4,6] [0,3,9]
= (2² + 1² + 4² + 0²) * (3² + 5² + 6² + 3²)
= (4 +  1 + 16  + 0)  * (9 + 25 + 36  + 9)
= 1659

Comprobar con QuickCheckWith que si as, bs cs y ds son listas no vacías de enteros positivos, entonces (productoSuma4Cuadrados as bs cs ds) se puede escribir como la suma de los cuadrados de cuatro enteros positivos.

Leer más…

El número 42 es una suma de cuatro cuadrados de números enteros positivos ya que

42 = 16 + 16 + 9 + 1 = 4² + 4² + 3² + 1²

Definir las funciones

sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)]
graficaNumeroSumas4Cuadrados :: Integer -> IO ()

tales que

• (sumas4Cuadrados n) es la lista de las descompociones de n como suma de cuatro cuadrados. Por ejemplo,

sumas4Cuadrados 42  ==  [(16,16,9,1),(25,9,4,4),(36,4,1,1)]
sumas4Cuadrados 14  ==  []
length (sumas4Cuadrados (5*10^4))  ==  260

• (graficaNumeroSumas4Cuadrados n) dibuja la gráfica del número de descomposiciones en sumas de 4 cuadrados de los n primeros. Por ejemplo, (graficaNumeroSumas4Cuadrados 600) dibuja

Leer más…

Definir la sucesión

numerosSin2EnBase3a :: [Integer]

cuyos términos son los números cuya representación en base 3 no contiene el dígito 2. Por ejemplo,

λ> take 20 numerosSin2EnBase3
[0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85]

Se observa que

• 12 está en la sucesión ya que su representación en base 3 es 110 (porque 1·3² + 1·3¹ + 0.3⁰ = 12) y no contiene a 2.
• 14 no está en la sucesión ya que su representación en base 3 es 112 (porque 1·3² + 1·3¹ + 2.3⁰ = 14) y contiene a 2.

Comprobar con QuickCheck que las sucesiones numerosSin2EnBase3 sucesionSin3enPA (del ejercicio anterior) son iguales; es decir, para todo número natural n, el n-ésimo término de numerosSin2EnBase3 es igual al n-ésimo término de sucesionSin3enPA.

Leer más…

Tres números x, y, z está en progresión aritmética (PA) si existe un d tal que y = x+d y z = y+d. Por ejemplo, 1, 3, 5 están en PA ya que 3 = 1+2 y 5 = 3+2.

Se considera la sucesión donde cada uno de sus términos es el número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo, si representamos por f(n) el n-ésimo término de la sucesión, entonces

f(0) = 0, que es el menor número natural;
f(1) = 1, que es el menor número natural que no está en la sucesión;
f(2) = 3, ya que [0, 1, 2] están en PA y
                 [0, 1, 3] no están en PA;
f(3) = 4, ya que [0, 1, 4], [0, 3, 4] y [1, 3, 4] no están en PA;
f(4) = 9, ya que se descartan
          + el 5 porque [1, 3, 5] están en PA
          + el 6 porque [0, 3, 6] están en PA
          + el 7 porque [1, 4, 7] están en PA
          + el 8 porque [0, 4, 8] estan en PA
          y se acepta el 9 porque no están en PA niguna de [0,1,9],
          [0,3,9], [0,4,9], [1,3,9], [1,4,9], [3,4,9].

Definir la sucesión

sucesionSin3enPA :: [Integer]

donde cada uno de sus términos es el menor número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo,

λ> take 20 sucesionSin3enPA
[0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85]
λ> sucesionSin3enPA !! 250
3270

Leer más…

La conjetura de Goldbach afirma que todo número entero mayor que 2 se puede expresar como suma de dos primos.

Las descomposiciones de Goldbach son las maneras de expresar un número como suma de dos primos. Por ejemplo, el número 10 tiene dos descomposiciones de Goldbach ya que se puede expresar como la suma de 3 y 7 y la suma de 5 y 5.

Definir las funciones

descomposicionesGoldbach :: Integer -> [(Integer,Integer)]
numeroGoldbach :: Integer -> Integer
tieneMaximoLocalGoldbach :: Integer -> Bool

tales que

• (descomposicionesGoldbach n) es la lista de las descomposiciones de Goldbach del número n. Por ejemplo,

descomposicionesGoldbach 5   ==  [(2,3)]
descomposicionesGoldbach 10  ==  [(3,7),(5,5)]
descomposicionesGoldbach 22  ==  [(3,19),(5,17),(11,11)]
descomposicionesGoldbach 34  ==  [(3,31),(5,29),(11,23),(17,17)]
descomposicionesGoldbach 35  ==  []
descomposicionesGoldbach (9+10^9)  ==  [(2,1000000007)]

• (numeroGolbach n) es el número de descomposiciones de Goldbach del número n. Por ejemplo,

numeroGoldbach 5         ==  1
numeroGoldbach 10        ==  2
numeroGoldbach 22        ==  3
numeroGoldbach 34        ==  4
numeroGoldbach 35        ==  0
numeroGoldbach (9+10^9)  ==  1
maximum [numeroGoldbach n | n <- [2..3000]]  ==  128

• (tieneMaximoLocalGoldbach n) se verifica si en n se alcanza un máximo local en el número de descomposiciones de Goldbach; es decir, los números n tales que el número de descomposiciones de Goldbach de n es mayor o igual que las de n-1 y las de n+1. Por ejemplo,

λ> filter tieneMaximoLocalGoldbach [1..45]
[1,2,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44]

En el ejemplo anterior se comprueba que en los múltiplos de 6 (es decir, en 6, 12, 18, 24, 30, 36 y 42), el número de descomposiciones de Goldbach alcanza un máximo local. Comprobar con QuickCheck que esta propiedad se cumple en general; es decir, para todo entero positivo n, el número de descomposiciones de Goldbach en 6n es un máximo local.

Leer más…

El teorema de la amistad afirma que

En cualquier reunión de n personas hay al menos dos personas que tienen el mismo número de amigos (suponiendo que la relación de amistad es simétrica).

Se pueden usar las siguientes representaciones:

• números enteros para representar a las personas,
• pares de enteros (x,y), con x < y, para representar que la persona x e y so amigas y
• lista de pares de enteros para representar la reunión junto con las relaciones de amistad.

Por ejemplo, [(2,3),(3,5)] representa una reunión de tres personas (2, 3 y 5) donde

• 2 es amiga de 3,
• 3 es amiga de 2 y 5 y
• 5 es amiga de 3. Si clasificamos las personas poniendo en la misma clase las que tienen el mismo número de amigos, se obtiene [[2,5],[3]] ya que 2 y 5 tienen 1 amigo y 3 tiene 2 amigos.

Definir la función

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

tal que (clasesAmigos r) es la clasificación según el número de amigos de las personas de la reunión r; es decir, la lista cuyos elementos son las listas de personas con 1 amigo, con 2 amigos y así hasta que se completa todas las personas de la reunión r. Por ejemplo,

clasesAmigos [(2,3),(3,5)]            ==  [[2,5],[3]]
clasesAmigos [(2,3),(4,5)]            ==  [[2,3,4,5]]
clasesAmigos [(2,3),(2,5),(3,5)]      ==  [[2,3,5]]
clasesAmigos [(2,3),(3,4),(2,5)]      ==  [[4,5],[2,3]]
clasesAmigos [(x,x+1) | x <- [1..5]]  ==  [[1,6],[2,3,4,5]]
length (clasesAmigos [(x,x+1) | x <- [1..2020]]) == 2

Comprobar con QuickCheck el teorema de la amistad; es decir, si r es una lista de pares de enteros, entonces (clasesAmigos r') donde r' es la lista de los pares (x,y) de r con x < y y se supone que r' es no vacía.

Leer más…