About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
May 2021 - Challenge
The Fibonacci sequence is defined by and the recurrence relationship
.
We call any sequence Fibonacci-like if it satisfies the recurrences
for all
.
The Fibonacci sequence contains many prime numbers. For instance, , 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
and
.
- 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:
-
.
- For every natural number n, we have that for some k, n is equivalent to
modulo
(i.e.
divides
).
-
is a prime divisor of the Fibonacci number
- All the
are distinct (the
and
can be non-distinct)
- Given this set, one can generate
-
is equivalent to
modulo
-
is equivalent to
modulo
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: .
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 elements are 2,3 and 5).
A bonus "*" will be given for computing and
from the found set, and explaining why every element of
is divisible by one of the
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)