由 10,000 项组成的类斐波那契数列

Question

请教我如何优化我的代码...

我正在寻找方程 a*Xn-1 - (c*c)Xn-2 的斐波那契数列。我正在寻找 GCD 为 1 的 a, c 值，这将导致从 10th 项到 10,000th 项复合的斐波那契数列。但是，对于序列中的每一项，我还希望 term + 1 的值和 term - 1 的值也是复合的。

随着数字变得非常大，代码需要很长时间才能完成。为了测试素性，我使用了 from sympy.ntheory import isprime 函数。我没有使用列表，而是使用两个变量来表示我的斐波那契数列。我正在使用递归来分析较小的间隔并逐渐向上移动到最大值。打印语句应该有助于理解代码在运行时在做什么。

这是我的代码：

from math import gcd
from sympy.ntheory import isprime


def check_pairs(a_c_pairs, start_checking_from, increment, max):
    end_checking_at = start_checking_from + increment
    pairs_that_passed_the_composite_test = []  # list of the successful pairs

    print()
    print(f"{a_c_pairs = }")
    print(f"{start_checking_from = }, {end_checking_at = }, {increment = }, {max = }")
    print()
    print(f"Number of terms to check: {len(a_c_pairs)}")

    count = 1
    for a, c in a_c_pairs:  # checking for each of the provided pairs
        print(f"{count}/{len(a_c_pairs)}: {a=}, {c=}, result=", end="")
        count += 1

        first_term = 0
        second_term = 1

        fail = False
        # iterating through each term in the sequence without using a list
        for i in range(end_checking_at):
            third_term = a*second_term - (c*c)*first_term

            if not i < start_checking_from:  # if the term is in our targeted range, check if that term is prime
                if isprime(third_term) or isprime(third_term + 1) or isprime(third_term - 1):
                    fail = True
                    print("FAIL")
                    break

            # set values for the loop to calculate the next term in the sequence
            first_term = second_term
            second_term = third_term

        if not fail:  # after the entire sequence has been analyzed, if none of the terms were prime
            print("pass")
            pairs_that_passed_the_composite_test.append([a, c])

    if not end_checking_at == max:
        check_pairs(pairs_that_passed_the_composite_test,
                    start_checking_from + increment, increment, max)
    else:
        print()
        print("FINAL LIST OF PAIRS:")
        for a, c in pairs_that_passed_the_composite_test:
            print(a, c)

        return


# these pairs have passed up to 3000 terms
a_c_pairs = [
    [11, 3],
    [34, 3],
    [37, 3],
    [38, 3],
    [40, 3],
    [41, 3],
    [53, 3],
    [56, 3],
    [59, 3],
    [61, 3],
    [65, 3],
    [71, 3],
    [77, 3],
    [82, 3],
    [89, 3],
    [94, 3],
    [95, 3],
    [98, 3],
    [37, 5],
    [39, 5],
    [42, 5],
    [43, 5],
    [46, 5],
    [51, 5],
    [54, 5],
    [57, 5],
    [64, 5],
    [73, 5],
    [74, 5],
    [77, 5],
    [86, 5],
    [89, 5],
    [91, 5],
    [98, 5],
    [53, 7],
    [55, 7],
    [64, 7],
    [71, 7],
    [75, 7],
    [79, 7],
    [81, 7],
    [83, 7],
    [87, 7],
    [92, 7],
    [99, 7],
    [100, 7],
    [86, 9],
    [89, 9],
    [94, 9],
    [97, 9],
    [98, 9]
]

check_pairs(a_c_pairs, 2000, 500, 3000)

Answer 1

检查一个数是否为质数对于巨大的数来说是昂贵的。尽管有像 AKS 这样具有多项式复杂度的算法可以做到这一点，但多项式的系数很大（即 O(n^7)，其中 n 是测试数字 N 的大小（以位为单位）。非确定性算法的多项式复杂度较低，但这仍然相当大。例如，Miller Rabin 测试可以在 O(n^4) 假设未经证实的广义黎曼假设为真（目前看来确实如此）。对于适合 64 位的中等大数字，您可以只检查几个碱基，从而进行快速素数测试。对于大量数据，研究人员正在积极致力于设计更好的算法（尤其是确定性通才无条件测试）并寻找此类算法的理论算法复杂度界限。不幸的是，AFAIK O(n^4) 接近最著名的复杂性（没有任何巨大的隐藏常量）来测试一个数字是否是复合的。

问题是斐波那契数列增长得非常快。对于标准版本，表示第 i 个元素的位数接近 2 i / 3。因此，i = 10 000 的计算时间将相当长，因为它需要处理大约 6700 位的数字，在最坏的情况下需要数百万次迭代（即素数）。目前还没有主流计算机可以快速做到这一点（可能在未来 20 年内也做不到）。

解决这个问题的唯一可能解决方案是设计一个特定的素数测试您生成的数字，乍一看这似乎是一项非常艰巨的任务。如果素数和斐波那契数之间没有关系，那么没有比使用最先进的算法更好的解决方案了（在你的情况下这太慢了）。否则，如果有任何关系，这样的问题在堆栈溢出上是题外话，但是你可以在math.stackexchange.com.

上问这个问题

一些旁注： 如果 third_term-1 是偶数，那么只需要检查 third_term （因为其他都不是质数）。如果 third_term-1 是奇数，则 third_term 不是质数，并且 third_term-1 或 third_term+1 都不是质数。此外，请注意 GCD 与斐波那契数之间存在关系，GCD 与素数之间存在关系，因此斐波那契数与素数之间可能存在关系。

由 10,000 项组成的类斐波那契数列

Fibonacci-like sequence that is composite for 10,000 terms

python

optimization

primes

largenumber

fibonacci