Implementing a factorisation method in Haskell

Question

Hi

I am doing question 266 at project euler and after a bit of searching, found this method of quickly finding the factors of a number. What you do is find all the permutations of the prime factors of a number, these are its factors.
I already have a module to find the prime power factors of a number, eg:

Main> primePowerFactors 196
[(2,2),(7,2)]

This is basically showing that: 2^2 * 7^2 == 196. From here I want to find all the permutations of those powers, to give the factors of 196 thusly:

• (2^0)(7^0) = 1
• (2^1)(7^0) = 2
• (2^2)(7^0) = 4
• (2^0)(7^1) = 7
• (2^1)(7^1) = 14
• (2^2)(7^1) = 28
• (2^0)(7^2) = 49
• (2^1)(7^2) = 98

I came up with the following:

factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
 where 
  facs (x,y) = (x,y)   
rSq n = toInteger $ round $ sqrt (fromInteger n)    
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)

But my problem is that factors doesn't work properly. I want it to permute through all the possible values of the exponent for each prime factor and then find the product to give the factor. How can it be modified to return the just the factors of n?

Answer 1

First of all, facs is the identity function:

facs (x,y) = (x,y)

The y is bound in the pattern match on the left hand side while you probably intended it to be the y from the list comprehension. Variable names bound in a list comprehension are local to that comprehension and can not be used in a different scope like the where clause.

Also, the y in the list comprehension is only computed from the last factors exponent:

y <- [0..(snd $ last $ primePowerFactors n)]

For each factor it's own exponent should be considered, not just always the exponent of the last factor.

A more fundamental problem is, that the return type of the factors function doesn't seem to match it's intention:

*Euler> :t factors
factors :: Integer -> [(Integer, Int)]

This returns a list of powers of prime factors while it should produce a list of these constructs, like this:

[
   [(2,0), (7,0)],
   [(2,1), (7,0)],
   [(2,2), (7,0)],
   [(2,0), (7,1)],
   [(2,1), (7,1)],
   ...
]

The prime factorization of all possible factors is needed, but the function seems to return just one prime factorization.

Answer 2

for some code golf i wrote a nice power set function that is pretty simple.

powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)

A deficiency of this algorithm is that it doesn't include the original set, however that is perfect for you since it doesn't look like you want it.

combine this with a way to convert your primePowerFactors n into a list of ints, lets say

ppfToList = concatMap (\(x,y)->replicate y x)

using these helpers, a list of factors from a number n is generated with

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that

This sort of algorithm is probably a bit harder to express in terms of a list comprehension.