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.

3 Comentarios

import Data.Numbers.Primes

mobius :: Integer -> Integer
mobius n
  | esLibreDeCuadrados n && even (length (primeFactors n)) = 1
  | esLibreDeCuadrados n && odd (length (primeFactors n))  = -1
  | not (esLibreDeCuadrados n)                             = 0
           
esLibreDeCuadrados :: Integer -> Bool
esLibreDeCuadrados n =
  null [x | x <- [2.. raiz n], rem n (x^2) == 0]

raiz :: Integer -> Integer
raiz = ceiling . sqrt . fromIntegral

mertens :: Integer -> Integer
mertens n = sum [mobius x | x <- [1..n]]

conjetura :: Integer -> Property
conjetura x = x > 1 ==> abs (mertens x)  < raiz x

-- λ> quickCheck conjetura
-- +++ OK, passed 100 tests.

import Data.Numbers.Primes

mobius :: Integer -> Integer

mobius n

| esLibreDeCuadrados n && even (length (primeFactors n)) = 1

| esLibreDeCuadrados n && odd (length (primeFactors n)) = -1

| not (esLibreDeCuadrados n) = 0

esLibreDeCuadrados :: Integer -> Bool

esLibreDeCuadrados n =

null [x | x <- [2.. raiz n], rem n (x^2) == 0]

raiz :: Integer -> Integer

raiz = ceiling . sqrt . fromIntegral

mertens :: Integer -> Integer

mertens n = sum [mobius x | x <- [1..n]]

conjetura :: Integer -> Property

conjetura x = x > 1 ==> abs (mertens x) < raiz x

-- λ> quickCheck conjetura

-- +++ OK, passed 100 tests.

Responder

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])

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]]

-- 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])

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]]

-- 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.

Responder

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

mobius :: Integer -> Integer
mobius n
  | factoresDistintos xs && even (length xs) = 1
  | factoresDistintos xs && odd (length xs)  = -1
  | otherwise                                = 0
  where xs = primeFactors n

factoresDistintos :: [Integer] -> Bool
factoresDistintos [] = True
factoresDistintos [_] = True
factoresDistintos (x:y:xs)
  | x == y = False
  | x /= y = factoresDistintos (y:xs)

mertens :: Integer -> Integer
mertens n = sum [mobius x | x <- [1..n]]

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

prop_Mertens :: Integer -> Property
prop_Mertens x =
  x > 1 ==> abs (mertens x) < ceiling (sqrt (fromIntegral x))

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

import Graphics.Gnuplot.Simple

mobius :: Integer -> Integer

mobius n

| factoresDistintos xs && even (length xs) = 1

| factoresDistintos xs && odd (length xs) = -1

| otherwise = 0

where xs = primeFactors n

factoresDistintos :: [Integer] -> Bool

factoresDistintos [] = True

factoresDistintos [_] = True

factoresDistintos (x:y:xs)

| x == y = False

| x /= y = factoresDistintos (y:xs)

mertens :: Integer -> Integer

mertens n = sum [mobius x | x <- [1..n]]

graficaMertens :: Integer -> IO ()

graficaMertens n =

plotLists [ Key Nothing

, Title "Conjetura de Mertens"

, PNG "Conjetura_de_Mertens.png"

]

[[mertens k | k <- [1..n]], raices, map negate raices]

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

prop_Mertens :: Integer -> Property

prop_Mertens x =

x > 1 ==> abs (mertens x) < ceiling (sqrt (fromIntegral x))

Responder

La conjetura de Mertens

Soluciones

Otras soluciones

Pensamiento

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico