How do I implement the Pratt gap sequence? (Python, Shell Sort)

I have to code a shell sort program in Python, but along side it I must have a program that creates text files using some of the special gap sequences, this is where my shell sort will get its gap numbers.

On Wikipedia (http://en.wikipedia.org/wiki/Shellsort) The equation for the Pratt sequence is this: "Successive numbers of the form 2^p*3^q" and it produces 1,2,3,4,6,8,9,12,...

What I don't get is how to implement this, basically what are P and Q?

The worst-case time complexity is O(Nlog^2N)

My Current Code for the sequence generator file:

        def Hibbard(big):
            H = open("Hibbard.txt","w")
            i = 1
            math = (2**i)-1
            while math <= big:
                H.write(str(math))
                H.write("\n")
                i+=1
                math = (2**i)-1
        def Pratt(big):
            pass
        def SedA(big):
            SA = open("SedgewickA.txt","w")
            SA.write("1\n")
            i = 1
            math = (4**i)+3*2**(i-1)+1
            while math <= big:
                SA.write(str(math))
                SA.write("\n")
                i+=1
                math = (4**i)+3*2**(i-1)+1
        def SedB(big):
            pass
        def main():
            big = int(input("Enter the largest gap: "))
            Hibbard(big)
#            Pratt(big)
            SedA(big)
#            SedB(big)

        main()

Solution

In the definition of the Pratt sequence, p and q are the exponents to which 2 and 3 are raised respectively. You need to find all products of powers of 2 and 3 no larger than the maximum gap size of your sort. To do this, make a table with powers of 2 across the top and powers of 3 down the side, and fill each cell with their products until they exceed the maximum gap size. For example, with the maximum gap size 500, the table would look like this:

   1   2   4   8  16  32  64 128 256
   3   6  12  24  48  96 192 384
   9  18  36  72 144 288
  27  54 108 216 432
  81 162 324
 243 486

Now simulate the generation of this table in Python.

def generate_pratt(max_size):
    """Generate a sorted list of products of powers of 2 and 3 below max_size"""
    # for https://stackoverflow.com/q/25964453/2738262
    products = []
    pow3 = 1  # start with q = 0
    while pow3 <= max_size:
        # At this point, pow3 = 3**q, so set p = 0
        pow2 = pow3
        while pow2 <= max_size:
            # At this point, pow2 = 2**p * 3**q
            products.append(pow2)
            pow2 = pow2 * 2  # this is like adding 1 to p
        # now that p overflowed the maximum size, add 1 to q and start over
        pow3 = pow3 * 3

    # the Pratt sequence is the result of this process up to the given size
    return sorted(products)

print(generate_pratt(12))