######################################################### # # # Coded by Indranil Ghosh (indranilg49@gmail.com) # # # ######################################################### #Python 2.7.11, OEIS sequence: A071662 from sympy import binomial, factorial as f, floor def a072643(n): i=c=0 a=1 while n>c: a*=(4*i + 2)/(2 + i) i+=1 c+=a return i def a014137(n): return sum([f(2*k)/(f(k)**2*(k + 1)) for k in xrange(n + 1)]) def a009766(n, k): return 0 if k<0 or k>n else binomial(n + k + 1, k)*(n + 1 - k)/(n + 1 + k) def CatalanUnRank(n, rr): r=(binomial(2*n, n)/(n + 1)) - (rr + 1) a=lo=0 t=n y=n - 1 while t>0: m=a009766(t, y) if r<(lo + m): y-=1 a=2*a + 1 else: lo+=m t-=1 a*=2 return a def a014486(n): return 0 if n==0 else CatalanUnRank(a072643(n), (n - a014137(a072643(n) - 1))) def a036044(n): return 1 if n==0 else int((''.join('1' if i == '0' else '0' for i in bin(n)[2:]))[::-1], 2) def a080166(n): l=0 while n>0: l+=(-1)**n if l<0: return 0 n=floor(n/2) return 0 if l>0 else 1 def a030101(n): return int(bin(n)[2:][::-1], 2) def a014137(n): return sum([f(2*k)/((f(k))**2*(k + 1)) for k in xrange(n + 1)]) def a215406(n): m=floor(len(bin(n)[2:])/2) A=a030101(n) y=0 t=1 for x in xrange(1, 2*m): u=2*m - x v=m - (x + y + 1)/2 mn=binomial(u, v) - binomial(u, v - 1) t+=mn*(1 - A%2) y-=(-1)**A A=floor(A/2) return a014137(m) - t def a080300(n): return a080166(n)*a215406(n) def a070939(n): return len(bin(n)[2:]) def NextSubBinTree(N): n=N c=z=0 while c<1: z=2*z + n%2 c+=(-1)**n n=floor(n/2) return z def BinTreeLeftBranch(n): return NextSubBinTree(floor(n/2)) def BinTreeRightBranch(n): return NextSubBinTree(floor(n/(2**(1 + a070939(BinTreeLeftBranch(n)))))) def ReflectBinTreeAux(n): a=ReflectBinTree2(BinTreeLeftBranch(n)) b=ReflectBinTree2(BinTreeRightBranch(n)) return 2**(a070939(b) + a070939(a)) + b*(2**a070939(a)) + a def ReflectBinTree2(n): return 0 if n==0 else ReflectBinTreeAux(a030101(n)) def ReflectBinTree(n): return ReflectBinTree2(n)/2 def a057163(n): return a080300(ReflectBinTree(a014486(n))) def a057164(n): return a080300(a036044(a014486(n))) def a057506(n): return a057163(a057164(n)) def a(n): return a057506(a057506(n)) print [a(n) for n in xrange(101)]