p167

p167.py

def delta(x):
    if x == 0:
        return 1
    return 0 

def Ulam(v, t):
    # See S. R. Finch, Patterns in 1-additive sequences, Experimental Mathematics 1 (1992), 57-63.
    a = 2
    e2 = 2*v + 2
    #Finding the starting part of the sequence
    u = [a] + [x for x in range(v, e2, 2)] + [e2]
    b = [0]
    for x in range(3, e2, 2):
        if x in u:
            b.append(1)
        else:
            b.append(0)

    n = (e2 - 1)//2 + 1
    cs = None
    #Start computing the rest of the sequence
    while True:
        curr = 2*n + 1
        bn = delta(b[n - 1] - 1) + delta(b[n - v - 1] - 1)
        
        if bn == 1:
            u.append(curr)
            
            if u[-1] - u[-2] == e2:
                #We have reached the periodic point
                if cs == None:
                    #if it's the first time we keep track
                    cs = len(u) - 2
                else:
                    #Secon time we stop searching
                    ce = len(u) - 2
                    break
            
        b.append(bn)
        n += 1
    if t < ce:
        return u[t]
    
    p = ce - cs #period length
    diff = u[ce] - u[cs]
    #Find the element we want directly using period length and difference
    return (t - cs)//p * diff + u[(t - cs) % p + cs - 1], p

def compute():
    total = 0 
    for n in range(2, 11):
        t, p = Ulam(2*n + 1, 10**11)
        total += t
    return total