斐波那契数列 - 非常大的 n 个数的六个最重要的数字（最右边）

Question

我试图通过仅保留最右边的六位数字来有效地计算可能非常大的第 n 个斐波那契值。例如 fib(1000000) 将 return 只有 546875.

我知道一些递归矩阵求幂算法，并且我一直在测试 O(log n) 实现，如下所示 -

def solution(n):
    fibs = {0: 0, 1: 1}

    def fib(n):
    # recursive helper function
        if n in fibs: 
            return fibs[n]
        if n % 2 == 0:
            fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2) % 1000000
            return fibs[n]
        else:
            fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2) % 1000000
            return fibs[n]

    answer = fib(n)
    return answer % 1000000

在 n = 1000000 之前，所有答案似乎都有效。10 return 之后的所有指数都应该是相同的答案吗？ 10^k where k = [7, 8, 9, 10...] all return 546875（价值一百万）。我假设它们应该是因为当您将它们乘以 10^6 时，这些值具有相同的零余数。所以我想知道这个实现是否正确？

Answer 1

所以我对 prove/disprove 你当前的定理做了一些简单的代码，我偶然发现了这个特殊的模式：代码最后 6 位的斐波那契数列似乎每 150 万个数列重复一次。

这是 100 万、1000 万、1 亿等值匹配的部分原因； 1000 万 - 900 万 = 100 万，但 900 万 = 6 * 150 万。

因此，要回答您的问题，您需要在代码中实现的是首先对 n 取模 1,500,000，然后计算您的答案，例如：

answer = fib(n%1500000)

我在下面提供了用于查找模数重复时的代码 (find_repeating_length) 以及检查模数是否按预期工作（检查）的函数。

希望对您有所帮助！

def solution(n):
    fibs = {0: 0, 1: 1}

    def fib(n):
        # simple linear-time fib function
        if n in fibs:
            return fibs[n]
        fibs[n] = (fibs[n-1]+fibs[n-2]) % 1000000
        return fibs[n]

    def find_repeating_length():
        find_number = [0, 1] # find these two numbers of the sequence
        for i in range(0, 10000001):
            n_0 = fib(i)
            if (n_0 in find_number):
                print(str(n_0) + ":" + str(i))

    def check(): # check that first 10,000,000 nums follow sequence
        for i in range(2, 10000001): 
            n_0 = fib(i)
            if (i >= 1500000):
                left = n_0
                right = fib(i - 1500000)
                # if (left == right):
                #    print("Success at " + str(i) + " Values: " +
                #          str(n_0))
                if (left != right):
                    return("Fail at " + str(i) + " Values: " +
                           str(n_0) + ":" + str(right))

            return "Success, repeats"
    find_repeating_length()
    print(check())


solution()

输出（稍微格式化，以value:sequence格式输出）：

0:0 1:1 1:2 0:750000 1:1499999

0:1500000 1:1500001 1:1500002 0:2250000 1:2999999

0:3000000 1:3000001 1:3000002 0:3750000 1:4499999

0:4500000 1:4500001 1:4500002 0:5250000 1:5999999

0:6000000 1:6000001 1:6000002 0:6750000 1:7499999

0:7500000 1:7500001 1:7500002 0:8250000 1:8999999

0:9000000 1:9000001 1:9000002 0:9750000

Success, repeats

斐波那契数列 - 非常大的 n 个数的六个最重要的数字（最右边）

Fibonacci - six most significant digits (right most) of very large n numbers

python

fibonacci