p186

p186.py

def compute(p, number = 524487):
    S = [0]
    #V keeps tracks of which connected component vertex i is in
    V = [i for i in range(10**6)]
    #These are the connected components of the graph, initially every vertex is in its own connected component
    #The head of the connected component is itself
    cc = {i:set([i]) for i in range(10**6)}
    k = 1
    calls = 0 
    while True:
      #Generate the caller and the called
        if k < 56:
            caller = (100003 - 200003*k + 300007*pow(k, 3, 10**6)) % 10**6 
            k += 1
            if k < 56:
                called = (100003 - 200003*k + 300007*pow(k, 3, 10**6)) % 10**6
            else:
                called = (S[k - 24] + S[k - 55]) % 10**6
            k += 1
        else:
            caller = (S[k - 24] + S[k - 55]) % 10**6
            called = (S[k - 23] + S[k - 54]) % 10**6
            k += 2
        S += [caller, called]
        #Esnsure we don't misdial
        if caller != called:
            #Get the connected component of the caller and the called from V
            cc_caller = V[caller]
            cc_called = V[called]
            #Since caller and called are now connected, merge their connected components
            #Merge into the one with the smaller head
            if cc_caller > cc_called:
                #For each element in connected component with the bigger head, we need to repoint each element to the new connected component
                for x in cc[cc_caller]:
                    V[x] = cc_called
                #Merge them, delete the the old connected component
                cc[cc_called] |= cc[cc_caller]
                del cc[cc_caller]
            #Same as above but for other case
            if cc_caller < cc_called:
                for x in cc[cc_called]:
                    V[x] = cc_caller
                cc[cc_caller] |= cc[cc_called]
                del cc[cc_called]
            calls += 1
        #If the connected component the prime ministr is in has more than p/100 * 10**6 = p * 10**4 members we are done
        if len(cc[V[number]]) > p*10**4 - 1:
            return calls