Making regular sequences from a not necessarily regular sequence, but how many unique reqular sequences can we actually make?

Question

Making regular sequences from a not necessarily regular sequence, but how many unique reqular sequences can we actually make?

TL;DR:
I thought of a way to make up to $2^{N-1}$ regular$^1$ sequences from a not necessarily regular sequence $S$ of length $N$, but this procedure might produce regular sequences which are not necessarily unique from each other.

---

Recently, I thought of a way to make regular$^1$ sequences from a not necessarily regular sequence.

Given a sequence $S = [a, b, c, ..., w]$, we can generate a regular sequence as follows:

1. Square each element. $S$ becomes $R = S^2 = [a^2, b^2, c^2, ..., w^2]$

Now, pairs of consecutive elements sum to a sum of two squares (e.g. $a^2 + b^2, b^2 + c^2, ...)$. We want to complete the square. For each pair of consecutive elements $x^2, y^2 \in R$, we can complete the square by either adding or subtracting $2xy$ because $x^2 + y^2 \pm 2xy = (x \pm y)^2$.

So we add $2ab$ to the $b^2$ element to complete the square for the first pair:

$$R = [a^2, b^2 + 2ab, c^2, ..., w^2]$$

Then we add $2bc$ to the $c^2$ element to complete the square for the second pair... but wait, because we added $2ab$ to the $b^2$ element to complete the square for the first pair, now our second pair sums to $b^2 + 2ab + c^2 +2bc$, so in fact we want to add $-2ab + 2bc$ to the $b^2$ element:

$$R = [a^2, b^2 + 2ab, c^2 - 2ab + 2bc, ..., w^2]$$

Now the first two pairs are complete.

In general, suppose we are somewhere along the sequence:

$$R = [...\ r_{i-2},\ r_{i-1},\ r_i,\ ...]$$

and that we have managed complete the square for all pairs up to the pair $(r_{i-2}, r_{i-1})$ and are now looking to complete the square for the next pair, pair $(r_{i-1}, r_i)$. Zooming in at $R$ we have the following situation:

$$R = [...\ (a_{i-2}^2\ + s_{i-2}),\ (a_{i-1}^2 + s_{i-1}),\ (a_i^2),\ ...]$$

and we want to add an adjustment, $s_i$, to $r_i$ such that

$$ \begin{align} r_{i-1} + r_i + s_i &= a_{i-1}^2 + s_{i-1} + a_i^2 + s_i\\ &= a_{i-1}^2 + a_i^2 \pm 2a_{i-1}a_i\\ &= (a_{i-1} \pm a_i)^2 \end{align} $$

Solving for $s_i$, we find:

$$s_i = \pm 2a_{i-1}a_i - s_{i-1}$$

and thus by adding this $s_i$ to $r_i$, we complete the square for the $(r_{i-1}, r_i)$ pair and can continue in this manner with the next pair and the next until we reach the end of the sequence at which point every pair will sum to a perfect square and the resulting sequence will be a regular sequence.

And not only that, but we can generate up to $2^{N-1}$ regular sequences from $S$ where $N$ is the length of $S$ since for each of the $N-1$ pairs we have a binary choice of whether to

1. add $+2a_{i-1}a_i - s_i$ to $a_i$ so that the pair sums to $(a_{i-1} + a_i)^2$ or
2. add $-2a_{i-1}a_i - s_i$ to $a_i$ so that the pair sums to $(a_{i-1} - a_i)^2$.

I also wrote some Python to implement the above procedure. You can find it below.

---

My question is that while I know this procedure produces $2^{N-1}$ regular sequences from $S$, I am not sure that they would all be unique. Abstractly, it could be possible that in certain cases, a local add/subtract $2xy$ choice is inconsequential in that either choice produces the same local result and we could end up with two generated sequences $R, R'$ being identical $R = R$. This happens for example when the input sequence $S$ has $0$s where a region of $S$ could look like $[... x^2, 0, y^2, ...]$. For the two pairs involving the $0$, the pairs being $(x, 0)$ and $(0, y)$, we have $\pm 2x(0) = 0 = \pm 2(0)y$, so it does not matter whether we choose to add or subtract as either choice produces the same local outcome. We have $s_0 = 0 - s_x = -s_x$ and $s_y = 0 - s_0 = -s_0 = s_x$:

$$R = [... (x^2 + s_x), (0 - s_x), (y^2 + s_x), ...]$$

From this, I can conclude that the procedure produces up to $2^{N-1-Z}$ where $Z$ is computed as show in footnote$^2$.

I have been trying to think if there are any other ways that an add/subtract choice can become inconsequential, but haven't been able to find any. The fact we accumulate adjustments could possibly make it so that despite making different choices, the accumulated adjustments of two sequences we're generating converge. Something like, say we have generated $R$ with a set of choices $C$ so far up to the $i$th index and likewise we have generated $R'$ with a set of different choices $C'$ also up the $ith$ index. $R$ and $R'$ look like:

$$ R = [...\ (a_{i-1}^2 + s_{i-1}),\ (a_i^2),\ ...] \\ R' = [...\ (a_{i-1}^2 + s'_{i-1}),\ (a_i^2),\ ...] $$

In both cases, we are looking to complete the square for the $(i-1, i)$ pair. $s_{i-1}$ and $s'_{i-1}$ are determined by the binary choices we have made so far $C[:i]$ and $C'[:i]$, respectively. Suppose that $C[:i] \neq C'[:i]$, but that somehow $s_{i-1}$ and $s'_{i-1}$ have converged to the same value $s_{i-1} = s'_{i-1}$. Even though each is a an accumulated sum of $\pm 2xy$ terms, where sometimes their choices line up and they both choose $+$ or both choose $-$ for the same term (e.g. both chose to add $2ab$), but other times they don't and one chooses $+$ while the other choose $-$ (e.g. one chose $+2de$, while the other chose $-2de$), it could still happen that in some cases, for some $S$ and some $C$ and $C'$, $s_{i-1}$ and $s'_{i-1}$ converge to the same value.

---

import math

def genRegularSeqs(S):
    ''' Generates pow(2, N-1) regular sequences based on the sequence S. '''
    N = len(S)
    Squares = list(map(lambda x: x**2, S))
    for bits in range(2**(N-1)):
        yield genRegularSeq(S, Squares, bits)


def genRegularSeq(S, Squares, bits):
    N = len(Squares)
    R = Squares.copy()
    cumAdjustments = 0
    for i in range(1, N):
        x, y = S[i-1], S[i]
        a, b = Squares[i-1], Squares[i]
        # a == x**2
        # b == y**2
        # Complete the square
        # a + b + 2xy == (x + y)**2
        # a + b - 2xy == (x - y)**2
        # Booleanness of (og_input_val(bits) & (1 << (i-1))
        # selects whether we add (truthy) or subtract (falsy) 2xy to complete the square
        sel = bits & 0b1
        
        adjustment = +2*x*y if sel else -2*x*y
        cumAdjustments = adjustment - cumAdjustments
        R[i] += cumAdjustments
        
        bits >>= 1
    return R

And here's a test:

# /** Test **/
def test():
    S = [1,2,3,4,5]
    for R in genRegularSeqs(S):
        assert isRegular(R)
        print(R)

def isRegular(R):
    return all(isSquare(a + b) for a, b in zip(R, R[1:]))
    
    # # Equivalently
    # N = len(R)
    # for i in range(1, N):
    #     a, b = R[i-1], R[i]
    #     if not isSquare(a + b):
    #         return False
    # return True

def isSquare(sq):
    return int(math.sqrt(sq)) ** 2 == sq

test()

---

$^1$: A regular sequence is a sequence whose consecutive elements sum to a perfect square. E.g. $[1, 3, 6, 10]$ is a regular sequence because $1+3, 3+6, 6+10$ are each a perfect square.

More about regular sequences can be found in this HexagonVideos video about regular sequences.

$^2$:

def getZeroClusterLens(nums):
  N = len(S) # assume N >= 2
  zero_cluster_lens = []
  i = 0
  while i < N:
    if nums[i] == 0:
      l = i
      while i < N and nums[i] == 0:
        i += 1
      # nums[l:i] == 0
      # i == N or nums[i] != 0
      zero_cluster_lens.append(i - l)
    # i == N or nums[i] != 0
    i += 1
  return zero_cluster_lens

if not any(S):
  # S is a list of 0's
  Z = N-1
else:
  zero_cluster_lens = getZeroClusterLens(S)
  # each zero cluster that touches an end of S contribute that cluster's length of inconsequential add/subtract choices since it is involved that many pairs
  # each zero cluster that does not touch an end of S contributes that cluster's length + 1 of inconsequential add/subtract choices since it is involved in that many pairs
  # e.g. if S = [0, 0, 0, 1, 2, 3, 0, 0, 0, 0, 4, 5, 6, 7, 8, 0, 0, 9, 10]
  # then zero_cluster_lens = [3, 4, 2]
  # Since the cluster of length 3 touches an end of S, it is involved 3 pairs
  # Since the clusters of length 4 and 2 do not touch an end of S, they are involved in 4+1=5 and 2+1=3 pairs, respectively.
  Z = sum(zero_cluster_lens) + len(zero_cluster_lens) - (S[0] == 0) - (S[-1] == 0)
```

Answer 1

Let $N = \operatorname{len}(S)$ and $g_i = 2a_{i-1}a_i$ for $i \in [1, N]$.

We have $r_i = a^2_i + s_i$ and $s_0 = 0$ and $s_i = c_ig_i - s_{i-1}$ for $i \in [1, N]$.

where $c_i$ is the choice we made for $i \in [1, N]$

$$ c_i = \begin{cases} -1\ \text{if we choose to subtract}\ g_i\\ +1\ \text{if we choose to add}\ g_i \end{cases} $$

$R = R'$ iff $r_i = r'_i$ for all $i$.

$r_0 = a^2_i = r'_0$

For $i \in [1, N]$, $r_i = r'_i$ iff $a^2_i - s_{i-1} = a^2_i - s'_{i-1}$ which happens iff $s_n = s'_n$ for $n >= 0$.

We know $s_0 = 0$ and

$$s_i = c_ig_i - s_{i-1}$$

Looking at the first few expressions for $s_i$, we get:

$$ \begin{align} s_0 &= 0\\ s_1 &= c_1g_1 - s_0 = c_1g_1\\ s_2 &= c_2g_2 - s_1 = c_2g_2 - c_1g_1\\ s_3 &= c_3g_3 - s_2 = c_3g_3 - c_2g_2 + c_1g_1\\ s_4 &= c_4g_4 - s_3 = c_4g_4 - c_3g_3 + c_2g_2 - c_1g_1 \end{align} $$

There is a pattern. In general, the closed form for $s_n$ for $n > 0$ is:

$$ s_n = \sum_{i=1}^n (-1)^{m_n + m_i} c_ig_i = (-1)^{m_n} \sum_{i=1}^n (-1)^{m_i} c_ig_i $$

where $m_n = \operatorname{mod}(n, 2)$ and $m_i = \operatorname{mod}(i, 2)$.

Let's define five sets taken from $I = [1, n]$. The first three are disjoint and their union is $I$. Likewise the last two are also disjoint and their union is also $I$.

1. $I_{n=} = \{i\ |\ c_i = c'_i\} \subset [1, n]$
2. $I_{n\pm} = \{i\ |\ +1 = c_i \neq = c'_i = -1\} \subset [1, n]$
3. $I_{n\mp} = \{i\ |\ -1 = c_i \neq = c'_i = +1\} \subset [1, n]$
4. $I_{n,even} = \{i\ |\ i\ \text{is even}\} \subset [1, n]$ and $(-1)^{m_i}$ is +1 for these $i$.
5. $I_{n,odd} = \{i\ |\ i\ \text{is odd}\} \subset [1, n]$ and $(-1)^{m_i}$ is -1 for these $i$.

In order for $R = R'$, we need $s_n = s'_n$ for all $n \in [1, N]$

$$ s_n = (-1)^{m_n} \sum_{i=1}^n (-1)^{m_i} c_ig_i = (-1)^{m_n} \sum_{i=1}^n (-1)^{m_i} c'_ig_i = s'_n $$

which happens iff

$$ \sum_{i=1}^n (-1)^{m_i} c_ig_i = \sum_{i=1}^n (-1)^{m_i} c'_ig_i $$

Terms corresponding to $i \in I_{=}$ appear identically on both sides so they can be cancelled out. Also, terms corresponding to

• $i \in A_n = I_{n\pm} \cap I_{n,even}$: LHS+, RHS-
• $i \in B_n = I_{n\mp} \cap I_{n,odd}$: LHS+, RHS-
• $i \in C_n = I_{n\pm} \cap I_{n,odd}$: LHS-, RHS+
• $i \in D_n = I_{n\mp} \cap I_{n,even}$: LHS-, RHS+

LHS+ means the terms are positive ($+g_i$) on the LHS. Corresponding definitions for LHS-, RHS+, and RHS- apply. For example, for $i \in A = I_{n\pm} \cap I_{n,even}$ from the definition of $I_{n,\pm}$, this means $+1 = c_i \neq c'_i = -1$ and $i \in I_{even}$ means $(-1)^{m_i}$ is $+1$, therefore on the LHS, $(-1)^{m_i} c_ig_i = (+1)(+1)g_i = +g_i$; whereas on the RHS we have $(-1)^{m_i} c'_ig_i = (+1)(-1)g_i = -g_i$

Writing this out we have that we must satisfy:

$$ +\sum_{i \in A_n} g_i +\sum_{i \in B_n} g_i -\sum_{i \in C_n} g_i -\sum_{i \in D_n} g_i = +\sum_{i \in D_n} g_i +\sum_{i \in C_n} g_i -\sum_{i \in B_n} g_i -\sum_{i \in A_n} g_i $$

which if we group like sums, we get:

$$ \begin{align} +2\sum_{i \in A_n} g_i +2\sum_{i \in B_n} g_i &= +2\sum_{i \in D_n} g_i +2\sum_{i \in C_n} g_i \\ +2\sum_{i \in A_n \cup B_n} g_i &= +2\sum_{i \in C_n \cup D_n} g_i \\ \sum_{i \in A_n \cup B_n} g_i &= \sum_{i \in C_n \cup D_n} g_i \end{align} $$

We wanted to know when $R = R'$ which requires $r_i = r'_i$ for all $i$ which requires $s_n = s'_n$ for all $n \in [1, N]$. After some "simplifying", we found that $s_n = s'_n$ iff

$$ \sum_{i \in A_n \cup B_n} g_i = \sum_{i \in C_n \cup D_n} g_i \qquad [1]:\ \text{equivalent to}\ s_n = s'_n $$

If we can choose $c_i$ and $c'_i$ that satisfy $[1]$ for all $n \in [1, N]$, then $R = R'$.