Menu Close

Etiqueta: isPrime

Sumas alternas de factoriales

Las primeras sumas alternas de los factoriales son números primos; en efecto,

   3! - 2! + 1! = 5
   4! - 3! + 2! - 1! = 19
   5! - 4! + 3! - 2! + 1! = 101
   6! - 5! + 4! - 3! + 2! - 1! = 619
   7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
   8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899

son primos, pero

   9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981

no es primo.

Definir las funciones

   sumaAlterna         :: Integer -> Integer
   sumasAlternas       :: [Integer]
   conSumaAlternaPrima :: [Integer]

tales que

  • (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,
     sumaAlterna 3  ==  5
     sumaAlterna 4  ==  19
     sumaAlterna 5  ==  101
     sumaAlterna 6  ==  619
     sumaAlterna 7  ==  4421
     sumaAlterna 8  ==  35899
     sumaAlterna 9  ==  326981
  • sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,
     λ> take 10 sumasAlternas
     [0,1,1,5,19,101,619,4421,35899,326981]
  • conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,
     λ> take 8 conSumaAlternaPrima
     [3,4,5,6,7,8,10,15]

Soluciones

import Data.List (cycle, genericTake)
import Data.Numbers.Primes (isPrime)
 
Definiciones de sumaAlterna                                      --
===========================
 
-- 1ª definición
-- -------------
 
sumaAlterna1 :: Integer -> Integer
sumaAlterna1 1 = 1
sumaAlterna1 n = factorial n - sumaAlterna1 (n-1)
 
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 2ª definición
-- -------------
 
sumaAlterna2 :: Integer -> Integer
sumaAlterna2 n = sum (zipWith (*) signos (tail factoriales))
    where
      signos | odd n     = 1 : concat (replicate (m `div` 2) [-1,1])
             | otherwise = concat (replicate (m `div` 2) [-1,1])
      m = fromIntegral n
 
-- factoriales es la lista de los factoriales. Por ejemplo,
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]
 
-- 3ª definición
-- -------------
 
sumaAlterna3 :: Integer -> Integer
sumaAlterna3 n = 
    sum (genericTake n (zipWith (*) signos (tail factoriales)))
    where signos | odd n     = cycle [1,-1]
                 | otherwise = cycle [-1,1]
 
-- Comparación de eficiencia
-- -------------------------
 
--    λ> sumaAlterna1 3000 `mod` (10^6)
--    577019
--    (5.33 secs, 7,025,937,760 bytes)
--    λ> sumaAlterna2 3000 `mod` (10^6)
--    577019
--    (0.03 secs, 15,738,480 bytes)
--    λ> sumaAlterna3 3000 `mod` (10^6)
--    577019
--    (0.05 secs, 16,520,896 bytes)
 
-- En lo que sigue se usa la 2ª definición
sumaAlterna :: Integer -> Integer
sumaAlterna = sumaAlterna2
 
sumasAlternas                                                    --
=============
 
-- 1ª definición
-- -------------
 
sumasAlternas1 :: [Integer]
sumasAlternas1 = [sumaAlterna n | n <- [0..]]
 
-- 2ª definición
-- -------------
 
sumasAlternas2 :: [Integer]
sumasAlternas2 = 0 : zipWith (-) (tail factoriales) sumasAlternas2
 
Definiciones de conSumaAlternaPrima
===================================
 
-- 1ª definición
-- -------------
 
conSumaAlternaPrima1 :: [Integer]
conSumaAlternaPrima1 =
    [n | n <- [0..], isPrime (sumaAlterna n)]
 
-- 2ª definición
-- -------------
 
conSumaAlternaPrima2 :: [Integer]
conSumaAlternaPrima2 =
    [x | (x,y) <- zip [0..] sumasAlternas2, isPrime y]

Pensamiento

¡Fiat umbra! Brotó el pensar humano.
Y el huevo universal alzó, vacío,
ya sin color, desustanciado y frío.

Antonio Machado

Mayor semiprimo menor que n

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2 x 13) y 49 también lo es (porque 49 = 7 x 7).

Definir la función

   mayorSemiprimoMenor :: Integer -> Integer

tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,

   mayorSemiprimoMenor 27      ==  26
   mayorSemiprimoMenor 50      ==  49
   mayorSemiprimoMenor 49      ==  46
   mayorSemiprimoMenor (10^6)  ==  999997

Soluciones

import Data.Numbers.Primes 
 
-- 1ª definición
-- =============
 
mayorSemiprimoMenor :: Integer -> Integer
mayorSemiprimoMenor n =
    head [x | x <- [n-1,n-2..2], semiPrimo x]
 
semiPrimo :: Integer -> Bool
semiPrimo n =
    not (null [x | x <- [n,n-1..2], 
                   primo x,
                   n `mod` x == 0,
                   primo (n `div` x)])
 
primo :: Integer -> Bool
primo n = [x | x <- [1..n], n `mod` x == 0] == [1,n] 
 
-- 2ª definición
-- =============
 
mayorSemiprimoMenor2 :: Integer -> Integer
mayorSemiprimoMenor2 n =
    head [x | x <- [n-1,n-2..2], semiPrimo2 x]
 
semiPrimo2 :: Integer -> Bool
semiPrimo2 n =
    not (null [x | x <- [n-1,n-2..2], 
                   isPrime x,
                   n `mod` x == 0,
                   isPrime (n `div` x)])
 
-- 3ª definición
-- =============
 
mayorSemiprimoMenor3 :: Integer -> Integer
mayorSemiprimoMenor3 n =
    head [x | x <- [n-1,n-2..2], semiPrimo3 x]
 
semiPrimo3 :: Integer -> Bool
semiPrimo3 n =
    not (null [x | x <- reverse (takeWhile (<n) primes),
                   n `mod` x == 0,
                   isPrime (n `div` x)])
 
-- 4ª solución
mayorSemiprimoMenor4 :: Integer -> Integer
mayorSemiprimoMenor4 n = head [ p | p <- [n-1,n-2..2]
                                  , (length . primeFactors) p == 2]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> mayorSemiprimoMenor 2000
--    1994
--    (2.32 secs, 329,036,016 bytes)
--    λ> mayorSemiprimoMenor2 2000
--    1994
--    (0.13 secs, 81,733,304 bytes)
--    λ> mayorSemiprimoMenor3 2000
--    1994
--    (0.02 secs, 0 bytes)
--    λ> mayorSemiprimoMenor4 2000
--    1994
--    (0.01 secs, 0 bytes)
--    
--    λ> mayorSemiprimoMenor3 300000
--    299995
--    (1.16 secs, 484,484,632 bytes)
--    λ> mayorSemiprimoMenor4 300000
--    299995
--    (0.01 secs, 0 bytes)

Pensamiento

El ser y el pensar (el pensar homogeneizador) no coinciden ni por casualidad.

Antonio Machado

Sumas de 4 primos

La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo número par mayor que 2 es la suma de dos números primos. Ambos problemas ha estado abiertos durante más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función

   suma4primos :: Integer -> (Integer,Integer,Integer,Integer)

tal que (suma4primos n) es una cuádrupla (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,

   suma4primos 24             ==  (2,2,3,17)
   suma4primos 1234567890123  ==  (2,3,29,1234567890089)

Comprobar con QuickCheck que suma4primos es correcta; es decir si (suma4primos n) es (a,b,c,d) entonces los números a, b c y d son primos y su suma es n.

Nota: Para cada n pueden existir distintas cuádruplas que cumplan la especificación. Por ejemplo, para el 16 hay tres: (2,2,5,7), (3,3,3,7) y (3,3,5,5). Cualquiera de ellas se admite como solución.

Soluciones

import Data.Numbers.Primes (isPrime, primes)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
suma4primos1 :: Integer -> (Integer, Integer, Integer, Integer)
suma4primos1 n = 
    head[(a,b,c,d) | let as = takeWhile (<n) primes,
                     a <- as,
                     let bs = takeWhile (<n-a) as,
                     b <- bs,
                     let cs = takeWhile (<n-a-b) bs,
                     c <- cs,
                     let d = n-a-b-c,
                     isPrime d]
 
-- 2ª solución
-- ===========
 
suma4primos2 :: Integer -> (Integer,Integer,Integer,Integer)
suma4primos2 n | even n    = (2,2,a,b)
               | otherwise = (2,3,c,d)
               where (a,b) = head (sumas2primos (n-4))
                     (c,d) = head (sumas2primos (n-5))
 
sumas2primos :: Integer -> [(Integer,Integer)]
sumas2primos n = [(x,y) | x <- takeWhile (<n) primes,
                          let y = n-x,
                          x <= y,
                          isPrime y]
 
-- Verificación                                                     --
-- ============
 
-- La propiedad es
prop_suma4primos :: Integer -> Property
prop_suma4primos n =
    n > 7 ==> a+b+c+d == n && all isPrime [a,b,c,d]
    where (a,b,c,d) = suma4primos2 n
 
-- La comprobación es
--    ghci> quickCheck prop_suma4primos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia                                        --
-- =========================
 
-- La comparación es
--    ghci> suma4primos1 10000000
--    (2,2,5,9999991)
--    (9.66 secs, 4346086952 bytes)
--    
--    ghci> suma4primos2 10000000
--    (2,2,5,9999991)
--    (0.01 secs, 2099888 bytes)

Pensamiento

A la hora del rocío,
de la niebla salen
sierra blanca y prado verde.
¡El sol en los encinares.!

Antonio Machado

Variación de la conjetura de Goldbach.

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

   sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
   conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
   noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

  • (sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,
   sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
   sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
   sumas3PrimosDistintos 10  ==  [(5,3,2)]
   sumas3PrimosDistintos 11  ==  []
  • (conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,
   conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
   conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
   conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
   conKsumas3PrimosDistintos 0 99  ==  [11,13,17]
  • (noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,
   noSonSumas3PrimosDistintos 99   ==  [11,13,17]
   noSonSumas3PrimosDistintos 500  ==  [11,13,17]

Soluciones

import Data.Numbers.Primes
 
sumas3PrimosDistintos :: Int -> [(Int,Int,Int)]
sumas3PrimosDistintos n =
  [(a,b,c) | a <- takeWhile (<=n-5) primes
           , b <- takeWhile (<a) primes
           , let c = n - a - b
           , c < b
           , isPrime c]
 
conKsumas3PrimosDistintos :: Int -> Int -> [Int]
conKsumas3PrimosDistintos k n =
  [x | x <- [10..n]
     , length (sumas3PrimosDistintos x) == k]
 
noSonSumas3PrimosDistintos :: Int -> [Int]
noSonSumas3PrimosDistintos = conKsumas3PrimosDistintos 0

Pensamiento

En su claro verso
se canta y medita
sin grito ni ceño.

Antonio Machado

El 2019 es semiprimo

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2×13) y 49 también lo es (porque 49 = 7×7).

Definir las funciones

   esSemiprimo :: Integer -> Bool
   semiprimos  :: [Integer]

tales que

  • (esSemiprimo n) se verifica si n es semiprimo. Por ejemplo,
     esSemiprimo 26          ==  True
     esSemiprimo 49          ==  True
     esSemiprimo 8           ==  False
     esSemiprimo 2019        ==  True
     esSemiprimo (21+10^14)  ==  True
  • semiprimos es la sucesión de números semiprimos. Por ejemplo,
     take 10 semiprimos   ==  [4,6,9,10,14,15,21,22,25,26]
     semiprimos !! 579    ==  2019
     semiprimos !! 10000  ==  40886

Soluciones

import Data.Numbers.Primes 
import Test.QuickCheck
 
-- 1ª definición de esSemiprimo
-- ============================
 
esSemiprimo :: Integer -> Bool
esSemiprimo n =
  not (null [x | x <- [n,n-1..2], 
                 primo x,
                 n `mod` x == 0,
                 primo (n `div` x)])
 
primo :: Integer -> Bool
primo n = [x | x <- [1..n], n `mod` x == 0] == [1,n] 
 
-- 2ª definición de esSemiprimo
-- ============================
 
esSemiprimo2 :: Integer -> Bool
esSemiprimo2 n =
  not (null [x | x <- [n-1,n-2..2], 
                 isPrime x,
                 n `mod` x == 0,
                 isPrime (n `div` x)])
 
-- 3ª definición de esSemiprimo
-- ============================
 
esSemiprimo3 :: Integer -> Bool
esSemiprimo3 n =
  not (null [x | x <- reverse (takeWhile (<n) primes),
                 n `mod` x == 0,
                 isPrime (n `div` x)])
 
-- 4ª definición de esSemiprimo
-- ============================
 
esSemiprimo4 :: Integer -> Bool
esSemiprimo4 n =
  length (primeFactors n) == 2
 
-- Equivalencia de las definiciones de esSemiprimo
-- ===============================================
 
-- La propiedad es
prop_esSemiprimo :: Positive Integer -> Bool
prop_esSemiprimo (Positive n) =
  all (== esSemiprimo n) [f n | f <- [ esSemiprimo2
                                     , esSemiprimo3
                                     , esSemiprimo4
                                     ]]
 
-- La comprobación es
--    λ> quickCheck prop_esSemiprimo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> esSemiprimo 5001
--    True
--    (1.90 secs, 274,450,648 bytes)
--    λ> esSemiprimo2 5001
--    True
--    (0.07 secs, 29,377,016 bytes)
--    λ> esSemiprimo3 5001
--    True
--    (0.01 secs, 1,706,840 bytes)
--    λ> esSemiprimo4 5001
--    True
--    (0.01 secs, 142,840 bytes)
--    
--    λ> esSemiprimo2 100001
--    True
--    (2.74 secs, 1,473,519,064 bytes)
--    λ> esSemiprimo3 100001
--    True
--    (0.09 secs, 30,650,352 bytes)
--    λ> esSemiprimo4 100001
--    True
--    (0.01 secs, 155,200 bytes)
--    
--    λ> esSemiprimo3 10000001
--    True
--    (8.73 secs, 4,357,875,016 bytes)
--    λ> esSemiprimo4 10000001
--    True
--    (0.01 secs, 456,328 bytes)
 
-- Definición de semiprimos
-- ========================
 
semiprimos :: [Integer]
semiprimos = filter esSemiprimo4 [4..]

Pensamiento

Porque toda visión requiere distancia, no hay manera de ver las cosas sin salirse de ellas.

Antonio Machado