How to make Haskell use another list depending on the previous answer in Haskell

Question

I am doing project euler question 63 where I must find the amount of numbers that exist where:

x^(n) == y

Where n is the length of y.

It soon emerges that the results for this condition alternate between odd and even and so I came up with this in Haskell:

prob63 = [ n | n <- nums n , i <-[1..10], i^(length $ show n) == n]

nums n | odd (n) == True = filter odd [n..]
    | otherwise         = filter even [n..]

If n <- [1..], prob63 produces a stream that looks like this:

[1,2,3,4,5,6,7,8,9,16,25,36,49,64,81,125,216,343,512,729,1296,2401,4096,6561,16807,32768,59049,117649,262144,531441]

But this is slow and what I came up with after doesn't work. What I need is, depending on the previous answer, it will start testing the odd or even integers from n. How would I go about this from what I already have?

Stephan202 Stephan202 · Accepted Answer · 2009-10-15T10:20:51

Look again at the output. The elements do not alternate between odd and even!

1,2,3,4,5,6,7,8,9,16,25,36,49,64,81,125,216,343,512,729,1296,2401,4096,6561,16807,32768,59049,117649,262144,531441]

I noticed this after implementing the code that you ask for. Its output does not match the output of your code. I'll post the code here anyway:

prob63 :: [Integer]
prob63 = test 1
  where
    test s = next : test (next + 1)
      where
        next = head [n | n <- [s,s+2..], i <-[1..10], i^(length $ show n) == n]

How to make Haskell use another list depending on the previous answer in Haskell

1 Answers