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)