Factorizaciones de 4n+1
Sea S el conjunto
S = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, ...}
de los enteros positivos congruentes con 1 módulo 4; es decir,
S = {4n+1 | n ∈ N}
Un elemento n de S es irreducible si sólo es divisible por dos elementos de S: 1 y n. Por ejemplo, 9 es irreducible; pero 45 no lo es (ya que es el proctos de 5 y 9 que son elementos de S).
Definir las funciones
esIrreducible :: Integer -> Bool factorizaciones :: Integer -> [[Integer]] conFactorizacionNoUnica :: [Integer]
tales que
- (esIrreducible n) se verifica si n es irreducible. Por ejemplo,
esIrreducible 9 == True esIrreducible 45 == False
- (factorizaciones n) es la lista de conjuntos de elementos irreducibles de S cuyo producto es n. Por ejemplo,
factorizaciones 9 == [[9]] factorizaciones 693 == [[9,77],[21,33]] factorizaciones 4389 == [[21,209],[33,133],[57,77]]
- conFactorizacionNoUnica es la lista de elementos de S cuya factorización no es única. Por ejemplo,
λ> take 10 conFactorizacionNoUnica [441,693,1089,1197,1449,1617,1881,1953,2205,2277]
Soluciones
esIrreducible :: Integer -> Bool esIrreducible n = divisores n == [1,n] -- (divisores n) es el conjunto de elementos de S que dividen a n. Por -- ejemplo, -- divisores 9 == [9] -- divisores 693 == [9,21,33,77,693] divisores :: Integer -> [Integer] divisores n = [x | x <- [1,5..n], n `mod` x == 0] factorizaciones :: Integer -> [[Integer]] factorizaciones 1 = [[1]] factorizaciones n | esIrreducible n = [[n]] | otherwise = [d:ds | d <- divisores n , esIrreducible d , ds@(e:_) <- factorizaciones (n `div` d) , d <= e] conFactorizacionNoUnica :: [Integer] conFactorizacionNoUnica = [n | n <- [1,5..], length (factorizaciones n) > 1]