'''
    What's the probability P in a 1-D random walk with constant 
    step and probability p=0.5 of going in either direction, that
    after 2N = 200 steps the walk returns to the starting point?
    
    Do not use random number generator. Instead, compute P the 
    binomial formula
    P(n=100 steps in one direction, out of m=200 steps taken) = 
       (m,n) p**n (1-p)**(m-n), 
       where (m,n) = m!/n!/(m-n)!  is the binomial coefficient 
       usually written in a form where m i placed above
       n, not by its side like here. 
    Number N is chosen here so large that you won't be able 
    to use a numpy function evaluating factorials of integers, 
    their values simply exceeding the range of floats (overflow).
    
    SOLUTION
    
    m=2N, n=N
    (1/2)**(2N) == (1/4)**N,
    P = (2N)!/[N!N!]  * (1/2)**(2N)
    P = (N+1)(N+2)(N+3)....(2N) / [(4*1)(4*2)(4*3)...(4*N)]
    To avoid dangerously large of small numbers, we evaluate this as
    P = (N+1)/(4*1) * (N+2)/(4*2) * (N+3)/(4*3) ... 2N/(4N), 
    in direct or reverse order.
'''
n = 0
s1 = 0.; s2 = 0.; s3 = 0.
while (n<2500) :
    # comment out if you want interactive input 
    # n = int(input(" n = "))
    n += 1      of n
#     itertion for a given n
    P = 1.
    for i in range(n):
        k = n-i     # k goes from n to 1
        P = P*(n+k)/k/4
    if (n<30 or n%100==0):  print("n=",n,"   P=",P)
    s1 += P; s2 += P*P; s3 += P*P*P 
print("sums to 2500;s1,2,3=",s1,s2,s3)