斐波那契-很大的n个数字的六个最高有效数字（最右边）

Question

我正在尝试仅保留最右边的六个数字来有效地计算第n个斐波那契值，该值可能非常大。例如fib（1000000）仅返回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指数都应该返回相同的答案吗？ 10 ^ k，其中k = [7、8、9、10 ...]全部返回546875（一百万的值）。我认为它们应该是因为当您将它们乘以10 ^ 6时，这些值具有相同的零余数。所以我想知道这种实现是否正确？

Answer 1

因此，我做了一些简单的代码来证明/反证您当前的定理，然后我偶然发现了这种特定模式：代码的最后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()

输出（格式简短，以值：序列格式输出）：

0：01：11:20：7500001：1499999

0：15000001：15000011：15000020：22500001：2999999

0：30000001：30000011：30000020：375万1：4499999

0：45000001：45000011：45000020：52500001：5999999

0：60000001：60000011：60000020：67500001：7499999

0：75000001：75000011：75000020：82500001：8999999

0：90000001：90000011：90000020：9750000

成功，重复