La sucesión ECG
La sucesión ECG estás definida por a(1) = 1, a(2) = 2 y, para n >= 3, a(n) es el menor natural que aún no está en la sucesión tal que a(n) tiene algún divisor común con a(n-1).
Los primeros términos de la sucesión son 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, …
Al dibujar su gráfica, se parece a la de los electrocardiogramas (abreviadamente, ECG). Por ello, la sucesión se conoce como la sucesión ECG.
Definir las funciones
1 2 |
sucECG :: [Integer] graficaSucECG :: Int -> IO () |
tales que
- sucECG es la lista de los términos de la sucesión ECG. Por ejemplo,
1 2 3 4 |
λ> take 20 sucECG [1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11] λ> sucECG !! 6000 6237 |
- (graficaSucECG n) dibuja la gráfica de los n primeros términos de la sucesión ECG. Por ejemplo, (graficaSucECG 160) dibuja
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import Data.List (delete) import Graphics.Gnuplot.Simple sucECG :: [Integer] sucECG = 1 : ecg 2 [2..] where ecg x zs = f zs where f (y:ys) | gcd x y > 1 = y : ecg y (delete y zs) | otherwise = f ys graficaSucECG :: Int -> IO () graficaSucECG n = plotList [ Key Nothing , PNG "La_sucesion_ECG.png" ] (take n sucECG) |
Pensamiento
Algunos desesperados
sólo se curan con soga;
otros, con siete palabras:
la fe se ha puesto de moda.Antonio Machado
Usando Set puede reducirse notablemente la constante cuadrática:
Usando una criba podemos factorizar rápidamente, pero la búsqueda del siguiente no visitado no veo como hacerla óptima (combinaciones de todos los primos), en todo caso muchísimo más rápida que las anteriores (ej. para n=194561 unos 10seg):