Sucesión de Rowland
Definir las siguientes sucesiones
sucesionA :: [Integer] sucesionB :: [Integer] sucesionRowland :: [Integer]
tales que
- el término n-ésimo de la sucesionA es a(n) definido por a(1) = 7 y a(n) = a(n-1) + mcd(n, a(n-1)), para n > 1. Por ejemplo,
λ> take 20 sucesionA
[7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44]
- los términos de la sucesionB son las diferencias de los términos consecutivos de la sucesionA. Por ejemplo,
λ> take 30 sucesionB
[1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3,1,1,1,1,1,1,1]
- los términos de la sucesionRowland son los términos de la sucesionB distintos de 1. Por ejemplo,\0
λ> take 20 sucesionRowland
[5,3,11,3,23,3,47,3,5,3,101,3,7,11,3,13,233,3,467,3]
λ> sucesionRowland !! 92
15567089
Comprobar con QuickCheck que los elementos de la sucesionRowland son números primos.
Nota: Eric S. Rowland demostró en A natural prime-generating recurrence que los elementos de la sucesionRowland son números primos.
Soluciones
import Data.Numbers.Primes (isPrime) import Test.QuickCheck (Property, (==>), quickCheck) sucesionA :: [Integer] sucesionA = 7 : zipWith (+) sucesionA (zipWith gcd sucesionA [2..]) sucesionB :: [Integer] sucesionB = zipWith (-) (tail sucesionA) sucesionA sucesionRowland :: [Integer] sucesionRowland = filter (> 1) sucesionB -- La propiedad es prop_sucesionRowland :: Int -> Property prop_sucesionRowland n = n >= 0 ==> isPrime (sucesionRowland !! n) -- La comprobación es -- λ> quickCheck prop_sucesionRowland -- +++ OK, passed 100 tests.