Ir al contenido principal

Descomposiciones en sumas de cuatro cuadrados

Misceláneas

Definir la función

descomposiciones :: Int -> [[Int]]

tal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.

λ> descomposiciones 4
[[1,1,1,1]]
λ> descomposiciones 5
[]
λ> descomposiciones 7
[[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]]
λ> descomposiciones 10
[[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]]
λ> descomposiciones 15
[[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1],
[4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]]
λ> length (descomposiciones 50000)
5682

Leer más…

Numero de particiones de un conjunto

Misceláneas

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}}

Definir la función

nParticiones :: [a] -> Integer

tal que (nParticiones xs) es el número de particiones de xs. Por ejemplo,

nParticiones [1,2]                     ==  2
nParticiones [1,2,3]                   ==  5
nParticiones "abcd"                    ==  15
length (show (nParticiones [1..500]))  ==  844

Leer más…

Particiones de un conjunto

Misceláneas

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}}

Definir la función

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

tal que (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,

λ> particiones [1,2]
[[[1,2]],[[1],[2]]]
λ> particiones [1,2,3]
[[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]
λ> particiones "abcd"
[["abcd"],["a","bcd"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"],
 ["ac","bd"],["c","abd"],["a","b","cd"],["a","bc","d"],["a","c","bd"],
 ["ab","c","d"],["b","ac","d"],["b","c","ad"],["a","b","c","d"]]

Leer más…

Inserciones en una lista de listas

Misceláneas

Definir la función

inserta :: a -> [[a]] -> [[[a]]]

tal que (inserta x yss) es la lista obtenida insertando x en cada uno de los elementos de yss. Por ejemplo,

λ> inserta 1 [[2,3],[4],[5,6,7]]
[[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]]
λ> inserta 'a' ["hoy","es","lunes"]
[["ahoy","es","lunes"],["hoy","aes","lunes"],["hoy","es","alunes"]]

Leer más…

Divisiones del círculo

Misceláneas

Dado 4 puntos de un círculo se pueden dibujar 2 cuerdas entre ellos de forma que no se corten. En efecto, si se enumeran los puntos del 1 al 4 en sentido de las agujas del reloj una forma tiene las cuerdas {1-2, 3-4} y la otra {1-4, 2-3}.

Definir la función

numeroFormas :: Integer -> Integer

tal que (numeroFormas n) es el número de formas que se pueden dibujar n cuerdas entre 2xn puntos de un círculo sin que se corten. Por ejemplo,

numeroFormas 1   ==  1
numeroFormas 2   ==  2
numeroFormas 4   ==  14
numeroFormas 75  ==  1221395654430378811828760722007962130791020
length (show (numeroFormas 1000))  ==  598

Leer más…

Número de sumandos en suma de cuadrados

Misceláneas

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

16 = 4²
29 = 2² + 5²
14 = 1^2 + 2^2 + 3^2
15 = 1^2 + 1^2 + 2^2 + 3^2

Definir las funciones

ordenLagrange        :: Integer -> Int
graficaOrdenLagrange :: Integer -> IO ()

tales que

  • (ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.
ordenLagrange 16     ==  1
ordenLagrange 29     ==  2
ordenLagrange 14     ==  3
ordenLagrange 15     ==  4
ordenLagrange 10000  ==  1
ordenLagrange 10001  ==  2
ordenLagrange 10002  ==  3
ordenLagrange 10007  ==  4
  • (graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Número de sumandos en suma de cuadrados

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Leer más…

Mayor exponente

Misceláneas

Definir las funciones

mayorExponente        :: Integer -> Integer
graficaMayorExponente :: Integer -> IO ()

tales que

  • (mayorExponente n) es el mayor número b para el que existe un a tal que n = a^b. Se supone que n > 1. Por ejemplo,
mayorExponente 9   ==  2
mayorExponente 8   ==  3
mayorExponente 7   ==  1
mayorExponente 18  ==  1
mayorExponente 36  ==  2
mayorExponente (10^(10^5))  ==  100000
  • (graficaMayorExponente n) dibuja la gráfica de los mayores exponentes de los números entre 2 y n. Por ejemplo, (graficaMayorExponente 50) dibuja

Mayor exponente

Leer más…

Mezcla de listas

Misceláneas

Definir la función

mezcla :: [[a]] -> [a]

tal que (mezcla xss) es la lista tomando sucesivamente los elementos de xss en la misma posición. Cuando una de las listas de xss es vacía, se continua con las restantes. por ejemplo,

mezcla [[1,2],[3..7],[8..10]]            ==  [1,3,8,2,4,9,5,10,6,7]
mezcla ["Estamos","en","2019"]           ==  "Ee2sn0t1a9mos"
take 9 (mezcla [[3,6..],[5,7..],[0,1]])  ==  [3,5,0,6,7,1,9,9,12]

Leer más…

Ternas euclídeas

Misceláneas

Uno de los problemas planteados por Euclides en los Elementos consiste en encontrar tres números tales que cada uno de sus productos, dos a dos, aumentados en la unidad sea un cuadrado perfecto.

Diremos que (x,y,z) es una terna euclídea si es una solución del problema; es decir, si x <= y <= z y xy+1, yz+1 y zx+1 son cuadrados. Por ejemplo, (4,6,20) es una terna euclídea ya que

4x6+1 = 5^2, 6x20+1 = 11^2 y 20*4+1 = 9^2

Definir la funciones

ternasEuclideas        :: [(Integer,Integer,Integer)]
esMayorDeTernaEuclidea :: Integer -> Bool

tales que

  • ternasEuclideas es la lista de las ternas euclídeas. Por ejemplo,
λ> take 7 ternasEuclideas
[(1,3,8),(2,4,12),(1,8,15),(3,5,16),(4,6,20),(3,8,21),(5,7,24)]
  • (esMayorDeTernaEuclidea z) se verifica si existen x, y tales que (x,y,z) es una terna euclídea. Por ejemplo,
esMayorDeTernaEuclidea 20  ==  True
esMayorDeTernaEuclidea 22  ==  False

Comprobar con QuickCheck que z es el mayor de una terna euclídea si, y sólo si, existe un número natural x tal que 1 < x < z - 1 y x^2 es congruente con 1 módulo z.

Leer más…

Sucesión de Cantor de números innombrables

Misceláneas

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior:

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
(30) 99 100

Definir las funciones

sucCantor        :: [Integer]
graficaSucCantor :: Int -> IO ()

tales que

  • sucCantor es la lista cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,
λ> take 100 sucCantor
[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
6, 92,93,94,95,96, 29, 30 ,99,100]
λ> sucCantor2 !! (5+10^6)
544480
λ> sucCantor2 !! (6+10^6)
266086
  • (graficaSucCantor n) es la gráfica de los n primeros términos de la sucesión de Cantor. Por ejemplo, (graficaSucCantor 200) dibuja

Sucesión de Cantor de números innombrables

Leer más…