Menu Close

Factorizaciones de 4n+1

José A. Alonso,

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]]
     factorizaciones 2205  ==  [[5,9,49],[5,21,21]]
  • 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]

Pensamiento

¡Qué bien los nombres ponía
quien puso Sierra Morena
a esta serranía!

Antonio Machado

Inicial
, , , ,

Una solución de “Factorizaciones de 4n+1”

  1. Responder
    javjimord 
    import Data.List (subsequences)
 
conjuntoS :: [Integer]
conjuntoS = [x | x <- [1..], mod x 4 == 1]
 
divisoresS :: Integer -> [Integer]
divisoresS n = [x | x <- takeWhile (<=n) conjuntoS, mod n x == 0]
 
esIrreducible :: Integer -> Bool
esIrreducible n = divisoresS n == [1,n]
 
factorizaciones :: Integer -> [[Integer]]
factorizaciones n =
  [xs | xs <- subsequences (takeWhile (<=n) conjuntoS)
      , product xs == n
      , and [esIrreducible x | x <- xs]]
 
conFactorizacionNoUnica :: [Integer]
conFactorizacionNoUnica =
  [n | n <- conjuntoS
     , length (factorizaciones n) >= 2]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.