Reverse Engineering Part 1

I have a sub-program in my daily number analysis program that will work backwards to find Fibonacci seed numbers that will generate a sequence of terms that leads to my daily number. For example, today I am 28206 days old, and my sub-program generates the following output:

Fibonacci Sequence: Smallest Starting Pair for Target 28206
Starting numbers: a = 126, b = 118
Sequence length to target: 13
Full sequence: [126, 118, 244, 362, 606, 968, 1574, 2542, 4116, 6658, 10774, 17432, 28206]

This can be expressed as:$$ \begin{align} \text{a}(n)=\text{a}(n-1) + \text{a}(n-2)  \\ \text{where } \text{a}(0)=126 \text{ and } \text{a}(1)=118 \end{align}$$These large initial values disturbed me and I wondered if the addition of coefficients \(p\) and \(q\) might reduce the size of the seed numbers required.

I asked Gemini the following:

I would like you to write a program in SageMath that will accept any positive integer \(n > 9\) as input and work backwards to find two seed numbers \( \text{a}(0) \text{ and } \text{a}(1)\) that, combined with constants \(p\) and \(q\), will lead to \(n\) via a Fibonacci-like sequence generated by \( \text{a}(n) = p \times \text{a}(n-1) + q \times \text{a}(n-2)\). The restrictions are that the seed numbers must be between 1 and 9 and the constants \(p\) and \(q\) must also be between -9 and 9.  In the case of more than one combination of constants and seed numbers being found, the criterion is that \(p + q\) should be the minimum possible. The default value for n can be taken as 28206. The program should run in SageMathCell and a Jupyter notebook. The output should show the sequence as it progresses from its starting seed numbers to the final number n. The members of the sequence should also be displayed as comma-separated values.

Unfortunately these restraints proved too restrictive and so I turned to Tribonacci numbers looking for three seed numbers, each between 0 and 9, and three constants \(p, q, r\), each lying between -9 and 9 so that:$$\text{a}(n) = p \times \text{a}(n-1) + q \times \text{a}(n-2) + r \times \text{a}(n-3) $$This proved more productive with Gemini creating the program and producing the following output (permalink):

Target Number: 28206
------------------------------
Constants found: p = -9, q = -6, r = -3
Constraint check: Minimum p + q + r = -18
Seed numbers:    a(0) = 2, a(1) = 4, a(2) = 2
------------------------------
Sequence progression:
  a(0) = 2
  a(1) = 4
  a(2) = 2
  a(3) = -48
  a(4) = 408
  a(5) = -3390
  a(6) = 28206
------------------------------
Comma-separated sequence:
2, 4, 2, -48, 408, -3390, 28206

For me, this is a more satisfactory output with the recursion looking like this: $$ \begin{align} &\text{a}(n) = -9 \times \text{a}(n-1) -6 \times \text{a}(n-2) -3 \times \text{a}(n-3) \\ &\text{with } \text{a}(0)=2, \text{a}(1)=4, \text{a}(2)=2 \end{align}$$What we have here is an homogenous linear recurrence relation of order 3 with coefficients and boundary conditions (seed values) as shown. The sequence is defined by two tuples: the coefficient tuple C and initial value tuple I and written as (C, I). In the example just shown, the representation would be:$$((-9, -6, -3), (2,4,2))$$Let's look at the next number 28207 characterised by ((-4, -9, -8), (3, 5, 1)):

Target Number for Reverse Tribonacci: 28207

------------------------------

Constants found: p = -4, q = -9, r = -8

Constraint check: Minimum p + q + r = -21

Seed numbers:    a(0) = 3, a(1) = 5, a(2) = 1

------------------------------

Sequence progression:

  a(0) = 3

  a(1) = 5

  a(2) = 1

  a(3) = -73

  a(4) = 243

  a(5) = -323

  a(6) = -311

  a(7) = 2207

  a(8) = -3445

  a(9) = -3595

  a(10) = 27729

  a(11) = -51001

  a(12) = -16797

  a(13) = 304365

  a(14) = -658279

  a(15) = 28207

------------------------------

Comma-separated sequence:

3, 5, 1, -73, 243, -323, -311, 2207, -3445, -3595, 27729, -51001, -16797, 304365, -658279, 28207

Figure 1 shows the trajectory of the sequence which begins to fluctuate wildly but the negative by negative multiplication quickly homes in on the target number (28207).

Figure 1

I've now incorporated this information into my daily number analysis.