Problem

Source: ITAMO 2021 Problem 6

Tags: number theory, prime numbers



A sequence $x_1, x_2, ..., x_n, ...$ consists of an initial block of $p$ positive distinct integers that then repeat periodically. This means that $\{x_1, x_2, \dots, x_p\}$ are $p$ distinct positive integers and $x_{n+p}=x_n$ for every positive integer $n$. The terms of the sequence are not known and the goal is to find the period $p$. To do this, at each move it possible to reveal the value of a term of the sequence at your choice. (a) Knowing that $1 \le p \le 10$, find the least $n$ such that there is a strategy which allows to find $p$ revealing at most $n$ terms of the sequence. (b) Knowing that $p$ is one of the first $k$ prime numbers, find for which values of $k$ there exist a strategy that allows to find $p$ revealing at most $5$ terms of the sequence.