2
$\begingroup$

The sequence $(x_i)_{\displaystyle i \geq 0}$ has the preperiod $2,3,5,7,11,13,17,19,23,29$ and the periodic part $31,37,41,43$. Find the smallest index $l \in \mathbb{N}$ with $x_l = x_{2l}$.

In other words, the sequence is

$$2,3,5,7,11,13,17,19,23,29,31,37,41,43,31,37,41,43,...$$

By inspection I found out that the answer is $l=12$. But I am not so much interested in the answer but rather if there more general way of finding the answer which does not involve writing out the sequence and comparing individual elements.

$\endgroup$
2
$\begingroup$

The sequence verifies $a_{10+k} = a_{10 + (k \; {\rm mod}\; 4)}$ for $k\geq 0$ (and there are no other relations). So look for $\ell=10+k$, $k\geq 0$ so that $a_{10+k}=a_{20+2k}=a_{10+(10+2k)}$. And this is equivalent to $k\geq 0$ and $$ k \equiv 10+2 k \ {\rm mod} \ 4 $$ or $k \equiv 2 \ {\rm mod} \ 4$.

$\endgroup$
1
$\begingroup$

A bit of modular arithmetic reveals a simple way to compute the answer, at least for the following special case:

Assume that the non-periodic string has no elements in common with the periodic part, and also that the repeated string has no duplicates e.g. your periodic part can be {4,7,0} but not {4,7,4,0}.

If the period is $n$ then you can just replace the periodic part with increasing integers mod $n$, the block $\{1,2,...,n\}$, so that $a_{k+1} = a_k + 1 \bmod 4$ in your case. Since your period starts with the 11th term, you want $a_{11} \equiv 1 \bmod 4$. Writing $a_k = k+2 \bmod 4$ works to achieve this.

(we could have just written $a_k = k$, so that starting at $k=11$ gives the block $\{3,4,1,2\}$ rather than $\{1,2,3,4\}$ as I made it. It doesn't really matter.)

Now we want to equate elements in the periodic part. Since the non period part is of length $10$, we want the smallest $l > 10$ so that $a_k \equiv a_{2k} \bmod 4$.

Comes out to be $k+2 \equiv 2k + 2 \bmod 4 \Rightarrow k \equiv 2k \bmod 4 \Rightarrow 0 \equiv k \bmod 4$. Then the answer is $k = 12$; the smallest integer, greater than 10, which is divisible by 4, the period of your sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.