Huecos de Euclides
El teorema de Euclides afirma que existen infinitos números primos. En palabras de Euclides,
«Hay más números primos que cualquier cantidad propuesta de números primos.» (Proposición 20 del Libro IX de «Los Elementos»)
Su demostración se basa en que si p₁,…,pₙ son los primeros n números primos, entonces entre 1+pₙ y 1+p₁·p₂·…·pₙ hay algún número primo. La cantidad de dichos números primos se llama el n-ésimo hueco de Euclides. Por ejemplo, para n = 3 se tiene que p₁ = 2, p₂ = 3 y p₃ = 5 entre 1+p₃ = 6 y 1+p₁·p₂·p₃ = 31 hay 8 números primos (7, 11, 13, 17, 19, 23, 29 y 31), por lo que el valor del tercer hueco de Euclides es 8.
Definir la función
|
1 |
hueco :: Int -> Integer |
tal que (hueco n) es el n-ésimo hueco de Eulides. Por ejemplo,
|
1 2 |
hueco 3 == 8 [hueco n | n <- [1..8]] == [1,2,8,43,339,3242,42324,646021] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import Data.List import Data.Numbers.Primes hueco :: Int -> Integer hueco n = nPrimosEntre (primes !! (n-1)) (1 + product (take n primes)) -- (nPrimosEntre x y) es el número de primos entre x e y. Por ejemplo, -- nPrimosEntre 3 7 == 2 nPrimosEntre :: Integer -> Integer -> Integer nPrimosEntre x y = genericLength (primosEntre x y) -- (primosEntre x y) es la lista de los números de primos entre x e -- y. Por ejemplo, -- primosEntre 3 7 == [5,7] primosEntre :: Integer -> Integer -> [Integer] primosEntre x y = takeWhile (<=y) (dropWhile (<=x) primes) |
Referencias
- Euclid’s theorem en la ProofWiki.
6 Comentarios