An exotic operation on repeating sequences of natural numbers such as $\overline{6,9} = 6,9,6,9,6,9, \dots$ Having to do with common subsums.

Question

Definitions. This is about repeating sequences of natural numbers such as $\overline{6} = 6,6,6, \dots$ or $\overline{2,1,2} = 2,1,2,2,1,2, \dots$. I am aware that these can be faithfully represented as the sequence of coefficients of a power series $f(x)(1 + x^k + x^{2k} + \dots)$ where $k = \deg f + 1$. And conversely, so there is a bijection. However, I have (consider this my attempt) verified that neither power series $+$ nor $\cdot$ represent the below described $\star$ operation.

Given $a = \overline{a_0, a_1, \dots, a_n}$ and $b = \overline{b_0, b_1, \dots, b_m}$ define $a \star b$ by the following algorithm.

We must start at $c_0 = (a\star b)_0$ the first entry of the result $c$.

The Algorithm. $a \star b$:

Input: $a, b$ (finite sequences such that if you index them the index you pass in gets modulo'd by their length).

Output: $c$ another repeating sequence in smallest length finite form.

0. Let $i = 0, j=0, k=0, c = []; s = 0, t = 0$
1. If $\sum c = \text{LCM}(\sum a, \sum b)$ reduce $c$ if possible and return.
2. Let $s = a_i, t=b_j$.
3. If $s=t$ let that be the result $c_k = t = s, k = k + 1; i = i +1; j = j + 1; s = 0, t = 0$, loop to step 1.
4. else if $s \lt t$ let $s = s + a_{i+1}; i = i + 1$ and test again (loop to step 3),
5. else if $s \gt t$ let $t = t + b_{j+1}; j = j + 1$ and test again (loop to step 3).

This can be proven to result in a repeating sequence. And thus we have an operation $\star$ closing such sequences.

Questions.

My question is given $a_1, \dots a_h$ or a total of $h$ repeating sequences, what is a non-trivial upper bound on $(a_1 \star \cdots \star a_h)_0$ that is better than $\text{LCM}(\sum_{i=0}^{n} a_i, \sum_{i=0}^{m} b_i) =$ a trivially known period of the resulting sequence?

Corollary question: what is a terminating condition better than the LCM of the sums of each?

Sometimes LCM of sums will be reached, but I'm wanting to terminate earlier for inputs / outputs where that is possible. Please a solution that doesn't use memoization as that would hide the mathematics of the situation.

Alternative question: Is $\star$ associative?

Worked Example (By inspection).

Notice that the sum of the elements in the result $c$ in the image is $35$. The sum of the elements in $a$ is $5$ and that of $b$ is $7$. So I guess my termination condition is about right, but what about the bound on $(a\star b)_{0}$? Here it is merely $2$.

Answer 1

I looked today again on the question, have also considered from the beginning the same (periodic) series approach, which is just an other way to write the operation $\star$, and saw no constructive progress. However, it may be of interest to have also this way to look at the problems, so here is an attempt of an answer.

Let $F=\Bbb F_2$ be the field with two elements. Consider the power series ring $R$ with powers in possible degrees $1,2,3,\dots$ over $F$ with the usual operations plus/minus $\pm$, and with two multiplications $\cdot$, the usual one, and $\odot$ which is acting only degree-wise (as the addition)! $$ P=\Big\{\ f=\sum_{n>0}f_nx^n\ \Big|\ a_1,a_2,a_3,\dots\in F\text{ periodic }\Big\}\ . $$ We identify for instance $a=[2,1,2]:=\overline {2,1,2}$ with the series $f=f(a)$ which satisfies: $$ f=f(a)=x^2(1+x^1(1+(x^2(1+f)))=x^2+x^3+x^5+x^5f=\frac{x^2+x^3+x^5}{1+x^5}\ . $$ Then $f$ moves the structure $\star$ from the set of periodic sequences to the set $P$ with the monoid operation $\odot$, $$ f(a\star b)=f(a)\odot f(b)\ , $$ so the operation $\star$ has all properties of the multiplication $\odot$.

The unit in $P$ is $x+x^2+x^3+\dots = x/(1+x)$, and it corresponds to $[1]=\bar 1$ in the world of periodic sequences. I need one more notation, the "sum" $s$ of a periodic sequence, it is the sum of the components in a minimal period. So for instance for $a=[2,1,2]$ we have $s(a)=2+1+2=5$. Then we transport $s$ also to $P$.

Let us try to say something about the properties of the operation $\star$, equivalently $\odot$.

Start with periodic sequences $a,b$. What can be said about the first entry in $a\star b$? It is also the first non-zero coefficient in $f(a)\odot f(b)$. If we start with $a,b$ the things are slightly unpredictable, but if we start equivalently with $f(a)$ with sum $s(f(a))=s(a)$, $f(b)$ with sum $s(f(b))=s(b)$ things feel better. (Are but the same.) I will consider the case when $s(a)$ and $s(b)$ are relatively prime. Now if $a$ is exactly $[s(a)]=\overline{s(b)}$ and $b$ is also $[s(b)]=\overline{s(b)}$ then we cannot do better. But else, if there are at least two entries in $a$, the first one on position $k$, then we are able to solve the diophantine problem $k +xs(a) =ys(b)$ first in integers, then reduce to the entries $1,2,\dots,s(a)s(b)$. So the question about what can be done better is a question about the control of this Chinese Remainder Theorem. With more terms and possibly non relatively prime periods sums the problem has the same complexity. (We cannot say "how early" the first match comes, but rather how many matches are there in total.)

Note: I could not exploit somehow usefully the usual ring structure from $\Bbb F_2[[x]]$ for understanding $\odot$, nor the distributivity of $\odot$ w.r.t. the addition...

Answer 2

Let $s_a =$ the sequence of partial sums of $a$, or $s_b = a_0,\ \ a_0 + a_1,\ \ a_0 + a_1 + a_2, \dots$. Similarly for $s_b$.

Then $c_0$ is defined to be the first sum in both sequences that is the same, the first from left to right as you list the sequence elements. $c_1$ is defined to be the second sum that is common to both $s_a, s_b$ minus $c_0$, and $c_2$ is defined to be the third sum that is common to both minus $c_0 + c_1$ and so on...

Clearly this is an operation of "least-common-subsum" or $\star$ is associative as the entries common to both $s_a, s_b$ are intersected with entries of a third $s_d$ to get the entries common to all three and it doesn't matter if you associate take those common to both $s_b, s_d$ first and then intersect with entries of $s_a$. And clearly the order doesn't matter.

Since $\overline{1}$ is identity for $\star$, we have proved it to be the law of a commutative monoid on repeating sequences.