from math import *

def to_int(arr):
    ii = 0
    size = len(arr)
    while(ii < size):
        arr[ii] = int(arr[ii])
        ii += 1
    return arr

def generate_genesis_element(ee):
    cell = []
    if ee > 0:
        xx = ee%2
    else:
        xx = -1*ee%2
    aa = int(ee/2) + xx
    #nn = (xx**2 + ee)/2
    nn = 1
    bb = aa + 2*xx + 2*nn
    cc = aa*bb
    if cc > 0:
        dd = fast_sqrt(cc)
    else:
        dd = fast_sqrt(-1*cc)
    genesis = to_int([ee, nn, dd, xx, aa, bb])
    #print(genesis)

    if False: #ee <= 0:
        t0 = left_index(-1*ee)
        genesis[0] = ee
        genesis = generate_negative_element(genesis, t0)

    return genesis

#make sure input e is negative or 0
def left_index(e):
    if e%2 == 0:
        x = fast_sqrt(e/2)
        #x = int(floor(sqrt(e/2)))
        y = 2*x**2 + 2*x
        enet = y
        #print(y)
        if y > e:
            x -= 1
            z = 2*x**2 + 2*x
            enet = z
        return x + 1

    if e%2 == 1:
        if e > 7:
            x = fast_sqrt(e)
            #x = int(floor(((e-1)*3)**(1/3)))
            enet = 9 + 2*x**2 + 8*x
            while enet > e:
                x -= 1
                enet = 9 + 2*x**2 + 8*x
            return x + 2
        else:
            return 1

def fast_sqrt(num):
    if num < 6:
        return int(floor(sqrt(num)))
    else:
        n = 0
        p = 0
        if num == 0:
            return 0
        high = num >> 1
        low = 0
        while(high > low + 1):
            n = (high + low) >> 1
            p = n * n
            if num < p:
                high = n
            elif num > p:
                low = n
            else:
                break
        return n if num == p else low

def ayylgorithm4(c):
    d = fast_sqrt(c)

    # _p or _n refers to the postive or negative link element respectively
    e_p = c - d*d
    e_n = e_p - (2*d + 1)

    n_p = 1
    n_n = 1

    x_triv = d - 1
    n_triv = (x_triv**2 + e_p)/(2*1)
    trivsol_p = [e_p, n_triv, d, x_triv, 1, c]
    print("trivsol_p = " + str(trivsol_p))

    d_n = d + 1
    x_triv_n = d_n - 1
    n_triv_n = ((x_triv_n**2 + e_n)/(2*1))
    trivsol_n = [e_n, n_triv_n, d_n, x_triv_n, 1, c]
    print("trivsol_n = " + str(trivsol_n))


    genesis_p = generate_genesis_element(e_p)
    genesis_n = generate_genesis_element(e_n)

    print("genesis positive = " + str(genesis_p))
    print("genesis negative = " + str(genesis_n))

    #(c - b)/(trivsol[3] - 7) = b
    print(c / (1  + (trivsol_p[3] - 7)))
    #print(divide_from_vector(subtract_vectors(genesis_p,trivsol),3))
    print(divide_from_vector(subtract_vectors(trivsol_p,trivsol_n),1))
    x_p0 = genesis_p[3] #either 1 or 0
    #x_p = e_p%2
    x_n0 = genesis_n[3]

    a_p0 = genesis_p[4]
    a_n0 = genesis_n[4]

    b_p0 = genesis_p[5]
    b_n0 = genesis_n[5]

    g_p = (x_p0%2)*2 + 2
    g_n = (x_n0%2)*2 + 2

    f_p = 4 - g_p
    f_n = 4 - g_n

    f_n = 2*(f_n + (x_n0 - e_n%2)/2)

    f_p = 0
    f_n = 10

    q = -1*(x_p0 - x_n0 + 1)/2

    #a = r*t_p + s
    r = (f_p - f_n + 4*q)
    s = a_p0 - a_n0 - 2*q**2 + (2 + f_n)*q

    ####################################################
    #incomplete
    ####################################################


def generate_column(e, num_els):
    gen = generate_genesis_element(e)
    print(gen)
    t = 1
    while t <= num_els:
        print(generate_element(gen, t-1))
        t += 1

def generate_b(genesis_element, tt):
    b0 = genesis_element[5]
    xx = genesis_element[3]
    gg = (xx % 2)*2 + 2
    b_tt = 2*(tt)*(tt+1) + b0 + gg*(tt)
    return b_tt

def generate_element(genesis, t):
    t = t+1
    e_t = genesis[0]
    n_t = genesis[1]
    b0 = genesis[5]
    x0 = genesis[3]
    g = (x0 % 2)*2 + 2
    b_t = 2*(t)*(t+1) + b0 + g*(t)
    a_t = 2*(t-1)*(t) + b0 + g*(t-1)
    print(a_t)
    x_t = x0 + 2*t

    c_t = a_t*b_t
    d_t = fast_sqrt(c_t)
    e_t = c_t - d_t**2

    #n_t = (x_t**2 + e_t)/(2*a_t)

    return [e_t,n_t,d_t,x_t,a_t,b_t]

def generate_negative_element(genesis, t):
    e_t = genesis[0]
    n_t = genesis[1]
    b0 = genesis[5]
    x0 = genesis[3]
    g = (x0 % 2)*2 + 2
    b_t = 2*(t)*(t+1) + b0 + g*(t)
    a_t = 2*(t-1)*(t) + b0 + g*(t-1)

    x_t = x0 + 2*t

    c_t = a_t*b_t
    d_t = fast_sqrt(c_t - e_t)
    #n_t = (x_t**2 + e_t)/(2*a_t)

    return [e_t,n_t,d_t,x_t,a_t,b_t]

def subtract_vectors(A,B):
    if len(A) != len(B):
        print("Error: Input vectors of unequal lengths.")
        return -1
    C = []
    ii = 0
    while ii < len(A):
        C.append(A[ii] - B[ii])
        ii += 1
    return C

def subtract_from_vector(A, sub):
    B = []
    for each in A:
        B.append(each - sub)
    return B

def divide_from_vector(A, div):
    B = []
    for each in A:
        B.append(each/div)
    return B

def convert_element(element):
    #input: "{7:4:14:7:7:29}"
    #output: [7, 4, 14, 7, 7, 29]

    element = element.strip("{").strip("}")
    element = element.split(":")
    cell = []
    for each in element:
        cell.append(int(each))
    return cell

###############################################################
# Begin Script
###############################################################

#c = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
#c = 8876044532898802067
#c = 179426341*179424691
#c = 32416189777*32416187567
#c = 217645199*236887691
#c = 217645199*32416187567
#c = 2630492240413883318777134293253671517529
c = 203
c = 145
print("Given: c = " + str(c) + " = a*b")
d = fast_sqrt(c)
print("d = " + str(d))
e = c - d**2
print("e = " + str(e))
gc = generate_genesis_element(e)
print("Genesis row at (e,1) = " + str(gc))

ayylgorithm4(c)
#print(generate_genesis_element(-246))