Introduction

The Fibonacci sequence, with its simple yet profound pattern, has captivated mathematicians for centuries. But when we venture beyond and explore its extension, the Tribonacci sequence, we stumble upon even more intriguing puzzles. In this post, we dive into a challenging riddle: finding the smallest sum of starting whole numbers a, b, and c in a Tribonacci sequence that includes the year 2024. Our approach is a straightforward, yet effective, brute-force method.

Understanding the Tribonacci Sequence

Similar to the Fibonacci sequence, the Tribonacci sequence starts with a set of numbers and each subsequent number is the sum of the three preceding ones. The complexity and possibilities increase as we consider three starting numbers instead of two.

Given \(a,b,c \in N\) the mathematical formulation it the following:

\[ \begin{equation*} Trib_n = \begin{cases} a \;\;\; if \;\; n = 1 \\ b \;\;\; if \;\; n = 2 \\ c \;\;\; if \;\; n = 3 \\ Trib_{n-1} + Trib_{n-2} + Trib_{n-3} \;\;\; if \;\; n > 3 \end{cases} \end{equation*} \]

The Riddle:

The Fibonacci sequence begins with the numbers 1 and 1, 2 with each new term in the sequence equal to the sum of the preceding two. The first few numbers of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on.

One can also make variations of the Fibonacci sequence by starting with a different pair of numbers. For example, the sequence that starts with 1 and 3 is 1, 3, 4, 7, 11, 18, 29, 47, 76 and so on. Generalizing further, a “tribonacci” sequence starts with three whole numbers, with each new term equal to the sum of the preceding three.

Many tribonacci sequences include the number 2023. For example, if you start with 23, 1000 and 1000, then the very next term will be 2023. Your challenge is to find starting whole numbers a, b and c so that 2023 is somewhere in their tribonacci sequence, a ≤ b ≤ c, and the sum a + b + c is as small as possible.

Our quest is to discover three starting numbers, a ≤ b ≤ c, that not only generate a sequence containing the number 2024 but also have the smallest possible sum.

Our Brute Force Approach

We chose a brute-force approach for its simplicity and directness. Here’s how we tackled the problem:

Defining the Tribonacci Function: We crafted a function tribonacci() to generate the sequence from any three starting numbers.
Creating a Comprehensive Search Algorithm: Using minimum_tribonacci(), we systematically searched through a predefined range of starting numbers.
Comprehensive Iteration: Leveraging itertools.product(), we exhaustively examined combinations for a, b, and c, adhering to the condition a ≤ b ≤ c.
Sorting for Efficiency: We sorted the combinations by the sum of a, b, and c to prioritize finding the smallest sum that fits the riddle’s requirements.

While this brute-force method guarantees a thorough search, it is computationally intensive and may not be the most efficient for larger sequences or ranges.

import pandas as pd
from itertools import product
from typing import Union, List

def tribonacci(a: int, b: int, c: int, year: int) -> Union[List[int], int]:
    """
    Generates a Tribonacci sequence starting with three specified initial terms.

    The Tribonacci sequence is similar to the Fibonacci sequence, but it starts 
    with three initial terms and each subsequent term is the sum of the preceding 
    three terms. This function continues to generate the sequence until a specified 
    limit (the 'year' parameter) is reached or exceeded.

    Parameters:
    a (int): The first term of the Tribonacci sequence.
    b (int): The second term of the Tribonacci sequence.
    c (int): The third term of the Tribonacci sequence.
    year (int): A numeric threshold that limits the length of the sequence. 
                The function generates Tribonacci numbers until the sum of 
                the last three numbers is less than or equal to this threshold.

    Returns:
    list[int] | int: Returns a list containing the Tribonacci sequence if the 
                     initial terms are in non-decreasing order (a <= b <= c). 
                     If the initial terms do not meet this condition, it returns 0.

    Example:
    tribonacci(1, 1, 2, 10)
    [1, 1, 2, 4, 7]

    tribonacci(3, 2, 1, 10)
    0
    
    Raises:
    TypeError: If any of the inputs (a, b, c, year) are not integers.
    """
    try:
        if  a <= b <= c and (a + b + c != 0):
            tribonacci_n = 0
            tribonacci_sequence=[a,b,c] 
            while tribonacci_n < year:
                tribonacci_n = sum(tribonacci_sequence[-3:])
                tribonacci_sequence.append(tribonacci_n)
            return tribonacci_sequence
        else:
            return 0
    except TypeError:
        print('Error: a, b, and c must be integers.')


def minimum_tribonacci(dataframe: pd.DataFrame, year: int) -> list:
    """
    Searches through a DataFrame for the first row where the Tribonacci sequence 
    (generated from the first three values of the row) contains a specified value ('year').

    This function iterates through each row of the provided DataFrame, using the first three 
    values of each row as the initial terms for a Tribonacci sequence. It then generates 
    the sequence up to the specified 'year'. If 'year' is found within the generated 
    Tribonacci sequence, the function returns the initial three values (a, b, c) from 
    that row as a list.

    Parameters:
    dataframe (pd.DataFrame): A DataFrame with at least three columns. The first three 
                              columns should contain numeric values to generate the 
                              Tribonacci sequence.
    year (int): The target value to search for within the Tribonacci sequences.

    Returns:
    list: A list containing the first three values (a, b, c) of the row from the DataFrame 
          where the 'year' is found in the generated Tribonacci sequence. If no sequence 
          contains the 'year', the function returns None.

    Example:
    df = pd.DataFrame([[3, 4, 20], [3, 4, 41], [1, 16, 32]])
    minimum_tribonacci(df, 2024)
    [3, 4, 20]
    """

    for index in dataframe.index:
        a = dataframe.iloc[index, 0]
        b = dataframe.iloc[index, 1]
        c = dataframe.iloc[index, 2]
        trib = tribonacci(a, b, c, year)
        if year in trib:
            return [a, b, c]

a = [x for x in range(1, 50)] 
b = [x for x in range(1, 50)] 
c = [x for x in range(1, 50)] 
df_tribo = pd.DataFrame(list(product(a,b,c)), columns=['a', 'b','c'])

df_tribo = df_tribo.query('a <= b <= c')
df_tribo['sum'] = df_tribo['a'] + df_tribo['b'] + df_tribo['c']
df_tribo = df_tribo.sort_values('sum').reset_index(drop=True)
df_tribo.head(5)

##    a  b  c  sum
## 0  1  1  1    3
## 1  1  1  2    4
## 2  1  1  3    5
## 3  1  2  2    5
## 4  1  2  3    6

Results and Reflections

minimum = minimum_tribonacci(df_tribo, 2024)
minimum

## [3, 4, 20]

Our brute-force method successfully identified [3, 4, 20] as the number with the minimum sum that contain 2024 in their tribonacci sequence, proving its effectiveness. However, it’s important to note that this approach, while straightforward, may not always be the most efficient, especially for problems with larger scopes. It highlights the trade-off between the simplicity of implementation and computational efficiency.

Conclusion

Exploring the Tribonacci sequence through a brute-force lens offers valuable lessons in both mathematics and computational strategies. While brute-force methods provide clear-cut solutions, they also open discussions about efficiency and optimization in problem-solving. As we continue to delve into the world of numbers, these insights become stepping stones for more sophisticated and nuanced approaches to mathematical puzzles.