La sucesión de Thue-Morse

José A. Alonso

14-01-2024

Misceláneas

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

   [0]
   [0,1]
   [0,1,1,0]
   [0,1,1,0,1,0,0,1]
   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

De esta forma se va formando una sucesión

   0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...

que se conoce como la sucesión de Thue-Morse.

Definir la sucesión

   sucThueMorse :: [Int]

cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,

   λ> take 30 sucThueMorse
   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
   λ> map (sucThueMorse4 !!) [1234567..1234596]
   [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0]
   λ> map (sucThueMorse4 !!) [4000000..4000030]
   [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]

Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces

   s(2n)   = s(n)
   s(2n+1) = 1 - s(n)

La serie de Thue-Morse

José A. Alonso

09-01-2024

Misceláneas

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros términos de la serie son

   [0]
   [0,1]
   [0,1,1,0]
   [0,1,1,0,1,0,0,1]
   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

Definir la lista

   serieThueMorse :: [[Int]]

tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,

   λ> take 4 serieThueMorse
   [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

Representaciones de un número como suma de dos cuadrados

José A. Alonso

04-01-2024

Misceláneas

Definir la función

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

tal que representaciones n es la lista de pares de números naturales (x,y) tales que n = x² + y². Por ejemplo.

   representaciones  20              ==  [(2,4)]
   representaciones  25              ==  [(0,5),(3,4)]
   representaciones 325              ==  [(1,18),(6,17),(10,15)]
   length (representaciones (10^14)) == 8

Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.

Sumas de dos primos

José A. Alonso

29-12-2023

Misceláneas

Definir la sucesión

   sumasDeDosPrimos :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,

   λ> take 23 sumasDeDosPrimos
   [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]
   λ> sumasDeDosPrimos !! (5*10^5)
   862878

Factorizaciones de números de Hilbert

José A. Alonso

24-12-2023

Misceláneas

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...

Definir la función

   factorizacionesH :: Integer -> [[Integer]]

tal que factorizacionesH n es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,

  factorizacionesH  25    ==  [[5,5]]
  factorizacionesH  45    ==  [[5,9]]
  factorizacionesH 441    ==  [[9,49],[21,21]]
  factorizacionesH 80109  ==  [[9,9,989],[9,69,129]]

Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).

Números primos de Hilbert

José A. Alonso

19-12-2023

Misceláneas

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, ...

Definir la sucesión

   primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

   take 15 primosH     == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
   primosH !! (3*10^4) == 313661

El teorema de Navidad de Fermat

José A. Alonso

14-12-2023

Misceláneas

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.

Definir las funciones

   representaciones :: Integer -> [(Integer,Integer)]
   primosImparesConRepresentacionUnica :: [Integer]
   primos4nM1 :: [Integer]

tales que

representaciones n es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo.

     representaciones  20           ==  [(2,4)]
     representaciones  25           ==  [(0,5),(3,4)]
     representaciones 325           ==  [(1,18),(6,17),(10,15)]
     representaciones 100000147984  ==  [(0,316228)]
     length (representaciones (10^10))    ==  6
     length (representaciones (4*10^12))  ==  7

primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,

     λ> take 20 primosImparesConRepresentacionUnica
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,

     λ> take 20 primos4nM1
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y² (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).

Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Números de Pentanacci

José A. Alonso

09-12-2023

Misceláneas

Los números de Fibonacci se definen mediante las ecuaciones

   F(0) = 0
   F(1) = 1
   F(n) = F(n-1) + F(n-2), si n > 1

Los primeros números de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones

   P(0) = 0
   P(1) = 1
   P(2) = 1
   P(3) = 2
   P(4) = 4
   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Definir las funciones

   pentanacci  :: Integer -> Integer
   pentanaccis :: [Integer]

tales que

pentanacci n es el n-ésimo número de Pentanacci. Por ejemplo,

     λ> pentanacci 14
     3525
     λ> pentanacci (10^5) `mod` 10^30
     482929150584077921552549215816
     λ> length (show (pentanacci (10^5)))
     29357

pentanaccis es la lista de los números de Pentanacci. Por ejemplo,

     λ> take 15 pentanacci
     [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]

Algoritmo de bajada para resolver un sistema triangular inferior

José A. Alonso

04-12-2023

Cálculo numérico

Un sistema de ecuaciones lineales \(Ax = b\) es triangular inferior si todos los elementos de la matriz \(A\) que están por encima de la diagonal principal son nulos; es decir, es de la forma \begin{align} &a_{1 1}x_1 &= b_1 \newline &a_{2 1}x_1 + a_{2 2}x_2 &= b_2 \newline &a_{3 1}x_1 + a_{3 2}x_2 + a_{3 3}x_3 &= b_3 \newline &... & \newline &a_{n 1}x_1 + a_{n 2}x_2 + a_{n 3}x_3 +...+ a_{n n}x_n &= b_n \end{align}

El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada: \begin{align} x_1 &= \frac{b_1}{a_{1 1}} \newline x_2 &= \frac{b_2 - a_{2 1}x_1}{a_{2 2}} \newline x_3 &= \frac{b_3 - a_{3 1}x_1 - a_{3 2}x_2}{a_{3 3}} \newline ... \newline x_n &= \frac{b_n - a_{n 1}x_1 - a_{n 2}x_2 - ... - a_{n,n-1}x_{n-1}}{a_{n n}} \end{align}

Definir la función

   bajada :: Matrix Double -> Matrix Double -> Matrix Double

tal que bajada a b es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,

   λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]]
   λ> let b = fromLists [[3],[6.5],[10]]
   λ> bajada a b
   ( 1.5 )
   ( 2.0 )
   ( 0.0 )

Es decir, la solución del sistema \begin{align} 2x &= 3 \newline 3x + y &= 6.5 \newline 4x + 2y + 5z &= 10 \end{align} es \(x=1.5\), \(y=2\) y \(z=0\).

Integración por el método de los rectángulos

José A. Alonso

29-11-2023

Cálculo numérico

La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo (ver en https://en.wikipedia.org/wiki/Riemann_sum) usando la fórmula \[ h(f(a+\frac{h}{2}) + f(a+h+\frac{h}{2}) + f(a+2h+\frac{h}{2}) + ... + f(a+nh+\frac{h}{2}))\] con \(a+nh+\frac{h}{2} \leq b < a+(n+1)h+\frac{h}{2}\) y usando valores pequeños para \(h\).

Definir la función

   integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a

tal que integral a b f h es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de (f(x) = x^3) entre 0 y 1, con paso 0.01, es

   integral 0 1 (^3) 0.01  ==  0.24998750000000042

Otros ejemplos son

   integral 0 1 (^4) 0.01                        ==  0.19998333362500048
   integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01       ==  1.9999250000000026
   log 2 - integral 1 2 (\x -> 1/x) 0.01         ==  3.124931644782336e-6
   pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01  ==  -8.333333331389525e-6