Free Fibonacci Sequences

On turning 26404 days, I couldn't help but notice the 404, a number made famous by the experience of everyone who has searched the Internet and failed to find what was being sought.

Apart from containing 404 as a subset of its digits, 26404 has some other interesting properties. Foremost amongst these is the fact that it is a member of OEIS A008892.

A008892

Aliquot sequence starting at 276.

I wrote about aliquot sequences in an eponymous post of December 20th 2017 and again, only recently, in Aliquot Sequences Revisited on June 21st 2021. 276 is the first of a sequence of numbers that are not known to be finite or periodic when the aliquot algorithm is applied. This algorithm takes as its input any integer \(n\) and returns the sum of the number's aliquot parts or proper divisors, \( \sigma(n)-n\). This output serves as the new input and the process is repeated until, most commonly, a prime number \(p\) is reached. Since \( \sigma(p)-p=1\), this means the process terminates because \( \sigma(1)=0\).

For some numbers, as far as can be determined, the process never terminates. These numbers include:

276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... and forming OEIS A131884 

In the case of 276, the sequence of numbers up to and including 26404 is:

276, 396, 696, 1104, 1872, 3770, 3790, 3050, 2716, 2772, 5964, 10164, 19628, 19684, 22876, 26404

However, this post is mainly about another interesting property of 26404 and that is its membership of OEIS A232666:

A232666

6-free Fibonacci numbers.

The OEIS comment is that:

The sequences of \(n\)-free Fibonacci numbers were suggested by John H. Conway. \(a(n)\) is the sum of the two previous terms divided by the largest possible power of 6. The sequence coincides with the Fibonacci sequence until the first multiple of 6 in the Fibonacci sequence: 144, which in this sequence is divided by 36 to produce 4.

The sequence of numbers leading to 26404 in OEIS A232666 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 4, 93, 97, 190, 287, 477, 764, 1241, 2005, 541, 2546, 3087, 5633, 8720, 14353, 23073, 37426, 60499, 97925, 26404

Here is the permalink to the generation of this sequence. There is a paper titled Free Fibonacci Sequences by Brandon Avila and Tanya Khovanova that appears in the Journal of Integer Sequences (Vol. 17 (2014), Article 14.8.5) that analyses these sequences in some detail. The authors of the paper write:

Let us denote Fibonacci numbers by \(F_k\). We define our indices such that \(F_0 = 0\) and \(F_1 = 1\). The sequence is defined by the Fibonacci recurrence: \(F_{n+1} = F_n + F_{n−1} \) (see OEIS A000045). We call an integer sequence \(a_n\) Fibonacci-like if it satisfies the Fibonacci recurrence: \(a_k = a_{k−1} + a_{k−2}\). A Fibonacci-like sequence is similar to the Fibonacci sequence, except that it starts with any two integers. The second most famous Fibonacci-like sequence is the sequence of Lucas numbers \(L_i\) that starts with \(L_0 = 2\) and \(L_1 = 1\): \(2, 1, 3, 4, 7, 11, \dots \) (see OEIS A000032). 

An \(n\)-free Fibonacci sequence starts with any two integers, \(a_1\) and \(a_2\), and is defined by the recurrence:$$a_k = \frac{a_{k−1} + a_{k−2}}{n^{ν_n(a_{k−1}+a_{k−2})}}$$where \(ν_n(x)\) is the exponent of the largest power of \(n\) that is a divisor of \(x\). To continue the tradition, we call numbers in the \(n\)-free Fibonacci sequence that starts with \(a_0 = 0\) and \(a_1 = 1\) \(n\)-free Fibonacci numbers.

The authors then go on to look at a variety of \(n\)-free Fibonacci sequences. They start with 2-free Fibonacci sequences and find that they all end in a cycle of length 1. For example, starting with \(a_0=5\) and \(a_1=10\) gives:$$5, 10, 15, 25, 5, 15, \overbrace{5}, \dots$$For 3-free Fibonacci sequences, it is suspected that all end in a cycle of \(k, k, 2k\) but it has not been proven. For example, starting with \(a_0=3\) and \(a_1=7\) gives:$$3, 7, 10, 17, 1, 2, \overbrace{1, 1, 2}, \dots$$with 1, 1, 2 repeating. Similarly, taking \(a_0=13\) and \(a_1=7\), the sequence generated is$$13, 7, 20, 1, 7, 8, 5, 13, 2, 5, 7, 4, 11, 5, 16, 7, 23, 10, 11, 7, 2, \overbrace{1, 1, 2} \dots$$ with 1, 1, 2 again repeating. The authors then go on to say that:

Consider the 4-free Fibonacci sequence starting with 0, 1. This sequence is OEIS A224382: 0, 1, 1, 2, 3, 5, 2, 7, 9, 1, 10, 11, 21, 2, 23, 25, .... It seems that this sequence grows and does not cycle. In checking many other 4-free Fibonacci sequences, we still did not find any cycles. The behaviour of 4-free sequences is completely different from the behaviour of 3-free sequences. For 3-free sequences, we expected that all of them cycle. Here, it might be possible that none of them cycles.

Let us look at the Lucas sequence mod 5: 2, 1, 3, 4, 2, 1, ... and see that no term is divisible by 5. Clearly, no term in the Lucas sequence will require that we factor out a power of 5, and the terms will grow indefinitely. Thus, the Lucas sequence is itself a 5-free Fibonacci sequence. On the other hand, it becomes quickly evident that the sequence of 5-free Fibonacci numbers: 0, 1, 1, 2, 3, 1, 4, 1, 1, 2, ... (see OEIS A214684) cycles. Some sequences cycle, and some clearly do not!

John Conway: 1937 - 2020

At the beginning of the paper, it's said that "John Horton Conway likes playing with the Fibonacci sequence. Instead of summing the two previous terms, he sums them up and then adds a twist: some additional operation." Of course, at that time, John Conway was still alive. He only died on April 11th 2020. That's a good way of thinking about the free Fibonacci sequences: Fibonacci with a twist!

I've posted frequently about Fibonacci sequences:

• The Fibonacci Number Base on July 30th 2019
• Fibonacci and Finance on April 15th 2019
• Random Fibonacci Numbers on March 9th 2020
• Dying Rabbits on June 26th 2021
• Fibonacci-like Sequences on June 10th 2020
• Finding Fibonacci and Tribonacci Seed Numbers on July 12th 2019
• Beyond Fibonacci on March 10th 2019
• Vishwanath Number on March 8th 2019
• Goldbach's Conjecture and Zeckendorf's Theorem on November 15th 2015
• Heptagonal Numbers on April 22nd 2019
• Metallic Means on March 3rd 2019

The paper contains more detailed information but the takeaway is that there is plenty of scope for further investigation of Fibonacci-like sequences with a twist. Consider this "twist" on the tribonacci sequence with initial terms of 0, 1 and 2. Each successive term is the sum of the previous three terms but (and here's the twist), if the result is a composite number, replace the term with the composite number's highest prime factor. The first terms are:

0, 1, 2, 3, 3, 2, 2, 7, 11, 5, 23, 13, 41, 11, 13, 13, 37, 7, 19, 7, 11, 37, 11, 59, 107, 59, 5, 19, 83, 107, 19, 19, 29, 67, 23, 17, 107, 7, ...

So what's going on. Well, a plot of the first 400 terms reveals the story. See Figure 1.

Figure 1: permalink

This composite number to highest prime factor "twist" is just something that popped into my head and it instantly yielded a most interesting result: a quick spike and then settling into a cycle after 255 terms. Figure 2 shows the first 1000 terms and the cycles are evident.

Figure 2: permalink

The dramatic rise and fall of the terms and their settling into an endless loop, with its own dramatic peak, are unexpected but that is what happens.