Reverse Engineering Part 3

In my previous post, Reverse Engineering Part 2, I ended up being quite satisfied with the reverse engineering that created as output an homogenous linear recurrence relation of order 3 after input of any positive integer greater than 9. I used 28206 and 28207 as examples to illustrate the process.

This got me thinking about creating as output an homogenous linear recurrence relation of order 2 after input of any positive integer greater than 9. I explained in my post Reverse Engineering Part 1 that Gemini's algorithm had failed when attempting this. I was trying to get Gemini to create the following:$$ \begin{align} &\text{a}(n)=p \times \text{a}(n-1)+q \times \text{a}(n-2) \\ &\text{where} -9 \leq p,q \leq 9 \text{ with } p \neq 0 \text{ and } q \neq 0 \\ &\text{ and } 0 \leq \text{a}(n-1), \text{a}(n-2) \leq 9 \end{align}$$So I asked Gemini to relax the conditions by specifying that \( |p + q|\) should be as small as possible. When applied to 28207 this produced values \(p=39\) and \(q=-38\). Not quite what I wanted. So in the end I specified that \(|p^2+q^2+a(0)^2+a(1)^2|\) should be as small as possible. Applied to 28206, this was the result (permalink):

Target Number: 28206

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

Constants found: p = 13, q = 1

Constraint check: Minimum p^2 + q^2 + a(0)^2 + a(1)^2 = 395

Seed numbers:    a(0) = 9, a(1) = 12

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

Sequence progression:

  a(0) = 9

  a(1) = 12

  a(2) = 165

  a(3) = 2157

  a(4) = 28206

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

Comma-separated sequence:

9, 12, 165, 2157, 28206

Applied to 28207, this was the result (permalink):

 Target Number: 28207

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

Constants found: p = 6, q = 5

Constraint check: Minimum p^2 + q^2 + a(0)^2 + a(1)^2 = 231

Seed numbers:    a(0) = 11, a(1) = 7

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

Sequence progression:

  a(0) = 11

  a(1) = 7

  a(2) = 97

  a(3) = 617

  a(4) = 4187

  a(5) = 28207

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

Comma-separated sequence:

11, 7, 97, 617, 4187, 28207

Overall I'm quite happy with these sequences. All terms are positive, the coefficients and seed values are not large and the terms increase steadily toward their targets, avoiding any wild gyrations. I have incorporated this program into my daily number analysis. 

Reverse Engineering Part 2

In my previous post Reverse Engineering Part 1, I had specified to Gemini that I wanted \(p + q + r \) to be the minimum possible within the specifications that each of these coefficients were to be between -9 and -9 inclusive. I was thinking in terms of the sum getting as close to zero as possible forgetting that the minimum possible sum would be -27. That's why I was getting coefficients in the output that were all negative. The algorithm was doing what I'd asked of it! What I should have instructed Gemini to do was to take the absolute value of \(p+q+r\). So to summarise, our starting point is:$$ \begin{align} &\text{a}(n)=p \times \text{a}(n-1)+q \times \text{a}(n-2) + r \times \text{a}(n-2)\\ &\text{with } -9 \leq p,q,r \leq 9, 0 \leq \text{a}(2), \text{a}(1),\text{a}(0) \leq 9 \\ &\text{and } |p+q+r| \text{ as close to zero as possible} \end{align}$$Having gotten Gemini to modify the algorithm, the result for 28206 becomes :$$ \begin{align} &\text{a}(n)=5 \times \text{a}(n-1)-7 \times \text{a}(n-2) + 2 \times \text{a}(n-2)\\ &a(0) = 2, a(1) = 2, a(2) = 6\end{align}$$The full details are (permalink):

Target Number: 28206

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

Constants found: p = 5, q = -7, r = 2

Constraint check: Minimum |p + q + r| = 0 (Actual Sum = 0)

Seed numbers:    a(0) = 2, a(1) = 2, a(2) = 6

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

Sequence progression:

  a(0) = 2

  a(1) = 2

  a(2) = 6

  a(3) = 20

  a(4) = 62

  a(5) = 182

  a(6) = 516

  a(7) = 1430

  a(8) = 3902

  a(9) = 10532

  a(10) = 28206

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

Comma-separated sequence:

2, 2, 6, 20, 62, 182, 516, 1430, 3902, 10532, 28206

This is a longer sequence than previously (2, 4, 2, -48, 408, -3390, 28206) but it has no negative members and is free of the wild gyrations that characterise the former. Similarly for 28207, we have (permalink):$$ \begin{align} &\text{a}(n)=5 \times \text{a}(n-1)+4 \times \text{a}(n-2) -8 \times \text{a}(n-2)\\ &a(0) = 1, a(1) = 1, a(2) = 7\end{align}$$The full results are (permalink):

Target Number: 28207

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

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

Constraint check: Minimum |p + q + r| = 1 (Actual Sum = 1)

Seed numbers:    a(0) = 1, a(1) = 1, a(2) = 7

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

Sequence progression:

  a(0) = 1

  a(1) = 1

  a(2) = 7

  a(3) = 31

  a(4) = 175

  a(5) = 943

  a(6) = 5167

  a(7) = 28207

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

Comma-separated sequence:

1, 1, 7, 31, 175, 943, 5167, 28207

This is shorter than the previously calculated sequence (3, 5, 1, -73, 243, -323, -311, 2207, -3445, -3595, 27729, -51001, -16797, 304365, -658279, 28207) and again it has no negative members and is free of the wild gyrations that characterise the former. So, a lesson learned. I've modified my daily number analysis algorithm accordingly. 

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.

Fibonacci Generating Functions

The Fibonacci Sequence can be generated from the following recurrence relation:$$a(n)=a(n-1)+a(n-2) \text{ with } a(0)=1 \text{ and } a(1)=1$$The generating function for this series is given by:$$ \frac{x^2}{1-x-x^2} $$How is generating function affected if we have a recurrence relation as follows:$$a(n)=a(n-1)+a(n-8)$$I created a post about this titled Fibonacci-like Sequences quite recently on May 13th 2024. The new generating function is now:$$ \frac{x^2}{1-x-x^8} $$What if there are coefficients (let's say \( \alpha \) and \( \beta \) in front of the two terms on the LHS:$$a(n) = \alpha . a(n-1) + \beta . a(n-2)$$In this case, the generating function becomes: $$ \frac{x^2}{1-\alpha . x - \beta . x^2}$$Let's take the following example:$$a(n)=4. \, a(n-1)+10. \, a(n-2)$$The generating function becomes$$ \frac{x^2}{1-4x - 10 x^2}$$The sequence of terms becomes (permalink):

0, 1, 4, 26, 144, 836, 4784, 27496, 157824, 906256, 5203264, 29875616, 171535104, 984896576, 5654937344, 32468715136, 186424233984, 1070384087296, 6145778689024, 35286955629056

This numbers form the initial terms of OEIS A180226:

A180226

a(n) = 4*a(n-1) + 10*a(n-2), with a(1)=0 and a(2)=1.

To check what happens to the generating function when the tribonacci sequence is considered, see my post titled Beyond Fibonacci (March 10th 2019).