title: How do I implement the Pratt gap sequence? (Python, Shell Sort)
body: <p>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.</p>
  
  <p>On Wikipedia (<a href="http://en.wikipedia.org/wiki/Shellsort" rel="nofollow">http://en.wikipedia.org/wiki/Shellsort</a>) 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,...</p>
  
  <p>What I don't get is how to implement this, basically what are P and Q? </p>
  
  <p>The worst-case time complexity is O(Nlog^2N)</p>
  
  <p>My Current Code for the sequence generator file:</p>
  
  <pre><code>    def Hibbard(big):
          H = open("Hibbard.txt","w")
          i = 1
          math = (2**i)-1
          while math &lt;= 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 &lt;= 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)
  </code></pre>
  
  <h1>Pratt(big)</h1>
  
  <pre><code>        SedA(big)
  </code></pre>
  
  <h1>SedB(big)</h1>
  
  <pre><code>    main()
  </code></pre>