Generating ascending sequence 2 ^ p * 3 ^ q

Question

I was interested in implementing the particular Shellsort method that I read, which had the same time complexity as the bitonic type. However, a sequence of spaces requires a sequence of numbers [1, N-1], which satisfy the expression 2 ^ p * 3 ^ q for any integers p and q. In non-professional terms, all numbers in this range that are only divisible by 2 and 3 are an integer number of times. Is there a relatively efficient way to generate this sequence?

Answer 1

Numbers of this form are called 3- smooth . Dijkstra studied the closely related problem of generating 5-smooth or regular numbers , proposing an algorithm that generates a sequence S of 5-smooth numbers, starting with S from 1, and then doing an ordered merging of the sequences 2S, 3S and 5S. Here's a rendering of this idea in Python for 3-smooth numbers, like 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

The easiest way I can think of is to start 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 products_of_powers_of_2and3 there is

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

)

Given that the size of products_of_powers_of_2and3 is of the order of log ₂ N * log ₃ N, the list does not grow very quickly and its sorting is not performed seem particularly inefficient. For instance. even with N = 1 million, the list is very short, 142 items, so you do not need to worry.