#!/usr/bin/env python

# we use two method to get the Eulercoins
# 1. iterate over the sequence
# 2. find the *n* such that for a given number *a*, mul*n=a (mod g)

mul = 1504170715041707
mod = 4503599627370517

# gcdrev(a,b)=(g,a',b')
# - g is gcd(a,b)
# - a'a+b'b=g
# gcdrev_ calculates one (a',b') answer, while gcdrev() makes a'>=0

def gcdrev_(a,b):
    if a == 0 and b == 0:
        raise ValueError

    if a == 0:
        return b,0,1

    if b == 0:
        return a,1,0

    q = a // b
    g,aa,bb = gcdrev_(b,a%b)
    return g,bb,(aa-q*bb)

def gcdrev(a,b):
    if b <= 0:
        raise ValueError

    g,x0,y0 = gcdrev_(a,b)
    if x0 < 0:
        t = (-x0 + b - 1) // b
        x = x0 + t * b
        y = y0 - t * a
        return g,x,y
    else:
        t = x0 // b
        x = x0 - t * b
        y = y0 + t * a
        return g,x,y

def main():
    sum_of_coins = 0
    g,r,_ = gcdrev(mul,mod) # actually g is 1

    # we use the second method, until the smallest n is smaller than the coin
    print("======== First run ========")
    coin = g
    n_min = mod
    while coin < n_min:
        n = coin * r % mod
        if n < n_min:
            n_min = n
            sum_of_coins = sum_of_coins + coin
            print("n = {}, coin = {}".format(n, coin))

        coin = coin + g

    # then use the first method, until n >= n_min
    print("======== Second run ========")
    mincoin = mod
    n = 1
    coin = mul % mod
    while n < n_min:
        if coin < mincoin:
            sum_of_coins = sum_of_coins + coin
            mincoin = coin
            print("n = {}, coin = {}".format(n,coin))

        n = n + 1
        coin = (coin + mul) % mod

    print(sum_of_coins)

if __name__ == "__main__":
    main()