loops - The number of the product n=(a^2) * (a^3) using recursion only in haskell

Question

In Haskell, I want to find how many pairs a,b there are for a given number n, given n = (a^2) * (a^3). I must give the numbers and it should return the pairs. For example:

Main> count 24
0
Main> count 72
1
Main> count 256
2
Main> count 4096
3
Main> count 46656
4

So far I have only done a program that for a number n, finds the sum of all possible combinations for n = (a^2) * (a^3). For example, for n=2, (1^2+1^3)+(1^2+2^3)+(2^2+2^3)+(2^2+1^3). Any suggestions? I am required to implement this program without lists.

sumF :: (Int->Int)->Int->Int
sumF f 0 = 0
sumF f n = sumF f (n-1) + f n



sumF1n1n :: (Int->Int->Int)->Int->Int
sumF1n1n f 0 = 0
sumF1n1n f n = sumF1n1n f (n-1)
    +sumF (i -> f i n) (n-1)
    +sumF (j -> f n j) (n-1)
    +f n n

func :: Int->Int->Int
func 0 0 = 0
func a b = res
    where
    res = (a^2*b^3)

call :: Int->Int
call n = sumF1n1n func n

Answer 1

You want to do it using recursion only You first have to find a way to enumerate all couples in a range. E.g. for the range (a, b) you want [(0,0), (0,1), ..., (0,a), (1,0), ..., (1,b), ..., (a,b)]. The first idea is to start with (a, b), decrease a until it reaches 0 and restart with (a,b-1) etc.

We could try something like that:

-- doesn't work
couples 0 0 = [(0,0)]
-- what to do when a reaches 0?   v
couples 0 b = [(0,b)] ++ couples *?* (b-1)
couples a b = [(a,b)] ++ couples (a-1) b

When a reaches 0, we want to restart from the initial value of a and decrease b by one. Hence we have to store the initial value of a:

couples' 0 0 _ = [(0,0)]
-- use max_a to set the restart
couples' 0 b max_a = [(0,b)] ++ couples' max_a (b-1) max_a
couples' a b max_a = [(a,b)] ++ couples' (a-1) b max_a

It works:

couples a b = couples' a b a
main = print $ couples 3 2
-- [(3,2),(2,2),(1,2),(0,2),(3,1),(2,1),(1,1),(0,1),(3,0),(2,0),(1,0),(0,0)]

Now, we don't want all the couples, but only those verifying a*a*b*b*b == n. (Note: I excluded the (0,0) couple since I assume n /= 0. If n==0, then you have a lot of solutions!).

This is simple as:

call' _ 0 0 _ = []
call' n 0 b max_a = call' n max_a (b-1) max_a
call' n a b max_a = (if n==a*a*b*b*b then [(a,b)] else []) ++ call' n (a-1) b max_a

If I write:

call n = call' n max max max
        where max = (ceiling.sqrt.fromIntegral) n

I get the following results:

call 24
-- []
call 72
-- [(3,2)]
call 256
-- [(2,4),(16,1)]
call 4096
-- [(1,16),(8,4),(64,1)]
call 46656
-- [(1,36),(8,9),(27,4),(216,1)]

If you only want the count, use this:

call' _ 0 0 _ = 0
call' n 0 b max_a = call' n max_a (b-1) max_a
call' n a b max_a = (if n==a*a*b*b*b then 1 else 0) + call' n (a-1) b max_a

For the record, you can do this with list comprehensions:

Prelude> couples a b = [(i,j)| i<-[0..a], j<-[0..b]]
Prelude> couples 3 2
[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2)]

And:

Prelude> call n = [(a,b)| let max = (ceiling.sqrt.fromIntegral) n, a<-[0..max], b<-[0..max], n==a*a*b*b*b]
Prelude> call 24
[]
Prelude> call 72
[(3,2)]
Prelude> call 256
[(2,4),(16,1)]
Prelude> call 4096
[(1,16),(8,4),(64,1)]
Prelude> call 46656
[(1,36),(8,9),(27,4),(216,1)]