项目 Euler 问题 26 Python 字符串分数限制

Question

欧拉计划问题 26：

单位分数的分子中包含 1。分母为 2 至 10 的单位分数的十进制表示形式如下：

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

其中 0.1(6) 表示 0.166666...，并且具有 1 位循环周期。可见1/7有6位循环。求 d < 1000 的值，其中 1/d 在其小数部分包含最长的循环周期。

尽管我已经提供了问题的正确答案（983），但我仍然认为代码可以进一步发展，因为我认为如果 d 的值可以超过 1000，我编写的代码可能是错误的。

我认为代码可能是错误的，因为分数的字符串限制是 20，如果有一个分数超过 20 个循环周期怎么办？

我尝试使用 format() 来增加分数的字符串限制，但我意识到第 20 个字符串后面的数字不是任何重复出现的数字。

import time
import math

timeStart = time.time()

prime_numbers = []

def is_prime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return True

def numbers(n):
    for number in range(2, n):
        if is_prime(number):
            prime_numbers.append(number)

def main():
    limit = 1000
    longest_recurring_cycle = 0
    longest_value = 0

    numbers(limit)

    for d in prime_numbers:
        fraction = str(1/d)
        count = 1
        if len(fraction) > 15:
            for index, recurring_cycle in enumerate(fraction[3:10]):
                if recurring_cycle == fraction[2] and recurring_cycle == 
fraction[index + 3 + count]:
                    break
                elif count >= longest_recurring_cycle:
                    longest_recurring_cycle = count
                    longest_value = d
                count += 1
    print(longest_value)
    print(time.time() - timeStart, "seconds")

main()

tltr 我想找到一种方法来增加产生正确数字的分数的字符串限制。

Answer 1

我建议模拟长除法。即1/7的位数为10//7=1，余数为10 - 1*7 = 3。下一个小数为30//7=4。余数为2。以此类推，直到余数相等再次变为 1。然后计算周期的长度。

def cycle(denom,num=1):
    digit = None
    decimals=[]
    while digit not in decimals:
        decimals += [digit]
        digit = num * 10 // denom
        remainder = num * 10 - digit * denom
        num = remainder
        print(digit)
    return len(decimals) - decimals.index(digit)
cycle(3)