0

Suppose there's a looped sequence $A=(a_0\ldots a_n)$ and, since it is a looped sequence, $a_0=a_n$.

Given $M$, is there a way to determine whether said sequence can be produced by a formula $$A_i=(p^ia+b\sum_{k=0}^{i-1}{p^k})\pmod M$$

In other words, given a looped sequence $A$, how can we determine if there exist a pair of $(p, b)$ such that the following sequence defines it beautifully? $$a_0\\(p a_0+b)\pmod M\\(p^2a_0+pb+b)\pmod M\\ \ldots $$

For example, given $M=16$, a looped sequence of $(1, 12,3,6,5,0,7,10,9,4,11,14,13,8,15,2,1)$ can be defined by choosing $p=5$, $b=7$: $$A_i=(5^ia+7\sum_{k=0}^{i-1}{5^k})\pmod {16}$$

How can we determine if an arbitrary looped sequence can be presented in such manner?

Thehx
  • 183

1 Answers1

0

Assume that a given looped sequence $\{A_n\}$ can be described by a pair of integers $(p,b)$ and the relation $$ A_n = A_0 p^n + n \sum_{k=0}^{n-1} p^k \mod M. $$ The first thing to note is that we have a recurrence relation: $$ A_{n+1} = p A_n + b \mod M $$ and it follows that the same $(p,b)$ combination would be found wherever we start in the loop. The first three elements of the loop are: $$A_0$$ $$A_1 = p A_0 + b$$ $$A_2 = p A_1 + b$$ and we can combine them to obtain $$A_2 - 2 A_1 + A_0 = (A_2-A_1) - (A_1-A_0) = (p-1) (A_1 - A_0) $$ $$A_1^2 - A_2 A_0 = A_1(p A_0 +b) - (p A_1 + b) A_0 = b (A_1-A_0)$$ This gives us the two congruence equations: $$A_2 - 2 A_1 + A_0 \equiv (p-1) (A_1 - A_0) \mod M$$ $$A_1^2 -A_1 A_0 \equiv b (A_1 - A_0) \mod M$$ to be solved for $p-1$ and $b$. These can be solved if and only if $$A_2 - 2 A_1 + A_0 \equiv A_1^2 - A_2 A_0 \equiv 0 \mod \gcd(M,A_1-A_0)$$ This double condition is easy to check and when satisfied, the values for $p$ and $b$ follow by solving the congruence equations with the standard algorithm, otherwise no such $(p,b)$ combinations exists that allows the loop to be described via the imposed formula.

Ronald Blaak
  • 3,277
  • That's a beautiful solution, definitely what I was looking for, thank you! Can you tell me how had you come up with a solution plan for this problem? Is the problem (or the approach you used) somewhat standard? – Thehx Aug 06 '17 at 21:35
  • I would not call this a standard problem. Solving such problems depends on intuition, a lot of practice/experience and a bit of luck in trying a successful approach. The ingredients are a sort of standard, but combining them in the proper way is never straightforward. – Ronald Blaak Aug 06 '17 at 22:15