Generating Ascending Sequence 2^p*3^q

Question

I was interested in implementing a specific Shellsort method I read about that had the same time complexity as a bitonic sort. However, it requires the gap sequence to be the sequence of numbers [1, N-1] that satisfy the expression 2^p*3^q for any integers p and q. In layman's terms, all the numbers in that range that are only divisible by 2 and 3 an integer amount of times. Is there a relatively efficient method for generating this sequence?

Answer 1

Numbers of that form are called 3-smooth. Dijkstra studied the closely related problem of generating 5-smooth or regular numbers, proposing an algorithm that generates the sequence S of 5-smooth numbers by starting S with 1 and then doing a sorted merge of the sequences 2S, 3S, and 5S. Here's a rendering of this idea in Python for 3-smooth numbers, as an infinite generator.

def threesmooth():
    S = [1]
    i2 = 0  # current index in 2S
    i3 = 0  # current index in 3S
    while True:
        yield S[-1]
        n2 = 2 * S[i2]
        n3 = 3 * S[i3]
        S.append(min(n2, n3))
        i2 += n2 <= n3
        i3 += n2 >= n3

Answer 2

Simplest I can think of is to run a nested loop over p and q and then sort the result. In Python:

N=100
products_of_powers_of_2and3 = []
power_of_2 = 1
while power_of_2 < N:
    product_of_powers_of_2and3 = power_of_2
    while product_of_powers_of_2and3 < N:
        products_of_powers_of_2and3.append(product_of_powers_of_2and3)
        product_of_powers_of_2and3 *= 3
    power_of_2 *= 2
products_of_powers_of_2and3.sort()
print products_of_powers_of_2and3

result

[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96]

(before sorting the products_of_powers_of_2and3 is

[1, 3, 9, 27, 81, 2, 6, 18, 54, 4, 12, 36, 8, 24, 72, 16, 48, 32, 96, 64]

)

Given the size of products_of_powers_of_2and3 is of the order of log₂N*log₃N the list doesn't grow very fast and sorting it doesn't seem particularly inefficient. E.g. even for N = 1 million, the list is very short, 142 items, so you don't need to worry.