Ir al contenido principal

Factorizaciones de números de Hilbert

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 función

factorizacionesH :: Integer -> [[Integer]]

tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,

factorizacionesH  25  ==  [[5,5]]
factorizacionesH  45  ==  [[5,9]]
factorizacionesH 441  ==  [[9,49],[21,21]]

Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque laa factorización, como para el 441, puede no ser única).

Soluciones

import Test.QuickCheck

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

-- primosH es la sucesión de primos de Hilbert. Por ejemplo,
--    take 15 primosH  ==  [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
primosH :: [Integer]
primosH = filter esPrimoH (tail numerosH)
    where esPrimoH n = all noDivideAn [5,9..m]
              where noDivideAn x = n `mod` x /= 0
                    m            = ceiling (sqrt (fromIntegral n))

factorizacionesH :: Integer -> [[Integer]]
factorizacionesH n = aux n primosH
    where aux n (x:xs)
              | x == n         = [[n]]
              | x > n          = []
              | n `mod` x == 0 = map (x:) (aux (n `div` x) (x:xs))
                                 ++ aux n xs
              | otherwise      = aux n xs

-- La propiedad es
prop_factorizable :: Integer -> Property
prop_factorizable n =
    n > 0 ==> not (null (factorizacionesH (1 + 4 * n)))

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

Referencias

Basado en el artículo Failure of unique factorization (A simple example of the failure of the fundamental theorem of arithmetic) de R.J. Lipton en el blog Gödel's Lost Letter and P=NP.

Otras referencias