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

Question

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()

Answer 1

http://oeis.org/A003586

Robert Wilson's observation can be used for sieving numbers
but it will be too slow O(n^2)
Mathematica code looks nice and generates
sorted Pratt sequence in less than O(n) time

unit queue;
interface
   type pfifo_node = ^fifo_node;
        fifo_node = record
                data:longint;
                next:pfifo_node;
             end;
        fifo_pointers = record
                    head,tail:pfifo_node;
                 end;

procedure queue_init(var fifo:fifo_pointers);
function  queue_isEmpty(fifo:fifo_pointers):boolean;
procedure enqueue(var fifo:fifo_pointers;d:longint);
procedure dequeue(var fifo:fifo_pointers);
procedure print_queue(fifo:fifo_pointers);

implementation

procedure queue_init(var fifo:fifo_pointers);
begin
  fifo.head := NIL;
  fifo.tail := NIL;
end;

function  queue_isEmpty(fifo:fifo_pointers):boolean;
begin
  queue_isEmpty := ((fifo.head = NIL) and (fifo.tail = NIL));
end;

procedure enqueue(var fifo:fifo_pointers;d:longint);
var new_node:pfifo_node;
begin
  new(new_node);
  new_node^.data := d;
  new_node^.next := NIL;
  if(fifo.head = NIL) then
  begin
    fifo.head := new_node;
    fifo.tail := new_node;
  end
  else
  begin
    fifo.tail^.next := new_node;
    fifo.tail := new_node;
  end;
end;

procedure dequeue(var fifo:fifo_pointers);
var tmp:pfifo_node;
begin
  if(fifo.head <> NIL)then
  begin
    tmp := fifo.head^.next;
    dispose(fifo.head);
    fifo.head := tmp;
    if(tmp = NIL)then
      fifo.tail := NIL;
  end;
end;

procedure print_queue(fifo:fifo_pointers);
var tmp:pfifo_node;
    f:text;
begin
  assign(f,'');
  rewrite(f);   
  tmp := fifo.head;
  while(tmp <> NIL) do
  begin
    write(f,tmp^.data,' ');
    tmp := tmp^.next;
  end;
  writeln(f);
  close(f);
end;

begin

end.

program PrattGenerator;
uses crt,queue;

var fifo:fifo_pointers;
    n,pow3:longint;
    err:integer;
    aux:pfifo_node;

begin
  val(ParamStr(1),n,err);
  queue_init(fifo);
  enqueue(fifo,1);
  pow3 := 3;
  aux := fifo.head;
  while(fifo.tail^.data <= n) do
  begin
    if(2*aux^.data < pow3) then
    begin
      enqueue(fifo,2*aux^.data);
      aux := aux^.next;
    end
    else
    begin
      enqueue(fifo,pow3);
      pow3 := pow3 * 3;
    end;
  end;
  print_queue(fifo);
  while not queue_isEmpty(fifo) do
     dequeue(fifo);
end.

For comparison I will present Damian's solution

unit list;
interface
type PNode = ^TNode;
     TNode = record
               key:longint;
               next:PNode;
             end;
procedure ListInit(var L:PNode);
function  ListIsEmpty(L:PNode):boolean;
procedure ListPrint(L:PNode);
function ListSearch(L:PNode;k:longint):PNode;
procedure ListInsert(var L:PNode;k:longint);
procedure ListDelete(var L:PNode;k:longint);
implementation 
procedure ListInit(var L:PNode);
begin
  L := NIL;
end;
function ListIsEmpty(L:PNode):boolean;
begin
  ListIsEmpty := (L = NIL);
end;
procedure ListPrint(L:PNode);
var x:PNode;
    f:text;
begin
  assign(f,'');
  rewrite(f);
  x := L;
  while(x <> NIL)do
  begin
    write(f,x^.key,' ');
    x := x^.next;
  end;
  writeln(f);
  close(f);
end;
function ListSearch(L:PNode;k:longint):PNode;
var x:PNode;
begin
  x := L;
  while((x <> NIL) and (x^.key <> k)) do
     x := x^.next;
  ListSearch := x;
end;
procedure ListInsert(var L:PNode;k:longint);
var x,y,z:PNode;
begin
  new(x);
  x^.key := k;
  if(L = NIL)then
  begin
    L := x;
    x^.next := NIL;
  end
  else
  begin
    y := L;
    z := NIL;
    while((y <> NIL) and (x^.key > y^.key)) do
    begin
      z := y;
      y := y^.next;
    end;
    x^.next := y;
    if z <> NIL then
       z^.next := x
    else 
       L := x;
  end;
end;
procedure ListDelete(var L:PNode;k:longint);
var x,y:PNode;
begin
  x := ListSearch(L,k);
  if ((L <> NIL) and (x <> NIL)) then
     if (L = x) then
     begin
       L := x^.next;
       dispose(x);
     end
     else
     begin
       y := L;
       while (y^.next <> x) do
          y := y^.next;
       y^.next := x^.next;
       dispose(x);
     end;
 end;
 begin

 end.
program Prattgenerator;
uses list;

var L:PNode;
    pow2,pow3,max_size:longint;
    err:integer;
begin
  val(ParamStr(1),max_size,err);
  ListInit(L);
  pow3 := 1;
  while (pow3 <= max_size) do
  begin
    pow2 := pow3;
    while (pow2 <= max_size) do
    begin
      ListInsert(L,pow2);
      pow2 := pow2 * 2;     
    end;
    pow3 := pow3 *3;
  end;
  ListPrint(L);
  while not ListIsEmpty(L) do
     ListDelete(L,L^.key);
end.

We can use stack to reverse order of elements
Creating new nodes for the stack is not necessary
We can try to build stack from existing queue nodes

Answer 2

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))