Números de Perrin
Los números de Perrin se definen por la elación de recurrencia
1 |
P(n) = P(n - 2) + P(n - 3) si n > 2, |
con los valores iniciales
1 |
P(0) = 3, P(1) = 0 y P(2) = 2. |
Definir la sucesión
1 |
sucPerrin :: [Integer] |
cuyos elementos son los números de Perrin. Por ejemplo,
1 2 3 4 |
λ> take 15 sucPerrin [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51] λ> length (show (sucPerrin !! (2*10^5))) 24425 |
Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.
Soluciones
[schedule expon=’2019-06-12′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 12 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
Encuentro lo que no busco:
las hojas del toronjil
huelen a limón maduro.Antonio Machado
[/schedule]
[schedule on=’2019-06-12′ at=»06:00″]
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import Data.List (genericIndex, unfoldr) import Data.Numbers.Primes (isPrime) import Test.QuickCheck -- 1ª solución sucPerrin1 :: [Integer] sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1) -- 2ª solución sucPerrin2 :: [Integer] sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)] where op (a,b,c) = (b,c,a+b) -- 3ª solución sucPerrin3 :: [Integer] sucPerrin3 = unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2)) -- Comparación de eficiencia -- λ> length (show (sucPerrin1 !! (10^5))) -- 12213 -- (1.44 secs, 295,373,680 bytes) -- λ> length (show (sucPerrin2 !! (10^5))) -- 12213 -- (1.22 secs, 301,493,408 bytes) -- λ> length (show (sucPerrin3 !! (10^5))) -- 12213 -- (0.86 secs, 296,911,304 bytes) -- Usaremos la 3ª sucPerrin :: [Integer] sucPerrin = sucPerrin3 -- La propiedad es conjeturaPerrin :: Integer -> Property conjeturaPerrin n = n > 1 ==> (perrin n `mod` n == 0) == isPrime n -- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por -- ejemplo, -- perrin 4 == 2 -- perrin 5 == 5 -- perrin 6 == 5 perrin :: Integer -> Integer perrin n = sucPerrin `genericIndex` n -- La comprobación es -- λ> quickCheck conjeturaPerrin -- +++ OK, passed 100 tests. -- Nota: Aunque QuickCheck no haya encontrado contraejemplos, la -- propiedad no es cierta. Sólo lo es una de las implicaciones: si n es -- primo, entonces el n-ésimo término de la sucesión de Perrin es -- divisible por n. La otra es falsa y los primeros contraejemplos son -- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291 |
[/schedule]
Una solución usando programación dinámica