#! /usr/bin/env python

# numCanonicalStr.py
# P.Clote

# Computes the number of canonical sec str, assuming
# every base can base pair with every other base and THRESHOLD=1. 
# Grammar to generate canonical sec str S, where R generates structures
# that become canonical by adding closing external base pair
# S -->  * | S * | ( R ) | S ( R )
# R --> ( * ) | (R) | (S(R)) | (S *)

import sys,math
THRESHOLD = 1

def maxNumBasePairs(n):
  return (n-THRESHOLD)/2

def numCanonStr(n):  
  #S[n] is number of canonical str on [1,n]
  S = {}; R = {}
  for m in range(THRESHOLD+4): S[m] = 1L  #empty structure only possible str
  for m in range(THRESHOLD+2): R[m] = 0L  #empty structure only possible str
  R[THRESHOLD+2] = 1L  # structure (*)
  R[THRESHOLD+3] = 1L  # not structures (*)*  and *(*), but structure (**)
  for m in range(THRESHOLD+4,n+1):
    S[m] = S[m-1] + R[m-2] 
    for k in range(THRESHOLD,m-2): #k in [THRESHOLD,m-3], so require |S|>0
      S[m] += R[k]*S[m-2-k]
    R[m] = R[m-2] + S[m-3]
    for k in range(THRESHOLD,m-4): #k in [THRESHOLD,m-5], so require |S|>0
      R[m] += R[k]*S[m-4-k]
  return S,R

def numCanonStrBis(n):  
  #S[n] is number of canonical str on [1,n]
  #In notation of Hofacker et al., S is Psi, R is Psi* and RR is Psi**
  S = {}; R = {}; RR = {}
  for m in range(THRESHOLD+4): 
    S[m]  = 1L 
    RR[m] = 1L  #empty structure only possible str
  RR[THRESHOLD+4] = 1L
  for m in range(THRESHOLD+2): 
    R[m]  = 0L  #no structure possible
  R[THRESHOLD+2] = 1L  #only structure is (*)
  R[THRESHOLD+3] = 1L  #only structure is (**)
  for m in range(THRESHOLD+4,n+1):
    S[m] = S[m-1] 
    for k in range(THRESHOLD+2,m-1): #k in [THRESHOLD+2,m-2]
      S[m] += R[k]*S[m-2-k]
    R[m] = 0L
    for k in range(1,(m-THRESHOLD)/2+1): #k in [1, (m-THRESHOLD)/2]
      R[m] += RR[m-2*k]
    RR[m] = S[m] - R[m-2] 
  return S,R,RR

def checkBothComputations(n):
  S,R = numCanonStr(n)
  S0,R0,RR0= numCanonStrBis(n)
  print "S(n) resp S0(n) is num canon str on [1,n] determined by us resp. Hofacker et al"
  print "n\tS(n)\tS0(n)\tR\tR0\tRR0"
  for k in range(n):
    print "%d\t%d\t%d\t%d\t%d\t%d" % (k,S[k],S0[k],R[k],R0[k],RR0[k])


def asymptoticValue(n):
  return 2.1614 * n**(-1.5) * 1.96798**n

def asymptoticValueBis(n):
  return 2.1614 * n**(-1.5) * (1.0/0.5081)**n

def main(n):
  S,R = numCanonStr(n)
  print "n\tS(n)/Asym(n)"
  for k in range(1,n+1):
    print "%d\t%f\t%f" % (k,asymptoticValue(k)/S[k], asymptoticValueBis(k)/S[k])




if __name__ == '__main__':
  if len(sys.argv)!= 2:
    print "Usage: %s integer" % sys.argv[0]
    sys.exit(1)
  main(int(sys.argv[1]))