Ponder This Challenge - May 2021 - Fibonacci-like sequence with no primes

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$. 2. 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$). 3. $p_k$ is a prime divisor of the Fibonacci number $F_{m_k}$ 4. 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 satisfy1. $A_0$ is equivalent to $F_{m_k-a_k}$ modulo $p_k$ 2. $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

Solution

• Click here to view the solution

  As many have pointed out, this problem was originally solved by Ronald Graham who found a specific set of triplets ( "A Fibonacci-like sequence of composite numbers" , also given in the excellent book "Concrete mathematics"). The challenge here was not copying the set from the paper!

  Alternative sets can also be given, such as
  s = [[2, 3, 3], [3, 4, 4], [5, 5, 5], [7, 8, 1], [17, 9, 1], [11, 10, 1], [61, 15, 2], [47, 16, 2], [19, 18, 7], [41, 20, 3], [23, 24, 14], [31, 30, 29], [2207, 32, 10], [107, 36, 22], [2161, 40, 13], [109441, 45, 4], [1103, 48, 26], [103681, 72, 70], [181, 90, 67], [769, 96, 58]]

  Yielding
  A0 = 44186851375096125029100906489607183486440
  A1 = 23990976680675392254644252020033167422281

Solvers

• *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)