IBM Research

PUZZLE   IBM-277

Fibonacci-like sequence with no primes

IBM Research · Ponder This · 2021-05

IBM Ponder This #277 · May 2021 ​

The Fibonacci sequence is defined by F0=0,F1=1 and the recurrence relationship Fn=Fn−1+Fn−2.

We call any sequence A0,A1,A2,… Fibonacci-like if it satisfies the recurrences An=An−1+An−2 for all n≥2.

The Fibonacci sequence contains many prime numbers. For instance, F3=2,F11=89, etc. Our goal is to see how to generate a fibonnaci-like sequence without any prime numbers and relatively prime initial elements. This amounts to finding suitable relatively prime A0 and A1.

The main step in the generation is finding a set [(p_1, m_1, a_1), (p_2, m_2, a_2),..., (p_t, m_t, a_t)] of triplets of the form (p_k, m_k, a_k) such that:1. 1≤ak≤mk. 2. For every natural number n, we have that for some k, n is equivalent to ak modulo mk (i.e. mk divides n−ak). 3. pk is a prime divisor of the Fibonacci number Fmk 4. All the pk are distinct (the mk and ak can be non-distinct)

Given this set, one can generate A0 and A1 that satisfy1. A0 is equivalent to Fmk−ak modulo pk 2. A1 is equivalent to Fmk−ak+1 modulo pk

and one can prove that this sequence does not contain any primes by using the following easy-to-prove identity, which holds for any Fibonacci-like sequence: Am+n=AmFn−1+Am+1Fn.

Your goal is to find the set [(p_1, m_1, a_1),..., (p_t, m_t, a_t)] of triplets satisfying conditions 1-4 described above. (Hint: A set of 18 elements exists where the only primes dividing its mk elements are 2,3 and 5).

A bonus "*" will be given for computing A0 and A1 from the found set, and explaining why every element of An is divisible by one of the pk elements, but not equal to it.

Solution

Best opened after a real attempt

To be added.