Challenge: The Sequence of Fibonacho

• Sequence Definition and Initial Values
• Part 1: Understanding the Problem & Deriving the Recurrence Relation
• Part 2: Predicting Digits at Larger Indices
• Part 3: Scaling Up!

The Fibonacho Sequence is a intriguing twist on the classical Fibonacci numbers. Unlike its better-known cousin, the Fibonacho Sequence does not follow the same simple recurrence relation. Instead, it introduces a slightly different structure, making it an entertaining little puzzle for math enthusiasts and programmers alike.

In this challenge, you will explore the sequence’s definition, uncover its recurrence relation, and tackle a series of progressively more complex questions. Starting with small values and scaling up to massive indices, the goal is to unlock the underlying properties of this unique sequence, culminating in the analysis of numbers with hundreds of digits.

Are you ready to dive into the challenge and see how far your skills can take you? Let’s get started!

Sequence Definition and Initial Values

The Fibonacho Sequence starts with a few predefined values and grows according to a hidden pattern. Unlike the Fibonacci sequence, which has a simple and elegant formula, the Fibonacho Sequence is less straightforward. Below is a table of the first few elements, \(F_n\) , of the Fibonacho Sequence:

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Fn	0	0	0	1	1	1	2	4	6	9	15	25	40	64	104	169	273	441	714	115	1870

Furthermore, you are given \(F_{100} = 97905340104793732225\). Notice how the sequence grows, but not in the same way as the Fibonacci numbers.

Part 1: Understanding the Problem & Deriving the Recurrence Relation

The challenge begins with uncovering the recurrence relation that governs the Fibonacho Sequence. A recurrence relation is a formula that expresses each term of a sequence as a function of its preceding terms. However, unlike the Fibonacci sequence’s simple \(F_n = F_{n-1} + F_{n-2}\), the Fibonacho Sequence defies such simplicity. Your task is to deduce the recurrence relation by analyzing the given terms.

Which general recurrence relation describes the sequence above?

Note again: It is NOT the recurrence relation for the Fibonacci numbers, since, for example, \(F_{17} \ne F_{15} + F_{16}\).

Part 2: Predicting Digits at Larger Indices

Now that you’ve explored the recurrence relation, it’s time to tackle larger terms in the sequence. You are given that:

• The first 10 digits of \(F_{1000}\) are \(1201386106\)
• The last 10 digits of \(F_{1000}\) are \(1044856625\)

What are the first and last \(10\) digits of \(F_{10000}\)?

Part 3: Scaling Up!

In this part, the challenge becomes even more daunting. You are now tasked with examining the first and last \(\mathbf{100}\) digits of massive terms like \(F_{7^7} = F_{823543}\).

For reference, you are given the first and last digits of \(F_{7^{7}} = F_{823543}\):

\(F_{7^{7}}\)	digits
first 100	2513371832737186384322330481943752132726740483311444508185490845781280728438771549838156508593799526
last 100	739646476432651186655886864569054345315965466581269946302070897583058681065487248400966951495110916

What are the first and last \(100\) digits of \(F_{4^{4^4}}\), \(F_{5^{5^5}}\), and \(F_{6^{6^6}}\) ?

---

Stay tuned, as I will reveal the solution and dive deeper into a few properties of the Fibonacho Sequence in a future blog post!