Teorema de Carmichael
La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
La sucesión comieanza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.
El teorema de Carmichael establece que para todo n mayor que 12, el n-ésimo número de Fibonacci F(n) tiene al menos un factor primo que no es factor de ninguno de los términos anteriores de la sucesión.
Si un número primo p es un factor de F(n) y no es factor de ningún F(m) con m < n, entonces se dice que p es un factor característico o un divisor primitivo de F(n).
Definir la función
|
1 |
factoresCaracteristicos :: Int -> [Integer] |
tal que (factoresCaracteristicos n) es la lista de los factores característicos de F(n). Por ejemplo,
|
1 2 3 4 5 |
factoresCaracteristicos 4 == [3] factoresCaracteristicos 6 == [] factoresCaracteristicos 19 == [37,113] factoresCaracteristicos 20 == [41] factoresCaracteristicos 37 == [73,149,2221] |
Comprobar con QuickCheck el teorema de Carmichael; es decir, para todo número entero (factoresCaracteristicos (13 + abs n)) es una lista no vacía.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import Data.List (nub) import Data.Numbers.Primes import Test.QuickCheck factoresCaracteristicos :: Int -> [Integer] factoresCaracteristicos n = [x | x <- factoresPrimos (fib n) , and [fib m `mod` x /= 0 | m <- [1..n-1]]] -- (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por -- ejemplo, -- fib 6 == 8 fib :: Int -> Integer fib n = fibs !! n -- fibs es la lista de términos de la sucesión de Fibonacci. Por ejemplo, -- λ> take 20 fibs -- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181] fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) -- (factoresPrimos n) es la lista de los factores primos de n. Por -- ejemplo, -- factoresPrimos 600 == [2,3,5] factoresPrimos :: Integer -> [Integer] factoresPrimos 0 = [] factoresPrimos n = nub (primeFactors n) -- Teorema -- ======= -- El teorema es teorema_de_Carmichael :: Int -> Bool teorema_de_Carmichael n = not (null (factoresCaracteristicos n')) where n' = 13 + abs n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=50}) teorema_de_Carmichael -- +++ OK, passed 100 tests. |
Pensamiento
No puede ser
amor de tanta fortuna:
dos soledades en una.Antonio Machado
Un comentario