python - "Three-bonacchi"序列

Question

我们有一个包含前 3 个元素的序列:t_1 = t_2 = t_3 = 1
序列的其余部分由规则定义:t_n = t_(n-1) + t_(n-2) + t_(n-3) (类似于斐波那契数列，但适用于 3 个数字)。

t = {1; 1; 1; 3; 5; 9; 17; 31; ...}

任务是找到第 N 个奇数，它不是序列中任何元素的除法器。

Input: N (1 <= N <= 10^4 )

Output: N-th number which satisfies the condition.

例子:

Input: 125

Output: 2025

我的直接解决方案太慢了。我应该如何改进/更改算法以在给定限制(N <= 10^4)的情况下在 1 秒内完成工作？

t = [1, 1, 1]
N = int(input())  # find N-th odd number which isn't a divider of any number in the sequence
counter = 0  # how many appropriate numbers we've already found
curr_number = 1  # number to check

for i in range(100000):
    t.append(t[-1] + t[-2] + t[-3])


while counter < N:
    curr_number += 2

    for i in range(len(t)):
        if t[i] % curr_number == 0:
            break
    else:
        counter += 1

print(curr_number)

Answer 1

正如欧拉计划的 description 中所述这个问题的:

It can be shown that 27 does not divide any terms of this sequence.

为了证明这一点，您显然不会将 tribonacci 数列计算为无穷大来检查 27 没有除以任何数字。必须有一个数学捷径来证明这一点，如果我们能找到这个捷径，我们就可以用它来检查其他数字是否可以整除三角序列。

检查一个数是否被 27 除与检查数模 27 是否等于 0 是一样的。

如果我们对 tribonacci 序列取模 27，我们得到:

  1 % 27 =  1  
  1 % 27 =  1  
  1 % 27 =  1  
  3 % 27 =  3  
  5 % 27 =  5  
  9 % 27 =  9  
 17 % 27 = 17  
 31 % 27 =  4  
 57 % 27 =  3  
105 % 27 = 24  
193 % 27 =  4
...

您会注意到，为了找到 193 % 27 = 4，我们不需要使用数字 193(因为它等于 31 + 57 + 105)，我们可以使用前三个数字的模数:

(4 + 3 + 24) % 27 = 4

这意味着我们不需要实际的 tribonacci 序列来检查 27 是否将它整除。我们只需要查看模数序列以检查是否找到零:

  1            % 27 =  1  
  1            % 27 =  1  
  1            % 27 =  1  
( 1 +  1 +  1) % 27 =  3
( 1 +  1 +  3) % 27 =  5  
( 1 +  3 +  5) % 27 =  9  
( 3 +  5 +  9) % 27 = 17  
( 5 +  9 + 17) % 27 =  4  
( 9 + 17 +  4) % 27 =  3  
(17 +  4 +  3) % 27 = 24  
( 4 +  3 + 24) % 27 =  4  
...

由于此序列仅包含 27 以下的数字，因此任何三个连续数字的可能性数量有限，并且在某些时候，将出现三个连续数字，而这些数字已经在序列中较早出现过。

任何三个特定数字总是会产生相同的第四个数字，这意味着如果三个连续数字的组合重复，则其后的整个序列将重复。因此，如果没有找到零，并且序列开始重复，那么您知道永远不会有零，并且该数字不会划分 tribonacci 序列。

还需要注意的是，序列中任意三个连续的数字只能是前一个特定数字的结果；例如序列 [3, 24, 4] 前面只能有数字 4。这意味着重复将从序列的开头开始。因此，要在找到零之前检查序列是否重复，我们只需找到前三个数字的重复:[1, 1, 1]。

这也意味着我们在计算时不必存储整个序列，我们可以继续用 [b, c, (a + b + c) % n] 替换 [a, b, c]，并进行比较它们与 [1, 1, 1]。

在 27 的情况下，序列在 117 个数字后重复:

1, 1, 1, 3, 5, 9, 17, 4, 3, 24, 4, 4, 5, 13, 22, 13, 21, 2, 9, 5, 16, 3, 24, 16, 16, 2, 7, 25, 7, 12, 17, 9, 11, 10, 3, 24, 10, 10, 17, 10, 10, 10, 3, 23, 9, 8, 13, 3, 24, 13, 13, 23, 22, 4, 22, 21, 20, 9, 23, 25, 3, 24, 25, 25, 20, 16, 7, 16, 12, 8, 9, 2, 19, 3, 24, 19, 19, 8, 19, 19, 19, 3, 14, 9, 26, 22, 3, 24, 22, 22, 14, 4, 13, 4, 21, 11, 9, 14, 7, 3, 24, 7, 7, 11, 25, 16, 25, 12, 26, 9, 20, 1, 3, 24, 1, 1, 26, 1, 1, 1 ...

因此，检查数字 n 是否可以整除 tribonacci 序列的算法将是:

• Start with the numbers a = 1, b = 1, c = 1
• Calucate d = (a + b + c) % n
• If d = 0 return true (n divides a number from the tribonacci sequence)
• Set a = b, b = c, c = d
• If a = 1 and b = 1 and c = 1 return false (beginning of repetition found)
• Repeat with new values for a, b and c

此代码示例适用于任何 N 值，但显然不够快，无法在不到一秒的时间内找到第 10000 个奇数非整除数(即 134241)。

var N = 125, n = 1, count = 0;
while (count < N) {
    var a = 1, b = 1, c = 1, d;
    n += 2;
    while (d = (a + b + c) % n) {
        a = b; b = c; c = d;
        if (a == 1 && b == 1 && c == 1) {
            ++count;
            break;
        }
    }
}
document.write(N + ": " + n);

我发现第一个零总是出现在第一个相同的三元组 [a=b=c] 之前，而不仅仅是在 [1,1,1] 之前，因此您可以将测试更改为 a == b && b == c使其运行速度提高约三倍。

var N = 125, n = 1, count = 0;
while (count < N) {
    var a = 1, b = 1, c = 1, d;
    n += 2;
    while (d = (a + b + c) % n) {
        a = b; b = c; c = d;
        if (a == b && b == c) {
            ++count;
            break;
        }
    }
}
document.write(N + ": " + n);

但即使使用 C 而不是 JavaScript，使用这种方法找到第 10000 个奇数的非整除数也需要几分钟而不是几秒钟。可以使用@rici 的答案中的筛选想法进行进一步改进，但如果真的有可能将其降低到一秒以下，那么必须有一个额外的数学捷径仍然无法实现。

下面的代码示例使用了增量筛，因此它不需要具有预定义的大小，并且可以用于 N 的任何值。倍数 3×n 被设置为值 n，或者如果它已经被标记为另一个非除法器的倍数，则 5×n 或 7×n 或 ... 被设置为 n。当认为值 n 被标记为筛中非除数的倍数时，标记将移动到该非除数的下一个奇数倍。

function Sieve() {                          // incremental sieve
    this.array = [];                        // associative array
}
Sieve.prototype.add = function(n) {
    var base = n;
    while (this.array[n += (2 * base)]);    // find first unset odd multiple of n
    this.array[n] = base;                   // set to base value
}
Sieve.prototype.check = function(n) {
    var base = this.array[n];               // get base value
    if (! base) return false;               // if not set, return
    delete this.array[n];                   // delete current multiple
    while (this.array[n += (2 * base)]);    // find next unset odd multiple
    this.array[n] = base;                   // set to base value
    return true;
}
function dividesTribonacci(n) {
    var a = 1, b = 1, c = 1, d;
    while (d = (a + b + c) % n) {
        a = b; b = c; c = d;
        if (a == b && b == c) return false; // identical triple found
    }
    return true;                            // zero found, n divides tribonacci
}
function NthOddNonDivider(N) {
    var n = 1, count = 0, sieve = new Sieve();
    while (count < N) {
        while (sieve.check(n += 2)) {       // skip multiples of non-dividers
            if (++count == N) return n;
        }
        if (! dividesTribonacci(n)) {
            ++count;
            sieve.add(n);
        }
    }
    return n;
}
document.write(NthOddNonDivider(125));      // 2025