Sucesión de Lichtenberg
La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Alternada ..... Lichtenberg 0 ....................... 0 1 ....................... 1 10 ...................... 2 101 ..................... 5 1010 ................... 10 10101 .................. 21 101010 ................. 42 1010101 ................ 85 10101010 .............. 170 101010101 ............. 341 1010101010 ............ 682 10101010101 .......... 1365 101010101010 ......... 2730 |
Definir las funciones
|
1 2 |
lichtenberg :: [Integer] graficaLichtenberg :: Int -> IO () |
tales que
- lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,
|
1 2 |
λ> take 17 lichtenberg [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690] |
- (graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja
Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import Data.Char (digitToInt) import Graphics.Gnuplot.Simple import Test.QuickCheck import Data.Numbers.Primes (isPrime) -- 1ª solución -- =========== lichtenberg1 :: [Integer] lichtenberg1 = map binarioAdecimal sucAlternada -- sucAlternada es la lista cuyos elementos son los términos de la -- sucesión de los dígitos 0 y 1 alternados. Por ejemplo, -- λ> take 7 sucAlternada -- ["0","1","10","101","1010","10101","101010"] sucAlternada :: [String] sucAlternada = ['0'] : [take n cadenaAlternada | n <- [1..]] -- cadenaAltenada es la cadena formada alternando los caracteres 1 y -- 0. Por ejemplo, -- take 20 cadenaAlternada == "10101010101010101010" cadenaAlternada :: String cadenaAlternada = cycle ['1','0'] -- (binarioAdecimal cs) es el número decimal correspondiente al número -- binario cuya cadena de dígitos es cs. Por ejemplo, -- binarioAdecimal "11101" == 29 binarioAdecimal :: String -> Integer binarioAdecimal = foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0 -- 2ª solución lichtenberg2 :: [Integer] lichtenberg2 = map a [0..] where a 0 = 0 a 1 = 1 a n = a (n-1) + 2 * a (n-2) + 1 -- 3ª solución lichtenberg3 :: [Integer] lichtenberg3 = 0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3)) -- Comprobación de eficiencia -- λ> length (show (lichtenberg1 !! 27)) -- 8 -- (0.02 secs, 155,384 bytes) -- λ> length (show (lichtenberg2 !! 27)) -- 8 -- (2.22 secs, 311,157,760 bytes) -- -- λ> length (show (lichtenberg1 !! (8*10^4))) -- 24083 -- (1.28 secs, 664,207,040 bytes) -- λ> length (show (lichtenberg3 !! (8*10^4))) -- 24083 -- (2.59 secs, 1,253,328,200 bytes) -- La propiedad es propLichtenberg :: Int -> Property propLichtenberg n = n > 4 ==> not (isPrime (lichtenberg1 !! n)) -- La comprobación es -- λ> quickCheck propLichtenberg -- +++ OK, passed 100 tests. graficaLichtenberg :: Int -> IO () graficaLichtenberg n = plotList [ Key Nothing , Title "Numero de digitos de la sucesion de Lichtenberg" , PNG "Sucesion_de_Lichtenberg.png" ] (take n (map (length . show) lichtenberg1)) |