gistfile1.py

p = 1000000007
T = 100000

def find(x):
    for i in xrange(1,T*3/2+1):
        mul4 = (((x << 1) % p) << 1) % p # x * 4
        x0 = (mul4 + 3) % p              # x0 = 4x+3 (mod p)
        x1 = (((x0 << 1) % p) + 1) % p   # x1 = 8x+7 (mod p)
        if x0 == 0:
            return (i, 0)
        if x1 == 0:
            return (i-1, 1)
        x = x0
    return (-1, 0)

def shortest(x):
    (n0, n1) = find(x)
    if n0 >= 0:
        n0 = int(n0 / 3) * 2 + (n0 % 3)
    return n0 + n1

def reach(x, t):
    (num4, num8) = find (x)
    if num4 + num8 == t or (num4 == -1 and t == -1):
        return True
    if num4 == -1 or (num4 + num8 - t) * 3 > num4:
        return False
    return True        

def test(a, expected):
    if reach (a, expected):
        return 'ok'
    else:
        s = shortest(a)
        if s == -1:
            return 'not reachable'
        else:
            return 'not reachable %d iteration. shortest = %d' % (expected, s)

print 'loop: 1'
print test(125000000, 1)
print test(250000001, 1)
print 'loop: 2'
print test(140625000, 2)
print test(281250001, 2)
print test(562500003, 2)
print 'loop: 3'
print test(285156251, 3)
print 'loop: T (%d)' % (T,)
print test(260107256, T)
print test(705616876, T)
print 'loop: T+1 (%d)' % (T+1,)
print test(713202113, -1)