Reciprocal cycles

本贴最后更新于 268 天前,其中的信息可能已经时异事殊

Project Euler 第 26 题

Question

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Analysis

  1. 如果被除数是 2 的整数次幂或者 5 的整数次幂,那么结果是有限小数,可以排除出去。
  2. 按照除法的流程,如果除数小于被除数,那就乘 10,直到除数大于被除数,之后取余作为新的除数。
  3. 在被除数不变的情况下,如果除数在若干次运算后再次出现,就说明循环周期已经出现,循环小数的长度就是两次相同除数出现之间循环的次数。

Program

cycle = -1
num_list = list(range(2, 1000))
result = 0


def get_recuring_cycle(divisor, dividend):
    divisors = []
    while divisor not in divisors:
        divisors.append(divisor)
        divisor *= 10
        divisor %= dividend

    return len(divisors) - divisors.index(divisor)


tmp = 2
while tmp < 1000:
    num_list.remove(tmp)
    tmp *= 2

tmp = 5
while tmp < 1000:
    num_list.remove(tmp)
    tmp *= 5

for num in num_list:
    tmp = get_recuring_cycle(1, num)
    if tmp > cycle:
        cycle = tmp
        result = num

print(result)

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...