ceiling

La menos conocida de las conjeturas de Goldbach

PorJosé A. Alonso 7-febrero-202017-febrero-2020

Goldbach, el de la famosa conjetura, hizo por lo menos otra conjetura que finalmente resultó ser falsa.

Esta última decía que todo número compuesto impar puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Así por ejemplo,

    9 =  7 + 2×1^2
   15 =  7 + 2×2^2
   21 =  3 + 2×3^2
   25 =  7 + 2×3^2
   27 = 19 + 2×2^2
   33 = 31 + 2×1^2

9 = 7 + 2×1^2

15 = 7 + 2×2^2

21 = 3 + 2×3^2

25 = 7 + 2×3^2

27 = 19 + 2×2^2

33 = 31 + 2×1^2

Definir las sucesiones

   imparesCompuestos :: [Integer]
   descomposiciones :: Integer -> [(Integer,Integer)]
   contraejemplosGoldbach :: [Integer]

imparesCompuestos :: [Integer]

descomposiciones :: Integer -> [(Integer,Integer)]

contraejemplosGoldbach :: [Integer]

tales que

imparesCompuestos es la lista de los números impares compuestos. Por ejemplo,

     take 9 imparesCompuestos  ==  [9,15,21,25,27,33,35,39,45]

1	take 9 imparesCompuestos == [9,15,21,25,27,33,35,39,45]

(descomposiciones n) es la lista de las descomposiciones de n de n como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,

     descomposiciones 9     ==  [(7,1)]
     descomposiciones 21    ==  [(3,9),(13,4),(19,1)]
     descomposiciones 5777  ==  []

descomposiciones 9 == [(7,1)]

descomposiciones 21 == [(3,9),(13,4),(19,1)]

descomposiciones 5777 == []

Las 3 descomposiciones de 21 son

     21 =  3 + 2*9 = 21 + 2*3^2
     21 = 13 + 2*4 = 13 + 2*3^2
     21 = 19 + 2*1 = 19 + 2*1^2

21 = 3 + 2*9 = 21 + 2*3^2

21 = 13 + 2*4 = 13 + 2*3^2

21 = 19 + 2*1 = 19 + 2*1^2

contraejemplosGoldbach es la lista de los contraejemplos de la anterior conjetura de Goldbach; es decir, los números impares compuestos que no pueden expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,

   take 2 contraejemplosGoldbach  ==  [5777,5993]

1	take 2 contraejemplosGoldbach == [5777,5993]

Comprobar con QuickCheck que la conjetura de Golbach se verifica a partir de 5993; es decir, todo número compuesto impar mayor que 5993 puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado.

Nota: Basado en el artículo La menos conocida de las conjeturas de Goldbach de Claudio Meller en el blog Números y algo más.

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

imparesCompuestos :: [Integer]
imparesCompuestos = filter esCompuesto [3,5..]

-- (esCompuesto x) se verifica si x es un número compuesto. Por ejemplo,
--    esCompuesto 6  ==  True
--    esCompuesto 7  ==  False
esCompuesto :: Integer -> Bool
esCompuesto = not . isPrime

contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach = filter esContraejemplo imparesCompuestos

-- (esContraejemplo x) es verifica si el número impar compuesto x es un
-- contraejemplo de la conjetura de Goldbach. Por ejemplo,
--    esContraejemplo 5777  ==  True
--    esContraejemplo 15    ==  False
esContraejemplo :: Integer -> Bool
esContraejemplo = null . descomposiciones

descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(p,x) | p <- takeWhile (<=n) primes
         , (n - p) `mod` 2 == 0
         , let x = (n - p) `div` 2
         , esCuadrado x]

-- (esCuadrado x) es verifica si x es un cuadrado perfecto. Por ejemplo, 
--    esCuadrado 16  ==  True
--    esCuadrado 27  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = y^2 == x
  where y = ceiling (sqrt (fromIntegral x))

-- La propiedad es
prop_conjetura :: Int -> Property
prop_conjetura n =
  n >= 0 ==> not (esContraejemplo (imparesCompuestosMayore5993 !! n))
  where imparesCompuestosMayore5993 = dropWhile (<=5993) imparesCompuestos

-- La comprobación es
--    λ> quickCheck prop_conjetura
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes

import Test.QuickCheck

imparesCompuestos :: [Integer]

imparesCompuestos = filter esCompuesto [3,5..]

-- (esCompuesto x) se verifica si x es un número compuesto. Por ejemplo,

-- esCompuesto 6 == True

-- esCompuesto 7 == False

esCompuesto :: Integer -> Bool

esCompuesto = not . isPrime

contraejemplosGoldbach :: [Integer]

contraejemplosGoldbach = filter esContraejemplo imparesCompuestos

-- (esContraejemplo x) es verifica si el número impar compuesto x es un

-- contraejemplo de la conjetura de Goldbach. Por ejemplo,

-- esContraejemplo 5777 == True

-- esContraejemplo 15 == False

esContraejemplo :: Integer -> Bool

esContraejemplo = null . descomposiciones

descomposiciones :: Integer -> [(Integer,Integer)]

descomposiciones n =

[(p,x) | p <- takeWhile (<=n) primes

, (n - p) `mod` 2 == 0

, let x = (n - p) `div` 2

, esCuadrado x]

-- (esCuadrado x) es verifica si x es un cuadrado perfecto. Por ejemplo,

-- esCuadrado 16 == True

-- esCuadrado 27 == False

esCuadrado :: Integer -> Bool

esCuadrado x = y^2 == x

where y = ceiling (sqrt (fromIntegral x))

-- La propiedad es

prop_conjetura :: Int -> Property

prop_conjetura n =

n >= 0 ==> not (esContraejemplo (imparesCompuestosMayore5993 !! n))

where imparesCompuestosMayore5993 = dropWhile (<=5993) imparesCompuestos

-- La comprobación es

-- λ> quickCheck prop_conjetura

-- +++ OK, passed 100 tests.

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«Obvio es la palabra más peligrosa de las matemáticas.»

Eric Temple Bell

Entre dos potencias sucesivas

PorJosé A. Alonso 3-febrero-202010-febrero-2020

Se dice que un número entero está entre potencias sucesivas de n si x-1 es una potencia n-ésima y x+1 es una potencia (n+1)-ésima; es decir, si existen a y b tales que x-1 es a^n y x+1 es b^(n+1). Por ejemplo,

 2 está entre potencias sucesivas de 0, ya que  1 =  1^0 y  3 = 3^1
15 está entre potencias sucesivas de 1, ya que 14 = 14^1 y 16 = 4^2
26 está entre potencias sucesivas de 2, ya que 25 =  5^2 y 27 = 3^3

2 está entre potencias sucesivas de 0, ya que 1 = 1^0 y 3 = 3^1

15 está entre potencias sucesivas de 1, ya que 14 = 14^1 y 16 = 4^2

26 está entre potencias sucesivas de 2, ya que 25 = 5^2 y 27 = 3^3

Definir las funciones

   entrePotencias :: Integer -> Integer -> Bool
   pares :: [(Integer,Integer)]
   paresEntrePotencias :: [(Integer,Integer)]

entrePotencias :: Integer -> Integer -> Bool

pares :: [(Integer,Integer)]

paresEntrePotencias :: [(Integer,Integer)]

tales que

(entrePotencias n x) se verifica si x está entre potencias sucesivas de n. Por ejemplo,

     entrePotencias 0 2   ==  True
     entrePotencias 1 15  ==  True
     entrePotencias 2 26  ==  True

entrePotencias 0 2 == True

entrePotencias 1 15 == True

entrePotencias 2 26 == True

pares es la lista de los números enteros ordenados por su suma y primer elemento. Por ejemplo,

     λ> take 11 pares
     [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4)]

1 2	λ> take 11 pares [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4)]

paresEntrePotencias es la lista de los pares (n,x) tales que x está entre potencias sucesivas de n. Por ejemplo,

     λ> take 10 paresEntrePotencias
     [(1,0),(0,2),(1,3),(1,8),(1,15),(1,24),(2,26),(1,35),(1,48),(1,63)]

1 2	λ> take 10 paresEntrePotencias [(1,0),(0,2),(1,3),(1,8),(1,15),(1,24),(2,26),(1,35),(1,48),(1,63)]

Comprobar con QuickCheck que 26 es el único número que está entre potencias sucesivas con exponentes mayor que 1; es decir, que el único par (n,x) tal que x está entre potencias sucesivas de n con n mayor que uno es el (2,26).

Nota: Este ejercicio ha sido propuesto por Rebeca Isabel González Gordillo y está basado en el artículo El número 26 … ¡un número especial! de Amadeo Artacho en MatematicasCercanas.

Soluciones

import Test.QuickCheck

entrePotencias :: Integer -> Integer -> Bool
entrePotencias n x = esPotencia n (x-1) && esPotencia (n+1) (x+1)

-- (esPotencia n x) se verifica si x es una potencia n-ésima. Por
-- ejemplo, 
--    esPotencia 3 27  ==  True
--    esPotencia 3 25  ==  False
esPotencia :: Integer -> Integer -> Bool
esPotencia n x = x == r^n
  where r = ceiling ((fromIntegral x)**(1/fromIntegral n))

pares :: [(Integer,Integer)]
pares = [(x,n-x) | n <- [0..], x <- [0..n]]

paresEntrePotencias :: [(Integer,Integer)]
paresEntrePotencias =
  [(n,x) | (n,x) <- pares
         , entrePotencias n x]

prop_entrePotencias :: Integer -> Integer -> Property
prop_entrePotencias n x =
  n > 1 ==> entrePotencias n x == ((n,x) == (2,26))

-- La comprobación es
--    λ> quickCheck prop_entrePotencias
--    +++ OK, passed 100 tests.

import Test.QuickCheck

entrePotencias :: Integer -> Integer -> Bool

entrePotencias n x = esPotencia n (x-1) && esPotencia (n+1) (x+1)

-- (esPotencia n x) se verifica si x es una potencia n-ésima. Por

-- ejemplo,

-- esPotencia 3 27 == True

-- esPotencia 3 25 == False

esPotencia :: Integer -> Integer -> Bool

esPotencia n x = x == r^n

where r = ceiling ((fromIntegral x)**(1/fromIntegral n))

pares :: [(Integer,Integer)]

pares = [(x,n-x) | n <- [0..], x <- [0..n]]

paresEntrePotencias :: [(Integer,Integer)]

paresEntrePotencias =

[(n,x) | (n,x) <- pares

, entrePotencias n x]

prop_entrePotencias :: Integer -> Integer -> Property

prop_entrePotencias n x =

n > 1 ==> entrePotencias n x == ((n,x) == (2,26))

-- La comprobación es

-- λ> quickCheck prop_entrePotencias

-- +++ OK, passed 100 tests.

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«El verdadero objetivo de la ciencia es el honor de la mente humana.»

Carl Gustav Jacob Jacobi

La conjetura de Mertens

PorJosé A. Alonso 27-enero-20203-febrero-2020

Un número entero n es libre de cuadrados si no existe un número primo p tal que p² divide a n; es decir, los factores primos de n son todos distintos.

La función de Möbius μ(n) está definida para todos los enteros positivos como sigue:

μ(n) = 1 si n es libre de cuadrados y tiene un número par de factores primos.
μ(n) = -1 si n es libre de cuadrados y tiene un número impar de factores primos.
μ(n) = 0 si n no es libre de cuadrados.

Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, …

La función de Mertens M(n) está definida para todos los enteros positivos como la suma de μ(k) para 1 ≤ k ≤ n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, …

La conjetura de Mertens afirma que

Para todo entero x mayor que 1, el valor absoluto de la función de Mertens en x es menor que la raíz cuadrada de x.

La conjetura fue planteada por Franz Mertens en 1897. Riele Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta más o menos a partir de $10^{10^{64}}$ , cifra que luego de algunos refinamientos se redujo a $10^{10^{40}}$ .

Definir las funciones

   mobius :: Integer -> Integer
   mertens :: Integer -> Integer
   graficaMertens :: Integer -> IO ()

mobius :: Integer -> Integer

mertens :: Integer -> Integer

graficaMertens :: Integer -> IO ()

tales que

(mobius n) es el valor de la función de Möbius en n. Por ejemplo,

     mobius 6   ==  1
     mobius 30  ==  -1
     mobius 12  ==  0

mobius 6 == 1

mobius 30 == -1

mobius 12 == 0

(mertens n) es el valor de la función de Mertens en n. Por ejemplo,

     mertens 1     ==  1
     mertens 2     ==  0
     mertens 3     ==  -1
     mertens 5     ==  -2
     mertens 661   ==  -11
     mertens 1403  ==  11

mertens 1 == 1

mertens 2 == 0

mertens 3 == -1

mertens 5 == -2

mertens 661 == -11

mertens 1403 == 11

(graficaMertens n) dibuja la gráfica de la función de Mertens, la raíz cuadrada y el opuestos de la raíz cuadrada para los n primeros n enteros positivos. Por ejemplo, (graficaMertens 1000) dibuja

Comprobar con QuickCheck la conjetura de Mertens.

Nota: El ejercicio está basado en La conjetura de Merterns y su relación con un número tan raro como extremada y colosalmente grande publicado por @Alvy la semana pasada en Microsiervos.

Soluciones

import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck
import Graphics.Gnuplot.Simple

mobius :: Integer -> Integer
mobius n | tieneRepetidos xs = 0
         | otherwise         = (-1)^(length xs)
  where xs = primeFactors n

tieneRepetidos :: [Integer] -> Bool
tieneRepetidos xs =
  or [x == y | (x,y) <- zip xs (tail xs)]
        
mertens :: Integer -> Integer
mertens n = sum (map mobius [1..n])

-- Definición de graficaMertens
-- ============================

graficaMertens :: Integer -> IO ()
graficaMertens n = do
  plotLists [ Key Nothing
            , Title "Conjetura de Mertens"
            , PNG "La_conjetura_de_Mertens.png"
            ]
            [ [mertens k | k <- [1..n]]
            , raices
            , map negate raices
            ]
    
  where
    raices = [ceiling (sqrt k) | k <- [1..fromIntegral n]]

-- Conjetura de Mertens
-- ====================

-- La conjetura es
conjeturaDeMertens :: Integer -> Property
conjeturaDeMertens n =
  n > 1
  ==>
  abs (mertens n) < ceiling (sqrt n')
  where n' = fromIntegral n

-- La comprobación es
--    λ> quickCheck conjeturaDeMertens
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

import Graphics.Gnuplot.Simple

mobius :: Integer -> Integer

mobius n | tieneRepetidos xs = 0

| otherwise = (-1)^(length xs)

where xs = primeFactors n

tieneRepetidos :: [Integer] -> Bool

tieneRepetidos xs =

or [x == y | (x,y) <- zip xs (tail xs)]

mertens :: Integer -> Integer

mertens n = sum (map mobius [1..n])

-- Definición de graficaMertens

-- ============================

graficaMertens :: Integer -> IO ()

graficaMertens n = do

plotLists [ Key Nothing

, Title "Conjetura de Mertens"

, PNG "La_conjetura_de_Mertens.png"

]

[ [mertens k | k <- [1..n]]

, raices

, map negate raices

]

where

raices = [ceiling (sqrt k) | k <- [1..fromIntegral n]]

-- Conjetura de Mertens

-- ====================

-- La conjetura es

conjeturaDeMertens :: Integer -> Property

conjeturaDeMertens n =

n > 1

==>

abs (mertens n) < ceiling (sqrt n')

where n' = fromIntegral n

-- La comprobación es

-- λ> quickCheck conjeturaDeMertens

-- +++ OK, passed 100 tests.

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«El control de la complejidad es la esencia de la programación informática.»

Brian Kernighan.

Teorema de existencia de divisores

PorJosé A. Alonso 10-enero-20206-junio-2022

El teorema de existencia de divisores afirma que

En cualquier subconjunto de {1, 2, …, 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.

Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,…,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,…,6} con más de 3 elementos.

Definir las funciones

   divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
   esMayoritario :: [Integer] -> Bool

1 2	divisoresMultiplos :: [Integer] -> [(Integer,Integer)] esMayoritario :: [Integer] -> Bool

tales que

(divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,

     divisoresMultiplos [2,3,5,6]  ==  [(2,6),(3,6)]
     divisoresMultiplos [2,3,5]    ==  []
     divisoresMultiplos [4..8]     ==  [(4,8)]

divisoresMultiplos [2,3,5,6] == [(2,6),(3,6)]

divisoresMultiplos [2,3,5] == []

divisoresMultiplos [4..8] == [(4,8)]

(esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,

     esMayoritario [2,3,5,6]  ==  True
     esMayoritario [2,3,5]    ==  False

1 2	esMayoritario [2,3,5,6] == True esMayoritario [2,3,5] == False

Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios

   mayoritario :: Gen [Integer]
   mayoritario = do
     m' <- arbitrary
     let m = 1 + abs m'
     xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
     return xs'

mayoritario :: Gen [Integer]

mayoritario = do

m' <- arbitrary

let m = 1 + abs m'

xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)

return xs'

con lo que la propiedad que hay que comprobar con QuickCheck es

   teorema_de_existencia_de_divisores :: Property
   teorema_de_existencia_de_divisores =
     forAll mayoritario (not . null . divisoresMultiplos)

teorema_de_existencia_de_divisores :: Property

teorema_de_existencia_de_divisores =

forAll mayoritario (not . null . divisoresMultiplos)

Soluciones

import Data.List (genericLength)
import Test.QuickCheck

divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
divisoresMultiplos xs =
  [(x,y) | x <- xs
         , y <- xs
         , y /= x
         , y `mod` x == 0]

esMayoritario :: [Integer] -> Bool
esMayoritario xs =
  not (null xs) && length xs > ceiling (n / 2) 
  where n = fromIntegral (maximum xs)

-- Comprobación del teorema
-- ========================

-- La propiedad es
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
  forAll mayoritario (not . null . divisoresMultiplos)

-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo, 
--    λ> sample mayoritario
--    [1,2]
--    [2,5,7,8]
--    [1,2,8,10,14]
--    [3,8,11,12,13,15,18,19,22,23,25,26]
--    [1,3,4,6]
--    [3,6,9,11,12,14,17,19]
mayoritario :: Gen [Integer]
mayoritario = do
  m' <- arbitrary
  let m = 1 + abs m'
  xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
  return xs'

-- La comprobación es
--    λ> quickCheck teorema_de_existencia_de_divisores
--    +++ OK, passed 100 tests.

import Data.List (genericLength)

import Test.QuickCheck

divisoresMultiplos :: [Integer] -> [(Integer,Integer)]

divisoresMultiplos xs =

[(x,y) | x <- xs

, y <- xs

, y /= x

, y `mod` x == 0]

esMayoritario :: [Integer] -> Bool

esMayoritario xs =

not (null xs) && length xs > ceiling (n / 2)

where n = fromIntegral (maximum xs)

-- Comprobación del teorema

-- ========================

-- La propiedad es

teorema_de_existencia_de_divisores :: Property

teorema_de_existencia_de_divisores =

forAll mayoritario (not . null . divisoresMultiplos)

-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo,

-- λ> sample mayoritario

-- [1,2]

-- [2,5,7,8]

-- [1,2,8,10,14]

-- [3,8,11,12,13,15,18,19,22,23,25,26]

-- [1,3,4,6]

-- [3,6,9,11,12,14,17,19]

mayoritario :: Gen [Integer]

mayoritario = do

m' <- arbitrary

let m = 1 + abs m'

xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)

return xs'

-- La comprobación es

-- λ> quickCheck teorema_de_existencia_de_divisores

-- +++ OK, passed 100 tests.

Pensamiento

Guiomar, Guiomar,
mírame en ti castigado:
reo de haberte creado,
ya no te puedo olvidar.

Antonio Machado

Suma de primos menores

PorJosé A. Alonso 9-diciembre-201917-diciembre-2019

La suma de los primos menores que 10 es 2 + 3 + 5 + 7 = 17.

Definir la función

   sumaPrimosMenores :: Integer -> Integer

1	sumaPrimosMenores :: Integer -> Integer

tal que (sumaPrimosMenores n) es la suma de los primos menores que n. Por ejemplo,

   sumaPrimosMenores 10        ==  17
   sumaPrimosMenores (5*10^5)  ==  9914236195

1 2	sumaPrimosMenores 10 == 17 sumaPrimosMenores (5*10^5) == 9914236195

Nota: Este ejercicio está basado en el problema 10 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primes)

-- 1ª solución
-- ===========

sumaPrimosMenores :: Integer -> Integer
sumaPrimosMenores n = sum (takeWhile (<n) primos)

-- primos es la lista de los números primos. Por ejemplo,
--    λ> take 12 primos
--    [2,3,5,7,11,13,17,19,23,29,31,37]
primos :: [Integer]
primos = 2 : filter esPrimo [3,5..]

esPrimo :: Integer -> Bool
esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n]
                    , n `mod` x == 0]

-- 2ª solución
-- ===========

sumaPrimosMenores2 :: Integer -> Integer
sumaPrimosMenores2 n = sum (takeWhile (<n) primos2)

primos2 :: [Integer]
primos2 = 2 : filter esPrimo2 [3,5..]
 
esPrimo2 :: Integer -> Bool
esPrimo2 x =
  all ((/= 0) . mod x)
  (takeWhile (<= floor (sqrt (fromIntegral x))) primos2)

-- 3ª solución
-- ===========

sumaPrimosMenores3 :: Integer -> Integer
sumaPrimosMenores3 n = sum (takeWhile (<n) primes)

-- Comparación de eficiencia
-- =========================

--    λ> sumaPrimosMenores (2*10^5)
--    1709600813
--    (2.56 secs, 1,522,015,240 bytes)
--    λ> sumaPrimosMenores2 (2*10^5)
--    1709600813
--    (0.56 secs, 376,951,456 bytes)
--    λ> sumaPrimosMenores3 (2*10^5)
--    1709600813
--    (0.07 secs, 62,321,888 bytes)

import Data.Numbers.Primes (primes)

-- 1ª solución

-- ===========

sumaPrimosMenores :: Integer -> Integer

sumaPrimosMenores n = sum (takeWhile (<n) primos)

-- primos es la lista de los números primos. Por ejemplo,

-- λ> take 12 primos

-- [2,3,5,7,11,13,17,19,23,29,31,37]

primos :: [Integer]

primos = 2 : filter esPrimo [3,5..]

esPrimo :: Integer -> Bool

esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n]

, n `mod` x == 0]

-- 2ª solución

-- ===========

sumaPrimosMenores2 :: Integer -> Integer

sumaPrimosMenores2 n = sum (takeWhile (<n) primos2)

primos2 :: [Integer]

primos2 = 2 : filter esPrimo2 [3,5..]

esPrimo2 :: Integer -> Bool

esPrimo2 x =

all ((/= 0) . mod x)

(takeWhile (<= floor (sqrt (fromIntegral x))) primos2)

-- 3ª solución

-- ===========

sumaPrimosMenores3 :: Integer -> Integer

sumaPrimosMenores3 n = sum (takeWhile (<n) primes)

-- Comparación de eficiencia

-- =========================

-- λ> sumaPrimosMenores (2*10^5)

-- 1709600813

-- (2.56 secs, 1,522,015,240 bytes)

-- λ> sumaPrimosMenores2 (2*10^5)

-- 1709600813

-- (0.56 secs, 376,951,456 bytes)

-- λ> sumaPrimosMenores3 (2*10^5)

-- 1709600813

-- (0.07 secs, 62,321,888 bytes)

Pensamiento

El movimiento no es nada esencial. La fuerza puede ser inmóvil (lo es en su estado de pureza); mas no por ello deja de ser activa.

Antonio Machado

Mayor divisor primo

PorJosé A. Alonso 26-noviembre-20193-diciembre-2019

Los divisores primos de 13195 son 5, 7, 13 y 29. Por tanto, el mayor divisor primo de 13195 es 29.

Definir la función

   mayorDivisorPrimo :: Integer -> Integer

1	mayorDivisorPrimo :: Integer -> Integer

tal que (mayorDivisorPrimo n) es el mayor divisor primo de n. Por ejemplo,

   mayorDivisorPrimo 13195            ==  29
   mayorDivisorPrimo 152416333181401  ==  12345701

1 2	mayorDivisorPrimo 13195 == 29 mayorDivisorPrimo 152416333181401 == 12345701

Nota: Este ejercicio está basado en el problema 3 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primeFactors)

-- 1ª solución  (sin librerías auxiliares)
-- =======================================

mayorDivisorPrimo :: Integer -> Integer
mayorDivisorPrimo = last . divisoresPrimos 

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por
-- ejemplo, 
--    divisoresPrimos 13195  ==  [5,7,13,29]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos 0 = []
divisoresPrimos 1 = []
divisoresPrimos n = m : divisoresPrimos (n `div` m)
  where m = menorDivisorPrimo n 

-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo, 
--    menorDivisorPrimo 24  ==  2
--    menorDivisorPrimo 25  ==  5
--    menorDivisorPrimo 29  ==  29
menorDivisorPrimo :: Integer -> Integer
menorDivisorPrimo x =
  head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]
          , x `mod` y == 0]

-- 2ª solución (con la librería Data.Numbers.Primes)
-- =================================================

mayorDivisorPrimo2 :: Integer -> Integer
mayorDivisorPrimo2 = last . primeFactors

-- Comparación de eficiencia
-- =========================

--   λ> mayorDivisorPrimo 152416333181401
--   12345701
--   (1.96 secs, 1,630,201,856 bytes)
--   λ> mayorDivisorPrimo2 152416333181401
--   12345701
--   (2.01 secs, 5,445,284,432 bytes)

import Data.Numbers.Primes (primeFactors)

-- 1ª solución (sin librerías auxiliares)

-- =======================================

mayorDivisorPrimo :: Integer -> Integer

mayorDivisorPrimo = last . divisoresPrimos

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por

-- ejemplo,

-- divisoresPrimos 13195 == [5,7,13,29]

divisoresPrimos :: Integer -> [Integer]

divisoresPrimos 0 = []

divisoresPrimos 1 = []

divisoresPrimos n = m : divisoresPrimos (n `div` m)

where m = menorDivisorPrimo n

-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo,

-- menorDivisorPrimo 24 == 2

-- menorDivisorPrimo 25 == 5

-- menorDivisorPrimo 29 == 29

menorDivisorPrimo :: Integer -> Integer

menorDivisorPrimo x =

head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]

, x `mod` y == 0]

-- 2ª solución (con la librería Data.Numbers.Primes)

-- =================================================

mayorDivisorPrimo2 :: Integer -> Integer

mayorDivisorPrimo2 = last . primeFactors

-- Comparación de eficiencia

-- =========================

-- λ> mayorDivisorPrimo 152416333181401

-- 12345701

-- (1.96 secs, 1,630,201,856 bytes)

-- λ> mayorDivisorPrimo2 152416333181401

-- 12345701

-- (2.01 secs, 5,445,284,432 bytes)

Pensamiento

«Un programa de ordenador es una demostración.» ~ Igor Rivin

Dígitos en las posiciones pares de cuadrados

PorJosé A. Alonso 1-febrero-20198-febrero-2019

Definir las funciones

   digitosPosParesCuadrado    :: Integer -> ([Integer],Int)
   invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

1 2	digitosPosParesCuadrado :: Integer -> ([Integer],Int) invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

tales que

(digitosPosParesCuadrado n) es el par formados por los dígitos de n² en la posiciones pares y por el número de dígitos de n². Por ejemplo,

     digitosPosParesCuadrado 8     ==  ([6],2)
     digitosPosParesCuadrado 14    ==  ([1,6],3)
     digitosPosParesCuadrado 36    ==  ([1,9],4)
     digitosPosParesCuadrado 116   ==  ([1,4,6],5)
     digitosPosParesCuadrado 2019  ==  ([4,7,3,1],7)

digitosPosParesCuadrado 8 == ([6],2)

digitosPosParesCuadrado 14 == ([1,6],3)

digitosPosParesCuadrado 36 == ([1,9],4)

digitosPosParesCuadrado 116 == ([1,4,6],5)

digitosPosParesCuadrado 2019 == ([4,7,3,1],7)

(invDigitosPosParesCuadrado (xs,k)) es la lista de los números n tales que xs es la lista de los dígitos de n² en la posiciones pares y k es el número de dígitos de n². Por ejemplo,

     invDigitosPosParesCuadrado ([6],2)             ==  [8]
     invDigitosPosParesCuadrado ([1,6],3)           ==  [14]
     invDigitosPosParesCuadrado ([1,9],4)           ==  [36]
     invDigitosPosParesCuadrado ([1,4,6],5)         ==  [116,136]
     invDigitosPosParesCuadrado ([4,7,3,1],7)       ==  [2019,2139,2231]
     invDigitosPosParesCuadrado ([1,2],3)           ==  []
     invDigitosPosParesCuadrado ([1,2],4)           ==  [32,35,39]
     invDigitosPosParesCuadrado ([1,2,3,4,5,6],11)  ==  [115256,127334,135254]

invDigitosPosParesCuadrado ([6],2) == [8]

invDigitosPosParesCuadrado ([1,6],3) == [14]

invDigitosPosParesCuadrado ([1,9],4) == [36]

invDigitosPosParesCuadrado ([1,4,6],5) == [116,136]

invDigitosPosParesCuadrado ([4,7,3,1],7) == [2019,2139,2231]

invDigitosPosParesCuadrado ([1,2],3) == []

invDigitosPosParesCuadrado ([1,2],4) == [32,35,39]

invDigitosPosParesCuadrado ([1,2,3,4,5,6],11) == [115256,127334,135254]

Comprobar con QuickCheck que para todo entero positivo n se verifica que para todo entero positivo m, m pertenece a (invDigitosPosParesCuadrado (digitosPosParesCuadrado n)) si, y sólo si, (digitosPosParesCuadrado m) es igual a (digitosPosParesCuadrado n)

Soluciones

import Test.QuickCheck

-- Definición de digitosPosParesCuadrado
-- =====================================

digitosPosParesCuadrado :: Integer -> ([Integer],Int)
digitosPosParesCuadrado n =
  (digitosPosPares (n^2),length (show (n^2)))

-- (digitosPosPares n) es la lista de los dígitos de n en posiciones
-- pares. Por ejemplo,
--    digitosPosPares 24012019  ==  [2,0,2,1]
digitosPosPares :: Integer -> [Integer]
digitosPosPares n = elementosPosPares (digitos n)

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]

-- (elementosPosPares xs) es la lista de los elementos de xs en
-- posiciones pares. Por ejemplo,
--    elementosPosPares [3,2,5,7,6,4]  ==  [3,5,6]
elementosPosPares :: [a] -> [a]
elementosPosPares []       = []
elementosPosPares [x]      = [x]
elementosPosPares (x:_:zs) = x : elementosPosPares zs

-- 1ª definición de invDigitosPosParesCuadrado
-- ========================================

invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]
invDigitosPosParesCuadrado (xs, a) =
  [x | x <- [ceiling (sqrt 10^(a-1))..ceiling (sqrt 10^a)]
     , digitosPosParesCuadrado x == (xs,a)]

-- 2ª definición de invDigitosPosParesCuadrado
-- ========================================

invDigitosPosParesCuadrado2 :: ([Integer],Int) -> [Integer]
invDigitosPosParesCuadrado2 x =
  [n | n <- [a..b], digitosPosParesCuadrado n == x]
  where a = floor (sqrt (fromIntegral (completaNum x 0)))
        b = ceiling (sqrt (fromIntegral (completaNum x 9)))

-- (completaNum (xs,k) n) es el número cuyos dígitos en las posiciones
-- pares son los de xs y los de las posiciones impares son iguales a n
-- (se supone que k es igual al doble de la longitud de xs o un
-- menos). Por ejemplo, 
--    completaNum ([1,3,8],5) 4  ==  14348
--    completaNum ([1,3,8],6) 4  ==  143484
completaNum :: ([Integer],Int) -> Integer -> Integer
completaNum x n = digitosAnumero (completa x n)

-- (completa (xs,k) n) es la lista cuyos elementos en las posiciones
-- pares son los de xs y los de las posiciones impares son iguales a n
-- (se supone que k es igual al doble de la longitud de xs o un
-- menos). Por ejemplo, 
--    completa ([1,3,8],5) 4  ==  [1,4,3,4,8]
--    completa ([1,3,8],6) 4  ==  [1,4,3,4,8,4]
completa :: ([Integer],Int) -> Integer -> [Integer]
completa (xs,k) n
  | even k    = ys
  | otherwise = init ys
  where ys = concat [[x,n] | x <- xs]

-- (digitosAnumero ds) es el número cuyos dígitos son ds. Por ejemplo,
--    digitosAnumero [2,0,1,9]  ==  2019
digitosAnumero :: [Integer] -> Integer
digitosAnumero = read . concatMap show

-- Comparación de eficiencia
-- =========================

--    λ> invDigitosPosParesCuadrado ([1,2,1,5,7,4,9],13)
--    [1106393,1234567,1314597]
--    (7.55 secs, 13,764,850,536 bytes)
--    λ> invDigitosPosParesCuadrado2 ([1,2,1,5,7,4,9],13)
--    [1106393,1234567,1314597]
--    (1.96 secs, 3,780,368,816 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es  
prop_digitosPosParesCuadrado :: Positive Integer -> Positive Integer -> Bool
prop_digitosPosParesCuadrado (Positive n) (Positive m) =
  (digitosPosParesCuadrado m == x)
  == (m `elem` invDigitosPosParesCuadrado x)
  where x = digitosPosParesCuadrado n

-- La comprobación es
--    λ> quickCheck prop_digitosPosParesCuadrado
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- Definición de digitosPosParesCuadrado

-- =====================================

digitosPosParesCuadrado :: Integer -> ([Integer],Int)

digitosPosParesCuadrado n =

(digitosPosPares (n^2),length (show (n^2)))

-- (digitosPosPares n) es la lista de los dígitos de n en posiciones

-- pares. Por ejemplo,

-- digitosPosPares 24012019 == [2,0,2,1]

digitosPosPares :: Integer -> [Integer]

digitosPosPares n = elementosPosPares (digitos n)

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 325 == [3,2,5]

digitos :: Integer -> [Integer]

digitos n = [read [c] | c <- show n]

-- (elementosPosPares xs) es la lista de los elementos de xs en

-- posiciones pares. Por ejemplo,

-- elementosPosPares [3,2,5,7,6,4] == [3,5,6]

elementosPosPares :: [a] -> [a]

elementosPosPares [] = []

elementosPosPares [x] = [x]

elementosPosPares (x:_:zs) = x : elementosPosPares zs

-- 1ª definición de invDigitosPosParesCuadrado

-- ========================================

invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

invDigitosPosParesCuadrado (xs, a) =

[x | x <- [ceiling (sqrt 10^(a-1))..ceiling (sqrt 10^a)]

, digitosPosParesCuadrado x == (xs,a)]

-- 2ª definición de invDigitosPosParesCuadrado

-- ========================================

invDigitosPosParesCuadrado2 :: ([Integer],Int) -> [Integer]

invDigitosPosParesCuadrado2 x =

[n | n <- [a..b], digitosPosParesCuadrado n == x]

where a = floor (sqrt (fromIntegral (completaNum x 0)))

b = ceiling (sqrt (fromIntegral (completaNum x 9)))

-- (completaNum (xs,k) n) es el número cuyos dígitos en las posiciones

-- pares son los de xs y los de las posiciones impares son iguales a n

-- (se supone que k es igual al doble de la longitud de xs o un

-- menos). Por ejemplo,

-- completaNum ([1,3,8],5) 4 == 14348

-- completaNum ([1,3,8],6) 4 == 143484

completaNum :: ([Integer],Int) -> Integer -> Integer

completaNum x n = digitosAnumero (completa x n)

-- (completa (xs,k) n) es la lista cuyos elementos en las posiciones

-- pares son los de xs y los de las posiciones impares son iguales a n

-- (se supone que k es igual al doble de la longitud de xs o un

-- menos). Por ejemplo,

-- completa ([1,3,8],5) 4 == [1,4,3,4,8]

-- completa ([1,3,8],6) 4 == [1,4,3,4,8,4]

completa :: ([Integer],Int) -> Integer -> [Integer]

completa (xs,k) n

| even k = ys

| otherwise = init ys

where ys = concat [[x,n] | x <- xs]

-- (digitosAnumero ds) es el número cuyos dígitos son ds. Por ejemplo,

-- digitosAnumero [2,0,1,9] == 2019

digitosAnumero :: [Integer] -> Integer

digitosAnumero = read . concatMap show

-- Comparación de eficiencia

-- =========================

-- λ> invDigitosPosParesCuadrado ([1,2,1,5,7,4,9],13)

-- [1106393,1234567,1314597]

-- (7.55 secs, 13,764,850,536 bytes)

-- λ> invDigitosPosParesCuadrado2 ([1,2,1,5,7,4,9],13)

-- [1106393,1234567,1314597]

-- (1.96 secs, 3,780,368,816 bytes)

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_digitosPosParesCuadrado :: Positive Integer -> Positive Integer -> Bool

prop_digitosPosParesCuadrado (Positive n) (Positive m) =

(digitosPosParesCuadrado m == x)

== (m `elem` invDigitosPosParesCuadrado x)

where x = digitosPosParesCuadrado n

-- La comprobación es

-- λ> quickCheck prop_digitosPosParesCuadrado

-- +++ OK, passed 100 tests.

Pensamiento

¡Ojos que a la luz se abrieron
un día para, después,
ciegos tornar a la tierra,
hartos de mirar sin ver.

Antonio Machado

Codificación matricial

PorJosé A. Alonso 21-marzo-201729-marzo-2017

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
Se extiende el mensaje con N²-L asteriscos. En el ejemplo, el mensaje extendido es "todoparanada****"
Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

     | t o d o |
     | p a r a |
     | n a d a |
     | * * * * |

| t o d o |

| p a r a |

| n a d a |

| * * * * |

Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

     | * n p t |
     | * a a o |
     | * d r d |
     | * a a o |

| * n p t |

| * a a o |

| * d r d |

| * a a o |

Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "*npt*aap*drd*aao"
El mensaje codificado se obtiene eliminando los asteriscos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

   codificado :: String -> String

1	codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

   codificado "todoparanada"    ==  "nptaaodrdaao"
   codificado "nptaaodrdaao"    ==  "danaopadtora"
   codificado "danaopadtora"    ==  "todoparanada"
   codificado "entodolamedida"  ==  "dmdeaeondltiao"

codificado "todoparanada" == "nptaaodrdaao"

codificado "nptaaodrdaao" == "danaopadtora"

codificado "danaopadtora" == "todoparanada"

codificado "entodolamedida" == "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Soluciones

import Data.List (genericLength)
import Data.Array

codificado :: String -> String
codificado cs =
  filter (/='*') (elems (rota p))
  where n = ceiling (sqrt (genericLength cs))
        p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char
rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]
  where d = bounds p
        n = fst (snd d)

import Data.List (genericLength)

import Data.Array

codificado :: String -> String

codificado cs =

filter (/='*') (elems (rota p))

where n = ceiling (sqrt (genericLength cs))

p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char

rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]

where d = bounds p

n = fst (snd d)

Primo suma de dos cuadrados

PorJosé A. Alonso 14-marzo-20161-abril-2016

Definir la sucesión

   primosSumaDe2Cuadrados :: [Integer]

1	primosSumaDe2Cuadrados :: [Integer]

cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,

   λ> take 20 primosSumaDe2Cuadrados
   [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]
   λ> primosSumaDe2Cuadrados !! (2*10^5)
   5803241

λ> take 20 primosSumaDe2Cuadrados

[2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]

λ> primosSumaDe2Cuadrados !! (2*10^5)

5803241

En el ejemplo anterior,

13 está en la sucesión porque es primo y 13 = 2²+3².
11 no está en la sucesión porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2²=7 y 11-3²=2 no son cuadrados).
20 no está en la sucesión porque, aunque es suma de dos cuadrados (20=4²+2²), no es primo.

Soluciones

import Data.Numbers.Primes (primes)

-- 1ª solución
-- ===========

primosSumaDe2Cuadrados1 :: [Integer]
primosSumaDe2Cuadrados1 =
    [n | n <- primes,
         esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool
esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]
sumas2cuadrados n = 
    [(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],
             let z = n - x^2,
             esCuadrado z, 
             let y = raiz z,
             x <= y]
             
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
    where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))

-- 2ª solución
-- ===========

primosSumaDe2Cuadrados2 :: [Integer]
primosSumaDe2Cuadrados2 =
    2 : [n | n <- primes,
             n `mod` 4 == 1]

-- Comparación de eficiencia
-- =========================

--    λ> primosSumaDe2Cuadrados1 !! (2*10^3)
--    38153
--    (3.03 secs, 568,239,744 bytes)
--    λ> primosSumaDe2Cuadrados2 !! (2*10^3)
--    38153
--    (0.05 secs, 20,017,912 bytes)

import Data.Numbers.Primes (primes)

-- 1ª solución

-- ===========

primosSumaDe2Cuadrados1 :: [Integer]

primosSumaDe2Cuadrados1 =

[n | n <- primes,

esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool

esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]

sumas2cuadrados n =

[(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],

let z = n - x^2,

esCuadrado z,

let y = raiz z,

x <= y]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado 25 == True

-- esCuadrado 26 == False

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz 25 == 5

-- raiz 24 == 4

-- raiz 26 == 5

raiz :: Integer -> Integer

raiz x = floor (sqrt (fromIntegral x))

-- 2ª solución

-- ===========

primosSumaDe2Cuadrados2 :: [Integer]

primosSumaDe2Cuadrados2 =

2 : [n | n <- primes,

n `mod` 4 == 1]

-- Comparación de eficiencia

-- =========================

-- λ> primosSumaDe2Cuadrados1 !! (2*10^3)

-- 38153

-- (3.03 secs, 568,239,744 bytes)

-- λ> primosSumaDe2Cuadrados2 !! (2*10^3)

-- 38153

-- (0.05 secs, 20,017,912 bytes)

Referencias

N.J.A. Sloane, Sucesión A002313 de la OEIS.
M. Bates, Primes of the form x² + ny²–
G. Xiao, Two squares.

Sumas de potencias de 3 primos

PorJosé A. Alonso 24-febrero-201625-marzo-2022

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

   28 = 2² + 2³ + 2⁴
   33 = 3² + 2³ + 2⁴
   47 = 2² + 3³ + 2⁴
   49 = 5² + 2³ + 2⁴

28 = 2² + 2³ + 2⁴

33 = 3² + 2³ + 2⁴

47 = 2² + 3³ + 2⁴

49 = 5² + 2³ + 2⁴

Definir la sucesión

   sumas3potencias :: [Integer]

1	sumas3potencias :: [Integer]

cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,

   λ> take 15 sumas3potencias
   [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
   λ> sumas3potencias !! 234567
   8953761

λ> take 15 sumas3potencias

[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]

λ> sumas3potencias !! 234567

8953761

Soluciones

import Data.Numbers.Primes (primes)

-- 1ª solución
-- ===========

sumas3potencias1 :: [Integer]
sumas3potencias1 = filter esTripleSuma [1..]
 
-- (esTripleSuma n) se verifica si n se puede escribir de la forma
-- p²+q³+r⁴, con p, q y r primos. Por ejemplo, 
--    esTripleSuma 33  ==  True
--    esTripleSuma 45  ==  False
esTripleSuma :: Integer -> Bool
esTripleSuma = not . null . triplesSumas  

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales
-- que p²+q³+r⁴ = n. Por ejemplo,
--    triplesSumas 33   ==  [(3,2,2)]
--    triplesSumas 145  ==  [(11,2,2),(2,5,2)]
--    triplesSumas 45   ==  []
triplesSumas :: Integer -> [(Integer,Integer,Integer)]
triplesSumas n =  
    [(p,q,r) 
    | r <- xs, 
      q <- xs, 
      let p2 = n - q^3 - r^4,
      let p = (floor . sqrt . fromIntegral) p2,
      p*p == p2,
      isPrime p]
    where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución
-- ===========

sumas3potencias2 :: [Integer]
sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]
sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
 
as = map (^2) primes
bs = map (^3) primes
cs = map (^4) primes

import Data.Numbers.Primes (primes)

-- 1ª solución

-- ===========

sumas3potencias1 :: [Integer]

sumas3potencias1 = filter esTripleSuma [1..]

-- (esTripleSuma n) se verifica si n se puede escribir de la forma

-- p²+q³+r⁴, con p, q y r primos. Por ejemplo,

-- esTripleSuma 33 == True

-- esTripleSuma 45 == False

esTripleSuma :: Integer -> Bool

esTripleSuma = not . null . triplesSumas

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales

-- que p²+q³+r⁴ = n. Por ejemplo,

-- triplesSumas 33 == [(3,2,2)]

-- triplesSumas 145 == [(11,2,2),(2,5,2)]

-- triplesSumas 45 == []

triplesSumas :: Integer -> [(Integer,Integer,Integer)]

triplesSumas n =

[(p,q,r)

| r <- xs,

q <- xs,

let p2 = n - q^3 - r^4,

let p = (floor . sqrt . fromIntegral) p2,

p*p == p2,

isPrime p]

where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución

-- ===========

sumas3potencias2 :: [Integer]

sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]

sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

as = map (^2) primes

bs = map (^3) primes

cs = map (^4) primes

Números primos de Hilbert

PorJosé A. Alonso 4-febrero-20161-mayo-2016

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …

Definir la sucesión

   primosH :: [Integer]

1	primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

   take 15 primosH  == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
   primosH !! 20000 == 203221

1 2	take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221

Soluciones

-- 1ª definición
-- =============

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,
--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]
numerosH :: [Integer]
numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a
-- n. Por ejemplo,
--   divisoresH 117  ==  [1,9,13,117]
--   divisoresH  21  ==  [1,21]
divisoresH :: Integer -> [Integer]
divisoresH n = [x | x <- takeWhile (<=n) numerosH,
                    n `mod` x == 0]

primosH1 :: [Integer]
primosH1 = [n | n <- tail numerosH,
                divisoresH n == [1,n]]

-- 2ª definición
-- =============

primosH2 :: [Integer]
primosH2 = filter esPrimoH (tail numerosH) 
    where esPrimoH n = all noDivideAn [5,9..m]
              where noDivideAn x = n `mod` x /= 0
                    m            = ceiling (sqrt (fromIntegral n))

-- Comparación de eficiencia
-- =========================

--    λ> primosH1 !! 2000
--    16957
--    (6.93 secs, 750,291,352 bytes)
--    λ> primosH2 !! 2000
--    16957
--    (0.13 secs, 18,066,288 bytes)

-- 1ª definición

-- =============

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,

-- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]

numerosH :: [Integer]

numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a

-- n. Por ejemplo,

-- divisoresH 117 == [1,9,13,117]

-- divisoresH 21 == [1,21]

divisoresH :: Integer -> [Integer]

divisoresH n = [x | x <- takeWhile (<=n) numerosH,

n `mod` x == 0]

primosH1 :: [Integer]

primosH1 = [n | n <- tail numerosH,

divisoresH n == [1,n]]

-- 2ª definición

-- =============

primosH2 :: [Integer]

primosH2 = filter esPrimoH (tail numerosH)

where esPrimoH n = all noDivideAn [5,9..m]

where noDivideAn x = n `mod` x /= 0

m = ceiling (sqrt (fromIntegral n))

-- Comparación de eficiencia

-- =========================

-- λ> primosH1 !! 2000

-- 16957

-- (6.93 secs, 750,291,352 bytes)

-- λ> primosH2 !! 2000

-- 16957

-- (0.13 secs, 18,066,288 bytes)

La menos conocida de las conjeturas de Goldbach

Soluciones

Otras soluciones

Pensamiento

Entre dos potencias sucesivas

Soluciones

Otras soluciones

Pensamiento

La conjetura de Mertens

Soluciones

Otras soluciones

Pensamiento

Teorema de existencia de divisores

Soluciones

Pensamiento

Suma de primos menores

Soluciones

Pensamiento

Mayor divisor primo

Soluciones

Pensamiento

Dígitos en las posiciones pares de cuadrados

Soluciones

Pensamiento

Codificación matricial

Soluciones

Primo suma de dos cuadrados

Soluciones

Referencias

Sumas de potencias de 3 primos

Soluciones

Números primos de Hilbert

Soluciones

Entradas recientes

Buscar

Correo electrónico