Enumerate unique multiples of numbers

Question

Suppose we're given an array of positive numbers M, say [3, 5, 7] and we want to enumerate all numbers which are multiple of any one of them, less than some upper bound, say K, so in this case 0, 3, 5, 6, 7, 9, 10, 12, 14, 15....

How would one do it efficiently when size of M is large?

One Naive approach is to start from 0 and for each value check if it divides any value in M, which is not great as values may be large so most numbers won't be enumerated but will waste computation.

I would like to enumerate in such a way that time complexity is as close to theoretical minimum as possible, ie. O(Number of elements in sequence), which means values which are common multiples, for example 6 in sequence of [2, 3] ideally shouldn't require more computation than any other value.

Answer 1

I think you can optimize the algorithm by using heap data structure (PriorityQueue queue in below Python code) to keep track of the next smallest multiple of the numbers in M list that will be added to the enumerated list until it reaches K. The advantage heap data structure is that it has O(1) lookup time for finding the smallest value in the list and O(log(n)) for insertion and deletion.

Initially the queue will have the M items, each has the following tuple structure (<num 1>, <num 1>), where the first item is the next multipled value to append to the list and the second item is the original value.

While the last enumerated number is less than K and the queue is empty, we can continuously pull the lexicographically smallest item from the queue and append to the enumerated list if the value not exist in the list and value is less than or equal to K. Afterwards, we append a new structure into the queue as (<num> + <multiple>, <multiple>) to represent the next multiple of the original value (<multiple>)

The estimated time complexity would be O(Klog(M)) which is more efficient than O(KM) in the original post

from queue import PriorityQueue

M = [3, 5, 7]
K =19 

res = [0]

queue = PriorityQueue()

# Queue initialization
for m in M:
    queue.put((m, m)) # structure (<new value>, <its multiple>)

# continue looping while largest element in the result list is less than K: O(K)
while res[-1] < K and not(queue.empty()):
    # get the smallest element in the priority queue: O(log(n))
    val, multiple = queue.get()

    if res[-1] != val and val <= K:
        # value is not already in the result list, then append to the list
        res.append(val)
    
    if val + multiple <= K:
        # append new candidate value which is the next multiple of the original value: O(log(n))
        queue.put((val + multiple, multiple))

print(res)