1到n个人排成一圈，从编号为1的人开始，依次说白，黑，白，黑，。。。，说到黑的人离队，问最后留下编号为几的人。

who_is_the_lucky_dog.py

# encoding: utf-8
# http://weibo.com/1915548291/CqcYV0Ga3
# 1到n个人排成一圈，从编号为1的人开始，依次说白，黑，白，黑，。。。，说到黑的人离队，问最后留下编号为几的人。


def who_is_the_lucky_dog(n):
    if n < 1:
        return 'n must be greater than 0'
    elif n == 1:
        return 1
    else:
        if n % 2 == 0:
            return who_is_the_lucky_dog(n / 2) * 2 - 1
        else:
            x = who_is_the_lucky_dog((n + 1) / 2)
            return n if x == 1 else 2 * x - 3


if __name__ == '__main__':
    print who_is_the_lucky_dog(99999999999999999999999999999999999999999999999999999999999999999999)
    seq = range(1, 100)
    print '\n'.join(["n = %s, it's %s" % item for item in zip(seq, map(who_is_the_lucky_dog, seq))])

# 92160213331397440821331939651921477305451422309837710075585559003135
# n = 1, it's 1
# n = 2, it's 1
# n = 3, it's 3
# n = 4, it's 1
# n = 5, it's 3
# n = 6, it's 5
# n = 7, it's 7
# n = 8, it's 1
# n = 9, it's 3
# n = 10, it's 5
# n = 11, it's 7
# n = 12, it's 9
# n = 13, it's 11
# n = 14, it's 13
# n = 15, it's 15
# n = 16, it's 1
# n = 17, it's 3
# n = 18, it's 5
# n = 19, it's 7
# n = 20, it's 9
# n = 21, it's 11
# n = 22, it's 13
# n = 23, it's 15
# n = 24, it's 17
# n = 25, it's 19
# n = 26, it's 21
# n = 27, it's 23
# n = 28, it's 25
# n = 29, it's 27
# n = 30, it's 29
# n = 31, it's 31
# n = 32, it's 1
# n = 33, it's 3
# n = 34, it's 5
# n = 35, it's 7
# n = 36, it's 9
# n = 37, it's 11
# n = 38, it's 13
# n = 39, it's 15
# n = 40, it's 17
# n = 41, it's 19
# n = 42, it's 21
# n = 43, it's 23
# n = 44, it's 25
# n = 45, it's 27
# n = 46, it's 29
# n = 47, it's 31
# n = 48, it's 33
# n = 49, it's 35
# n = 50, it's 37
# n = 51, it's 39
# n = 52, it's 41
# n = 53, it's 43
# n = 54, it's 45
# n = 55, it's 47
# n = 56, it's 49
# n = 57, it's 51
# n = 58, it's 53
# n = 59, it's 55
# n = 60, it's 57
# n = 61, it's 59
# n = 62, it's 61
# n = 63, it's 63
# n = 64, it's 1
# n = 65, it's 3
# n = 66, it's 5
# n = 67, it's 7
# n = 68, it's 9
# n = 69, it's 11
# n = 70, it's 13
# n = 71, it's 15
# n = 72, it's 17
# n = 73, it's 19
# n = 74, it's 21
# n = 75, it's 23
# n = 76, it's 25
# n = 77, it's 27
# n = 78, it's 29
# n = 79, it's 31
# n = 80, it's 33
# n = 81, it's 35
# n = 82, it's 37
# n = 83, it's 39
# n = 84, it's 41
# n = 85, it's 43
# n = 86, it's 45
# n = 87, it's 47
# n = 88, it's 49
# n = 89, it's 51
# n = 90, it's 53
# n = 91, it's 55
# n = 92, it's 57
# n = 93, it's 59
# n = 94, it's 61
# n = 95, it's 63
# n = 96, it's 65
# n = 97, it's 67
# n = 98, it's 69
# n = 99, it's 71