## May 2021 - Challenge

The Fibonacci sequence is defined by F_0 = 0, F_1 = 1 and the recurrence relationship F_n = F_{n-1} + F_{n-2}.

We call any sequence A_0, A_1, A_2,\ldots **Fibonacci-like** if it satisfies the recurrences A_n = A_{n-1}+A_{n-2} for all n \ge 2.

The Fibonacci sequence contains many prime numbers. For instance, F_3 = 2, F_{11} = 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 A_0 and A_1.

- 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 \le a_k \le m_k.
- For every natural number n, we have that for some k, n is equivalent to a_k modulo m_k (i.e. m_k divides n-a_k).
- p_k is a prime divisor of the Fibonacci number F_{m_k}
- All the p_k are distinct (the m_k and a_k can be non-distinct)

- Given this set, one can generate A_0 and A_1 that satisfy
- A_0 is equivalent to F_{m_k-a_k} modulo p_k
- A_1 is equivalent to F_{m_k-a_k+1} modulo p_k

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: A_{m+n} = A_mF_{n-1} + A_{m+1}F_n.

**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 m_k elements are 2,3 and 5).

**A bonus "*"** will be given for computing A_0 and A_1 from the found set, and explaining why every element of A_n is divisible by one of the p_k elements, but not equal to it.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com

**Challenge:**
29/04/2021 @ 12:00 PM EST

**Solution:**
04/06/2021 @ 12:00 PM EST

**List Updated:**
04/06/2021 @ 12:00 PM EST

#### People who answered correctly:

***Alper Halbutogullari **(2/5/2021 9:15 AM IDT)

***Albert Stadler **(2/5/2021 9:00 PM IDT)

***Lazar Ilic **(2/5/2021 9:38 PM IDT)

**Hakan Summakoğlu **(2/5/2021 9:53 PM IDT)

***Bertram Felgenhauer **(2/5/2021 11:48 PM IDT)

**Reda Kebbaj **(3/5/2021 1:06 AM IDT)

***Chu-Wee Lim **(3/5/2021 5:17 PM IDT)

**Andreas Stiller **(4/5/2021 12:40 AM IDT)

***Victor Chang **(4/5/2021 9:04 AM IDT)

**Daniel Chong Jyh Tar **(4/5/2021 5:54 PM IDT)

***Uoti Urpala **(4/5/2021 7:25 PM IDT)

***Clive Tong **(5/5/2021 1:33 PM IDT)

***Dieter Beckerle **(5/5/2021 8:26 PM IDT)

**Andrew Mullins **(5/5/2021 11:51 PM IDT)

**Walter Sebastian Gisler **(6/5/2021 1:14 PM IDT)

**Wang Longbu **(7/5/2021 6:51 AM IDT)

**Guillaume Escamocher **(7/5/2021 2:26 PM IDT)

**Alex Fleischer **(7/5/2021 10:07 PM IDT)

**Nir Drucker **(9/5/2021 8:29 AM IDT)

**Karl D’Souza **(9/5/2021 6:27 PM IDT)

***Amos Guler **(9/5/2021 7:01 PM IDT)

***James Muir **(13/5/2021 7:17 AM IDT)

***Marco Bellocchi **(15/5/2021 2:45 AM IDT)

**Eran Vered **(17/5/2021 2:14 PM IDT)

***Latchezar Christov **(17/5/2021 5:32 PM IDT)

**David Greer **(17/5/2021 7:08 PM IDT)

**Daniel Bitin **(19/5/2021 11:27 PM IDT)

**Liubing Yu **(20/5/2021 5:53 PM IDT)

***Tim Walters **(21/5/2021 3:20 AM IDT)

**JJ Rabeyrin **(22/5/2021 4:21 PM IDT)

**Simeon Krastnikov **(23/5/2021 6:43 PM IDT)

**Lorenz Reichel **(24/5/2021 11:37 AM IDT)

**Li Li **(27/5/2021 4:31 AM IDT)

**Fabio Michele Negroni **(27/5/2021 8:28 AM IDT)

***Hansraj Nahata **(28/5/2021 12:28 AM IDT)

***Florian Fischer **(29/5/2021 12:30 AM IDT)

**Nyles Heise **(29/5/2021 7:17 AM IDT)

***Reda Kebbaj **(31/5/2021 12:13 AM IDT)

***Harald Bögeholz **(31/5/2021 5:37 AM IDT)

**Tamir Ganor & Shouky Dan **(31/5/2021 5:13 PM IDT)

**Todd Will **(31/5/2021 9:18 PM IDT)

**Reiner Martin **(1/6/2021 12:19 AM IDT)

**Radu-Alexandru Todor **(1/6/2021 1:54 AM IDT)

***Motty Porat **(2/6/2021 3:34 AM IDT)

***Oscar Volpatti **(2/6/2021 9:01 AM IDT)

***Phil Proudman **(4/6/2021 3:46 AM IDT)