Binary Number Sequence



In [1]:

    
from itertools import product



In [2]:

    
def func(n, x, k):
    result = set()
    for suffix in product([1, 0], repeat=n):
        suffix = str(suffix).strip('(,)').replace(', ', '')
        if "0" * (k + 1) not in suffix:
            if "0" * k in suffix:
                if suffix.count('1') == (n - x):
                    result.add(suffix)
    return result



In [3]:

    
print func(4,2,1)









    



set(['0101', '0110', '1010'])



In [5]:

    
print func(5,4,2)









    



set(['00100'])



In [6]:

    
print func(7,3,1)









    



set(['1010101', '1101010', '0101101', '0111010', '0101011', '0101110', '1011010', '1010110', '0110101', '0110110'])



In [7]:

    
def funcLen(n, x, k):
    return func(n,x,k).__len__()



In [8]:

    
print funcLen(7,3,1)

No pair of consecutive zeros

Fibonacci Numbers



In [9]:

    
def noConsec(n):
    sum=1 #funcLen(n,0,0)
    for x in range(n+1):
        sum=sum+funcLen(n,x,1)
    return sum



In [10]:

    
print noConsec(5), noConsec(4), noConsec(3)



In [11]:

    
print noConsec(8), noConsec(7), noConsec(6)



In [12]:

    
print noConsec(11), noConsec(10), noConsec(9)

Sum of binary strings of length n



In [13]:

    
def cardinality(n,):
    sum=0
    for x in range(n+1):
        for k in range(x+1):
            sum=sum+funcLen(n,x,k)
    return sum



In [14]:

    
print cardinality(3)



In [15]:

    
print cardinality(4)



In [16]:

    
print cardinality(8)



In [ ]:

    
print cardinality(12)



In [24]:

    
print func(3,0,0)









    



set(['111'])

sum of binary strings of length n with x zeros



In [25]:

    
def perm(n,x):
    sum=0
    for k in range(x+1):
        sum=sum+funcLen(n,x,k)
    return sum



In [26]:

    
print perm(4,2)



In [27]:

    
print perm(7,3)



In [28]:

    
print perm(7,4)



In [29]:

    
print func(3,2,1)









    



set(['010'])

Fn(x, x) = (n -􀀀 x) + 1



In [33]:

    
print funcLen(5,1,1)



In [34]:

    
print func(5,1,1)









    



set(['11110', '11101', '01111', '11011', '10111'])



In [35]:

    
print funcLen(8,3,3)



In [36]:

    
print funcLen(9,5,5)



In [37]:

    
print funcLen(5,0,0)

Fn(x, x - 1) = (n - x)(n -􀀀 x + 1)



In [38]:

    
print funcLen(5,4,3)



In [39]:

    
print funcLen(8,5,4)



In [40]:

    
print funcLen(10,9,8)



In [41]:

    
print funcLen(6,2,1), "Exception x>=3"









    



10 Exception x>=3

Fn(x, 0) = 0



In [42]:

    
print funcLen(9,5,0)

Fn(n, k) = 0 ,k!=n



In [43]:

    
print funcLen(7,7,5)

series of length upto n



In [44]:

    
def series(n,x,k):
    lengthSeries=[]
    for i in range(x,n+1):
         lengthSeries.append(funcLen(i,x,k))
    return lengthSeries



In [45]:

    
print series(10,0,0)









    



[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]



In [46]:

    
print series(10,1,1)









    



[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]



In [47]:

    
print series(10,2,1)









    



[0, 1, 3, 6, 10, 15, 21, 28, 36]



In [48]:

    
print series(10,2,2)









    



[1, 2, 3, 4, 5, 6, 7, 8, 9]



In [ ]:

    
print series(6,3,3)

interpolation



In [49]:

    
from scipy.interpolate import *



In [50]:

    
def polynomial(list):
    x=[i*1.0 for i in range(1,len(list))]
    return lagrange(x,list)



In [51]:

    
print polynomial(series(10,5,2))









    



        4       3          2
0.1667 x - 0.5 x + 0.3333 x - 7.105e-15



In [52]:

    
print polynomial(series(10,6,4))









    



     3       2
0.5 x - 0.5 x



In [55]:

    
print polynomial(series(14,7,1))









    



          6           5          4         3         2
0.001389 x - 0.02917 x + 0.2431 x - 1.021 x + 2.256 x - 2.45 x + 1

Approximation



In [56]:

    
from fractions import Fraction



In [57]:

    
print Fraction(0.6667)









    



6005099743135819/9007199254740992



In [58]:

    
print Fraction(0.6667).limit_denominator(10000)



In [59]:

    
print Fraction(0.6667).limit_denominator(100)

2/3



In [60]:

    
print polynomial(series(10,5,2))









    



        4       3          2
0.1667 x - 0.5 x + 0.3333 x - 7.105e-15



In [62]:

    
for i in polynomial(series(10,5,2)):
    print i,









    



0.166666666667 -0.5 0.333333333333 0.0 -7.1054273576e-15



In [64]:

    
for coef in polynomial(series(10,5,4)):
    print Fraction(coef).limit_denominator(100),



In [66]:

    
for coef in polynomial(series(14,7,1)):
    print Fraction(coef).limit_denominator(1000),









    



1/720 -7/240 35/144 -49/48 203/90 -49/20 1

The Real Formula

Fn(x, k) =k-1Ei=0 Fn-i-1(x - i, k) + kEj=0 Fn-k-1(x - k, j)

Finally!!!



In [67]:

    
def formula(n, x, k):
    sum = 0
    for i in range(0, k):
        value=funcLen(n - i - 1, x - i, k)
        if value>0:
            print "F(",n-i-1,',',x-i,',',k,') is',value
        sum = sum + value
    for j in range(0, k + 1):
        value=funcLen(n - k - 1, x - k, j)
        if value>0:
            print "F(",n-k-1,',',x-k,',',j,') is',value
        sum = sum + value
    value=funcLen(n, x, k)
    print "Using formula F(",n,',',x,',',k,') is',value
    if sum == value:
        return True
    return False



In [68]:

    
print formula(6,3,2)









    



F( 5 , 3 , 2 ) is 6
F( 4 , 2 , 2 ) is 3
F( 3 , 1 , 1 ) is 3
Using formula F( 6 , 3 , 2 ) is 12
True



In [69]:

    
print formula(10,7,5)









    



F( 9 , 7 , 5 ) is 9
F( 8 , 6 , 5 ) is 6
F( 7 , 5 , 5 ) is 3
F( 4 , 2 , 1 ) is 3
F( 4 , 2 , 2 ) is 3
Using formula F( 10 , 7 , 5 ) is 24
True



In [70]:

    
print formula(3,2,2)









    



F( 2 , 2 , 2 ) is 1
F( 0 , 0 , 0 ) is 1
Using formula F( 3 , 2 , 2 ) is 2
True



In [71]:

    
print formula(2,1,1)









    



F( 1 , 1 , 1 ) is 1
F( 0 , 0 , 0 ) is 1
Using formula F( 2 , 1 , 1 ) is 2
True



In [ ]: