"三博纳奇"序列

Question

我们有一个前3个元素的序列: t_1 = t_2 = t_3 = 1

序列的其余部分由规则定义:( t_n = t_(n-1) + t_(n-2) + t_(n-3)与Fibonacci序列相似,但对于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

正如Project Euler 对此问题的描述所述:

可以证明27不会划分该序列的任何术语.

为了证明这一点,你显然不会将tribonacci序列计算为无穷大,以检查27不会划分任何数字.必须有一个数学快捷方式来证明这一点,如果我们能找到这个快捷方式,我们可以用它来检查其他数字是否划分了tribonacci序列.

检查数字是否除以27与检查模数27是否等于0相同.

如果我们采用模数为27的tribonacci序列,我们得到:

  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序列的算法将是:

• 从数字a = 1开始,b = 1,c = 1
• Calucate d =(a + b + c)%n
• 如果d = 0则返回true (n除以tribonacci序列中的数字)
• 设a = b,b = c,c = d
• 如果a = 1且b = 1且c = 1则返回false (重复开始)
• 重复a,b和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值.当测试值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