Tribonacci Non-divisors

The sequence $1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, \dots$
is defined by $T_1 = T_2 = T_3 = 1$ and $T_n = T_{n – 1} + T_{n – 2} + T_{n – 3}$.

It can be shown that $27$ does not divide any terms of this sequence.In fact, $27$ is the first odd number with this property.

Find the $124$th odd number that does not divide any terms of the above sequence.

This problem involves modular arithmetic to a high degree.

The given sequence is defined by $T_1 = T_2 = T_3 = 1$ and $T_n = T_{n – 1} + T_{n – 2} + T_{n – 3}$. This sort of sequence is known as a linear recurrence sequence.

Once you recognize $T_n = T_{n – 1} + T_{n – 2} + T_{n – 3}$, it is easy to establish a pattern. Let’s look at the sequence modulo 3:

$1, 1, 1, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0$.

Notice the pattern of $(1, 1, 1, 0, 2, 2)$ repeats. Since $0$ is included, which means that $3$, or any multiple of $3$, cannot be a divisor of any term in the sequence.

Next, let’s look at the sequence modulo 5:

$1, 1, 1, 3, 0, 4, 2, 1, 2, 2, 0, 3, 0, 3, 3, 2, 1, 1,…$

Notice that the pattern $(1, 1, 3, 0, 4, 2)$ repeats and again includes $0$, base of $5$ or any multiple of $5$ cannot be a divisor.

This tells us that any term of the sequence is not divisible by any number whose prime factors are $3, 5, 3^2, 5^2, 3*5,$ etc. This precisely hits all odd multiples of $3$ (those not divisible by $5$) and all odd multiples of $5$ (those not divisible by $3$) up through all odd multiples less than $90 = 2 * 3^2 * 5$.

Any odd number larger than $90$ and whose prime divisors are only composed of $3$ and $5$ (but not divisible by $3^2$ or $5^2$) is also not allowed, as due to the Chinese Remainder Theorem, we can just consider them modulo $90$.

This leaves us with $n(2n – 1)$ for odd $n$ and where $2n – 1$ is prime as possible candidate for divisors of our sequence, which in fact gives the potential divisors $7$, $21$, $39$, $63$, $93$, $129$, $171$, $219$, $273$, … , but $63$ is a multiple of $3^2$ and $273$ is a multiple of $3 * 7$, so they don’t work.

This means for our task, we only need to find the $124$th odd prime where neither the prime nor twice the prime is of the form $3^a * 5^b$ (where $a > 2$ or $b > 1$).

Computing this gives the prime as $337$, so our answer is $2 * 337 = \boxed{674}$.

More Answers: