Ir al contenido principal

Variación de la conjetura de Goldbach

Misceláneas

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

  • (sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,
sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
sumas3PrimosDistintos 10  ==  [(5,3,2)]
sumas3PrimosDistintos 11  ==  []
  • (conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,
conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
conKsumas3PrimosDistintos 0 99  ==  [11,13,17]
  • (noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,
noSonSumas3PrimosDistintos 99   ==  [11,13,17]
noSonSumas3PrimosDistintos 500  ==  [11,13,17]

Leer más…

Matriz dodecafónica

Misceláneas

Como se explica en Create a Twelve-Tone Melody With a Twelve-Tone Matrix una matriz dodecafónica es una matriz de 12 filas y 12 columnas construidas siguiendo los siguientes pasos:

  • Se escribe en la primera fila una permutación de los números del 1 al 12. Por ejemplo,
(  3  1  9  5  4  6  8  7 12 10 11  2 )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
(                                     )
  • Escribir la primera columna de forma que, para todo i (entre 2 y 12), a(i,1) es el número entre 1 y 12 que verifica la siguiente condición
(a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila y la 1ª columna es

(  3  1  9  5  4  6  8  7 12 10 11  2 )
(  5                                  )
(  9                                  )
(  1                                  )
(  2                                  )
( 12                                  )
( 10                                  )
( 11                                  )
(  6                                  )
(  8                                  )
(  7                                  )
(  4                                  )
  • Escribir la segunda fila de forma que, para todo j (entre 2 y 12), a(j,2) es el número entre 1 y 12 que verifica la siguiente condición
(a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila, 1ª columna y 2ª fila es

(  3  1  9  5  4  6  8  7 12 10 11  2 )
(  5  3 11  7  6  8 10  9  2 12  1  4 )
(  9                                  )
(  1                                  )
(  2                                  )
( 12                                  )
( 10                                  )
( 11                                  )
(  6                                  )
(  8                                  )
(  7                                  )
(  4                                  )
  • Las restantes filas se completan como la 2ª; es decir, para todo i (entre 3 y 12) y todo j (entre 2 y 12), a(i,j) es el número entre 1 y 12 que verifica la siguiente relación.
(a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz dodecafónica es

(  3  1  9  5  4  6  8  7 12 10 11  2 )
(  5  3 11  7  6  8 10  9  2 12  1  4 )
(  9  7  3 11 10 12  2  1  6  4  5  8 )
(  1 11  7  3  2  4  6  5 10  8  9 12 )
(  2 12  8  4  3  5  7  6 11  9 10  1 )
( 12 10  6  2  1  3  5  4  9  7  8 11 )
( 10  8  4 12 11  1  3  2  7  5  6  9 )
( 11  9  5  1 12  2  4  3  8  6  7 10 )
(  6  4 12  8  7  9 11 10  3  1  2  5 )
(  8  6  2 10  9 11  1 12  5  3  4  7 )
(  7  5  1  9  8 10 12 11  4  2  3  6 )
(  4  2 10  6  5  7  9  8  1 11 12  3 )

Definir la función

matrizDodecafonica :: [Int] -> Matrix Int

tal que (matrizDodecafonica xs) es la matriz dodecafónica cuya primera fila es xs (que se supone que es una permutación de los números del 1 al 12). Por ejemplo,

λ> matrizDodecafonica [3,1,9,5,4,6,8,7,12,10,11,2]
(  3  1  9  5  4  6  8  7 12 10 11  2 )
(  5  3 11  7  6  8 10  9  2 12  1  4 )
(  9  7  3 11 10 12  2  1  6  4  5  8 )
(  1 11  7  3  2  4  6  5 10  8  9 12 )
(  2 12  8  4  3  5  7  6 11  9 10  1 )
( 12 10  6  2  1  3  5  4  9  7  8 11 )
( 10  8  4 12 11  1  3  2  7  5  6  9 )
( 11  9  5  1 12  2  4  3  8  6  7 10 )
(  6  4 12  8  7  9 11 10  3  1  2  5 )
(  8  6  2 10  9 11  1 12  5  3  4  7 )
(  7  5  1  9  8 10 12 11  4  2  3  6 )
(  4  2 10  6  5  7  9  8  1 11 12  3 )

Comprobar con QuickCheck para toda matriz dodecafónica D se verifican las siguientes propiedades:

  • todas las filas de D son permutaciones de los números 1 a 12,
  • todos los elementos de la diagonal de D son iguales y
  • la suma de todos los elementos de D es 936.

Leer más…

La conjetura de Collatz

Misceláneas

La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.

La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es

12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.

Definir las funciones

siracusa        :: Integer -> [Integer]
graficaSiracusa :: Int -> [Integer] -> IO ()

tales que

  • (siracusa x) es la sucesión de Siracusa de x. Por ejemplo,
λ> take 20 (siracusa 12)
[12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]
λ> take 20 (siracusa 22)
[22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]
  • (graficaSiracusa n xs) dibuja los n primeros términos de las sucesiones de Siracusas de los elementos de xs. Por ejemplo, (graficaSiracusa 100 [27]) dibuja

La conjetura de Collatz

y (graficaSiracusa 150 [1..1000]) dibuja

La conjetura de Collatz

Comprobar con QuickCheck la conjetura de Collatz.

Leer más…

Conjetura de las familias estables por uniones

Misceláneas

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.

La conjetura afirma que toda familia no vacía estable por uniones y distinta {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

esEstable :: Ord a => Set (Set a) -> Bool
familiasEstables :: Ord a => Set a -> Set (Set (Set a))
mayoritarios :: Ord a => Set (Set a) -> [a]
conjeturaFrankl :: Int -> Bool

tales que

  • (esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,
λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
True
λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
False
λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
True
  • (familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,
λ> familiasEstables (fromList [1..2])
fromList
  [ fromList []
  , fromList [fromList []]
  , fromList [fromList [],fromList [1]]
  , fromList [fromList [],fromList [1],fromList [1,2]],
  fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [1,2]]
  , fromList [fromList [],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [2]]
  , fromList [fromList [1]]
  , fromList [fromList [1],fromList [1,2]]
  , fromList [fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [1,2]]
  , fromList [fromList [1,2],fromList [2]]
  , fromList [fromList [2]]]
λ> size (familiasEstables (fromList [1,2]))
14
λ> size (familiasEstables (fromList [1..3]))
122
λ> size (familiasEstables (fromList [1..4]))
4960
  • (mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,
mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []
  • (conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,...,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.
conjeturaFrankl 2  ==  True
conjeturaFrankl 3  ==  True
conjeturaFrankl 4  ==  True

Leer más…

Distribución de diferencias de dígitos consecutivos de pi

Misceláneas

Usando la librería Data.Number.CReal, que se instala con

cabal install number

se pueden calcular el número pi con la precisión que se desee. Por ejemplo,

λ> import Data.Number.CReal
λ> showCReal 60 pi
"3.141592653589793238462643383279502884197169399375105820974945"

importa la librería y calcula el número pi con 60 decimales.

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros n dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

distribucionDDCpi :: Int -> [Int]
graficas :: [Int] -> FilePath -> IO ()

tales que

  • (distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,
λ> distribucionDDCpi 18
[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
λ> distribucionDDCpi 100
[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
λ> distribucionDDCpi 200
[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
λ> distribucionDDCpi 1000
[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
λ> distribucionDDCpi 5000
[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]
  • (graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] "distribucionDDCpi.png" se escribe en el fichero "distribucionDDCpi.png" la siguiente gráfica

Distribución de diferencias de dígitos consecutivos de pi

Leer más…

Cálculo de dígitos de pi y su distribución

Misceláneas

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi c0on la función digitosPi definida por

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
  g (q,r,t,k,n,l) =
    if 4*q+r-t < n*t
    then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
    else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

λ> take 25 digitosPi
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, ...

Usando digitosPi, definir las siguientes funciones

distribucionDigitosPi :: Int -> [Int]
frecuenciaDigitosPi   :: Int -> [Double]

tales que

  • (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,
λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]
  • (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,
λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Leer más…

Huecos de Aquiles

Misceláneas

Un número de Aquiles es un número natural n que es potente (es decir, si p es un divisor primo de n, entonces p² también lo es) y no es una potencia perfecta (es decir, no existen números naturales m y k tales que n es igual a m^k). Por ejemplo,

  • 108 es un número de Aquiles proque es un número potente (ya que su factorización es 2^2 · 3^3, sus divisores primos son 2 and 3 y sus cuadrados (2^2 = 4 y 3^2 = 9) son divisores de 108. Además, 108 no es una potencia perfecta.
  • 360 no es un número de Aquiles ya que 5 es un divisor primo de 360, pero 5^2 = 15 no lo es.
  • 784 no es un número de Aquiles porque, aunque es potente, es una potencia perfecta ya que 784 = 28^2.

Los primeros números de Aquiles son

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, ...

Definir las funciones

esAquiles              :: Integer -> Bool
huecosDeAquiles        :: [Integer]
graficaHuecosDeAquiles :: Int -> IO ()

tales que

  • (esAquiles x) se verifica si x es un número de Aquiles. Por ejemplo,
esAquiles 108         ==  True
esAquiles 360         ==  False
esAquiles 784         ==  False
esAquiles 5425069447  ==  True
esAquiles 5425069448  ==  True
  • huecosDeAquiles es la sucesión de la diferencias entre los números de Aquiles consecutivos. Por ejemplo,
λ> take 15 huecosDeAquiles
[36,92,88,104,40,68,148,27,125,64,104,4,153,27,171]
  • (graficaHuecosDeAquiles n) dibuja la gráfica de los n primeros huecos de Aquiles. Por ejemplo, (graficaHuecosDeAquiles 160) dibuja

Huecos de Aquiles

Leer más…

Árbol de divisores

Misceláneas

Se dice que a es un divisor propio maximal de un número b si a es un divisor de b distinto de b y no existe ningún número c tal que a < c < b, a es un divisor de c y c es un divisor de b. Por ejemplo, 15 es un divisor propio maximal de 30, pero 5 no lo es.

El árbol de los divisores de un número x es el árbol que tiene como raíz el número x y cada nodo tiene como hijos sus divisores propios maximales. Por ejemplo, el árbol de divisores de 30 es

       30
       /|\
      / | \
     /  |  \
    /   |   \
   /    |    \
  6    10    15
 / \   / \   / \
2   3 2   5 3   5

Usando el tipo de dato

data Arbol = N Integer [Arbol]
  deriving (Eq, Show)

el árbol anterior se representa por

N 30
  [N 6
     [N 2 [N 1 []],
      N 3 [N 1 []]],
   N 10
     [N 2 [N 1 []],
      N 5 [N 1 []]],
   N 15
     [N 3 [N 1 []],
      N 5 [N 1 []]]]

Definir las funciones

arbolDivisores             :: Integer -> Arbol
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

tales que

  • (arbolDivisores x) es el árbol de los divisores del número x. Por ejemplo,
λ> arbolDivisores 30
N 30 [N 6  [N 2 [N 1 []],N 3 [N 1 []]],
      N 10 [N 2 [N 1 []],N 5 [N 1 []]],
      N 15 [N 3 [N 1 []],N 5 [N 1 []]]]
  • (nOcurrenciasArbolDivisores x y) es el número de veces que aparece el número x en el árbol de los divisores del número y. Por ejemplo,
nOcurrenciasArbolDivisores  3 30  ==  2
nOcurrenciasArbolDivisores  6 30  ==  1
nOcurrenciasArbolDivisores 30 30  ==  1
nOcurrenciasArbolDivisores  1 30  ==  6
nOcurrenciasArbolDivisores  9 30  ==  0
nOcurrenciasArbolDivisores  2 (product [1..10])  ==  360360
nOcurrenciasArbolDivisores  3 (product [1..10])  ==  180180
nOcurrenciasArbolDivisores  5 (product [1..10])  ==  90090
nOcurrenciasArbolDivisores  7 (product [1..10])  ==  45045
nOcurrenciasArbolDivisores  6 (product [1..10])  ==  102960
nOcurrenciasArbolDivisores 10 (product [1..10])  ==  51480
nOcurrenciasArbolDivisores 14 (product [1..10])  ==  25740

Leer más…

Triángulo de Euler

Misceláneas

El triángulo de Euler se construye a partir de las siguientes relaciones

A(n,1) = A(n,n) = 1
A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m).

Sus primeros términos son

1
1 1
1 4   1
1 11  11    1
1 26  66    26    1
1 57  302   302   57     1
1 120 1191  2416  1191   120   1
1 247 4293  15619 15619  4293  247   1
1 502 14608 88234 156190 88234 14608 502 1

Definir las siguientes funciones:

numeroEuler        :: Integer -> Integer -> Integer
filaTrianguloEuler :: Integer -> [Integer]
trianguloEuler     :: [[Integer]]

tales que

  • (numeroEuler n k) es el número de Euler A(n,k). Por ejemplo,
numeroEuler 8 3  == 15619
numeroEuler 20 6 == 21598596303099900
length (show (numeroEuler 1000 500)) == 2567
  • (filaTrianguloEuler n) es la n-ésima fila del triángulo de Euler. Por ejemplo,
filaTrianguloEuler 7  ==  [1,120,1191,2416,1191,120,1]
filaTrianguloEuler 8  ==  [1,247,4293,15619,15619,4293,247,1]
length (show (maximum (filaTrianguloEuler 1000)))  ==  2567
  • trianguloEuler es la lista con las filas del triángulo de Euler
λ> take 6 trianguloEuler
[[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]
λ> length (show (maximum (trianguloEuler !! 999)))
2567

Leer más…