12

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?

TooTone
  • 7,129
  • 5
  • 34
  • 60
Patrick Roberts
  • 49,224
  • 10
  • 102
  • 153

4 Answers4

17

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
Athari
  • 33,702
  • 16
  • 105
  • 146
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Out of interest I timed your answer (as plain Python code producing `S`) and mine and couldn't see a lot of difference. As expected they were both extremely fast because even for, e.g., N=10^10, the sequence is only 476 long and both implementations execute sub 1ms. The curious thing was that looking at your code I expected it to be linear in the sequence size and hence faster, but it ran almost 2x slower even for very large `N`. I'm not a Python expert so perhaps I didn't get the [code](http://ideone.com/5fWiKB) right, or the difference would show in C++, or something else? What do you think? – TooTone Aug 16 '14 at 23:10
  • @TooTone What you have there looks reasonable to me, though I'm no expert on Python performance. I'm reluctant to speculate about what would happen in C++, and as you point out, the time spent computing the strides for shellsort is trivial compared to actually sorting. – David Eisenstat Aug 16 '14 at 23:35
  • Can you explain what the "yield" syntax does? I'm not familiar with what that statement does. – Patrick Roberts Aug 17 '14 at 00:28
  • @PatrickRoberts If you replaced it with a `print`, then the code would print out the elements of the sequence one by one. What `yield` does effectively is to redirect what would be printed into an infinite sequence that can be consumed by other pieces of code. See also this Stack Overflow question: http://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python – David Eisenstat Aug 17 '14 at 00:47
  • Oh okay, thanks. I'll select yours as the correct since it generates them already sorted. – Patrick Roberts Aug 17 '14 at 00:56
  • ethan points out that this will list duplicates. You might want to double check that `min!=S[-1]` before appending. And is `i3 += n2 >= n3` the same as `if n2 >= n3: i3 += n2`? – Teepeemm Apr 24 '15 at 11:18
  • 1
    @Teepeemm It's fine as is. – David Eisenstat Apr 24 '15 at 12:56
  • Awesome algorithm, proof that it won't add duplicates -> assume that x is going to be added again and wlog let say x was added using i2 pointer, then i2 pointer can't add x again as 2*S[i2] is increasing. and as x was added it was less than 3*S[i3] so even i3 pointer can't add x again as 3*S[i3] is also strictly increasing! – illla Oct 09 '21 at 12:27
5

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 log2N*log3N 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.

TooTone
  • 7,129
  • 5
  • 34
  • 60
0

You can do it very easy in JavaScript

arr = [];
n = 20;
function generateSeries() {
  for (let i = 0; i < n; i++) {  
    for (let j = 0; j < n; j++) {
      arr.push(Math.pow(2, i) * Math.pow(3, j))
    }
  }
  sort();
}

function sort() {
  arr.sort((a, b) => {
    if (a < b) {return -1;}
    if (a > b) {return 1;}
    return 0;
  });
}

function solution(N) {
  arr = [];
  if (N >= 0 && N <= 200 ) {
    generateSeries();
    console.log("arr >>>>>", arr);
    console.log("result >>>>>", arr[N]);
    return arr[N];
  }
}
Me Sa
  • 1,036
  • 12
  • 14
-1
N = 200
res =[]
a,b = 2,3
for i in range(N):
  for j in range(N):
    temp1=a**i
    temp2=b**j
    temp=temp1*temp2
    if temp<=200:
      res.append(temp)
res = sorted(res)
print(res)
Ajayan Saroj
  • 1