What are handy Haskell concepts to generate numbers of the form 2^m*3^n*5^l-CodePudding

I am trying generate numbers of the form 2^m*3^n*5^l where m, n, and l are natural numbers including 0.

The sequence follows: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, .....

I am testing it by getting the one millionth number. I implemented it using list comprehension and sorting, but it takes too long. I want a faster solution. I have been spending days trying to do this to no avail.

I do not want a complete solution. I just want to know what Haskell concepts are necessary in accomplishing it.

CodePudding user response：

Here's an approach that doesn't need any Haskell concepts, just some math and computer science.

Grab a library that offers priority queues.

Initialize a priority queue containing only the number 1.

Loop the following indefinitely: extract the minimum value from the queue. Put it next in the output list. Insert that number times 2, 3, and 5 as three individual entries in the queue. Make sure the queue insert function merges duplicates, because there will be a lot of them thanks to commutativity of multiplication.

If you have a maximum you're working up to, you can use it to prune insertions to the queue as a minor optimization. Alternatively, you could take advantage of actual Haskell properties and just return an infinite list using laziness.

CodePudding user response：

First, write a function of type Int -> Bool that dermines if a given integer is in the sequence you defined. It would divide the number by 2 as many times as possible (without creating a fraction), then divide it by 3 as many times as possible, and finally divide it by 5 as many times as possible. After all of this, if the number is larger than 1, then it cannot be expressed as a products of twos, threes, and fives, so the function would return false. Otherwise, the number is in your sequence, so the function returns true.

Then take the infinite sequence of integers greater than 0, and use the function above to filter out all numbers that are not in the sequence.

CodePudding user response：

Carl's approach can be improved by inserting less elements when removing the minimal element x: As 2<3<4<5<6 you can just

append 3*x/2 if x is even but not divisible by 4
append 4*x/3 if x is divisible by 3
append 5*x/4 if x is divisible by 4
append 6*x/5 if x is divisible by 5

In code it looks like this:

g2 x | mod x 4 == 0 = [5*div x 4]
     | even x       = [3*div x 2]
     | otherwise    = []
g3 x | mod x 3 == 0 = [4*div x 3]
     | otherwise    = []
g5 x | mod x 5 == 0 = [6*div x 5]
     | otherwise    = []
g x = concatMap ($ x) [g2, g3, g5]

So you if your remove the minimal element x from the priority queue, you have to insert the elements of g x into the priority queue. On my laptop I get the millionth element after about 8 min, even if I use just a list instead of the better priority queue, as the list grows only to a bit more than 10000 elements.