"Three-bonacchi" sequence

Question

We have a sequence with first 3 elements: t_1 = t_2 = t_3 = 1

The rest of the sequence is defined by rule: t_n = t_(n-1) + t_(n-2) + t_(n-3) (like Fibonacci sequence but for 3 numbers).

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

The task is to find the N-th odd number which isn't a divider of any element of the sequence.

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

Output: N-th number which satisfies the condition.

Example:

Input: 125

Output: 2025

My straight solution works too slow. How should I improve/change the algorithms to finish the work in 1 second with given restrictions (N <= 10^4)?

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

As stated in Project Euler's description of this problem:

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

To prove this, you obviously don't calculate the tribonacci sequence to infinity to check that 27 doesn't divide any of the numbers. There must be a mathematical shortcut to prove this, and if we can find this shortcut, we can use it to check whether other numbers divide the tribonacci sequence.

Checking whether a number is divided by 27 is the same as checking whether the number modulo 27 equals 0.

If we take the tribonacci sequence modulo 27, we get:

  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
...

You'll notice that in order to find that 193 % 27 = 4, we don't need to use the number 193 (because it equals 31 + 57 + 105) and we could just use the modulo's of the previous three numbers:

(4 + 3 + 24) % 27 = 4

This means we don't need the actual tribonacci sequence to check whether 27 divides it. We only need to look through the sequence of modulo's to check whether we find a zero:

  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  
...

Since this sequence only contains numbers below 27, there is a limited number of possibilities for any three consecutive numbers, and at some point three consecutive numbers will appear that have already appeared earlier in the sequence.

Any three specific numbers will always result in the same fourth number, which means that if a combination of three consecutive numbers is repeated, the whole sequence thereafter will be repeated. So if no zero has been found, and the sequence starts to repeat, you know there will never be a zero, and the number doesn't divide the tribonacci sequence.

It is also important to note that any three consecutive numbers in the sequence can only be the result of a specific previous number; e.g. the sequence [3, 24, 4] can only be preceeded by the number 4. This means that the repetition will start from the beginning of the sequence. So to check whether the sequence repeats before a zero is found, we only have to find a repetition of the first three numbers: [1, 1, 1].

This also means we don't have to store the whole sequence while we're calculating it, we can keep replacing [a, b, c] by [b, c, (a + b + c) % n], and comparing them with [1, 1, 1].

In the case of 27, the sequence repeats after 117 numbers:

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 ...

So the algorithm to check whether a number n divides the tribonacci sequence would be:

• 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

---

This code example will work for any value of N, but it's obviously not fast enough to find the 10000th odd non-dividing number (which is 134241) in less than a second.

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);

I found that the first zero always comes before the first identical triplet [a=b=c], not just before [1,1,1], so you can change the test to a == b && b == c to make it run about three times faster.

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);

But even when using C instead of JavaScript, finding the 10000th odd non-dividing number with this method takes minutes rather than seconds. Further improvements can be made using the sieve idea from @rici's answer, but if it's really possible to get it down below one second there must be an additional mathematical shortcut that's still eluding us.

---

The code example below uses an incremental sieve, so that it doesn't need to have a predefined size, and can be used for any value of N. When a value n is tested and found to be a non-divider, its first odd multiple 3×n is set to the value n, or if that is already marked as a multiple of another non-divider, 5×n or 7×n or ... is set to n. When a value n is considered that is marked as a multiple of a non-divider in the sieve, the mark is moved to the next odd multiple of that non-divider.

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