Question

Para cualquier entero $k \ge 1,$ sea $p(k)$ el menor primo que no divide a $k.$ Define la función entera $X(k)$ como el producto de todos los primos menores que $p(k)$ si $p(k) \gt 2,$ y $X(k) = 1$ si $p(k) = 2.$ Sea $\{x_n\}$ la sucesión definida por $x_0 = 1,$ y $x_{n+1} X(x_n) = x_n p(x_n)$ para $n \ge 0.$ Halla el menor entero positivo $t$ tal que $x_t = 2090.$

For any integer $k \ge 1,$ let $p(k)$ be the smallest prime which does not divide $k.$ Define the integer function $X(k)$ to be the product of all primes less than $p(k)$ if $p(k) \gt 2,$ and $X(k) = 1$ if $p(k) = 2.$ Let $\{x_n\}$ be the sequence defined by $x_0 = 1,$ and $x_{n+1} X(x_n) = x_n p(x_n)$ for $n \ge 0.$ Find the smallest positive integer $t$ such that $x_t = 2090.$

Respuesta

Solución:

Enumera los primos en orden como $\rho_0 = 2,$ $\rho_1 = 3,$ $\rho_2 = 5, \ldots.$ Cada $x_n$ es libre de cuadrados, así que queda descrito por el conjunto de primos que lo dividen, y afirmamos que este conjunto codifica $n$ en binario: si $n = \sum_i d_i 2^i$ con $d_i \in \{0, 1\},$ entonces $x_n = \prod_i \rho_i^{d_i}.$

En efecto, supón que $x_n = \prod_i \rho_i^{d_i}$ y sea $j$ el menor índice con $d_j = 0.$ Entonces $p(x_n) = \rho_j,$ y $X(x_n) = \rho_0 \rho_1 \cdots \rho_{j-1}$ es exactamente el producto de los primos de los bits $1$ finales (con $X(x_n) = 1$ cuando $j = 0$ ). Así $x_{n+1} = \frac{x_n \, \rho_j}{\rho_0 \rho_1 \cdots \rho_{j-1}}$ elimina los unos finales e inserta $\rho_j$ , que es precisamente sumar $1$ en binario. Como $x_0 = 1$ corresponde a $0,$ la inducción demuestra la afirmación.

Ahora $2090 = 2 \cdot 5 \cdot 11 \cdot 19 = \rho_0 \rho_2 \rho_4 \rho_7,$ que corresponde a dígitos binarios en las posiciones $0,$ $2,$ $4,$ $7.$ Por tanto $t = 2^0 + 2^2 + 2^4 + 2^7 = 149.$

List the primes in order as $\rho_0 = 2,$ $\rho_1 = 3,$ $\rho_2 = 5, \ldots.$ Every $x_n$ is squarefree, so it is described by the set of primes dividing it, and we claim this set encodes $n$ in binary: if $n = \sum_i d_i 2^i$ with $d_i \in \{0, 1\},$ then $x_n = \prod_i \rho_i^{d_i}.$

Indeed, suppose $x_n = \prod_i \rho_i^{d_i}$ and let $j$ be the smallest index with $d_j = 0.$ Then $p(x_n) = \rho_j,$ and $X(x_n) = \rho_0 \rho_1 \cdots \rho_{j-1}$ is exactly the product of the primes for the trailing $1$ -bits (with $X(x_n) = 1$ when $j = 0$ ). So $x_{n+1} = \frac{x_n \, \rho_j}{\rho_0 \rho_1 \cdots \rho_{j-1}}$ removes the trailing ones and inserts $\rho_j$ — precisely adding $1$ in binary. Since $x_0 = 1$ corresponds to $0,$ induction proves the claim.

Now $2090 = 2 \cdot 5 \cdot 11 \cdot 19 = \rho_0 \rho_2 \rho_4 \rho_7,$ which corresponds to binary digits at positions $0,$ $2,$ $4,$ $7.$ Hence $t = 2^0 + 2^2 + 2^4 + 2^7 = 149.$

2014 AIME II Problema 15

Solución:

El Problema 15 en otros años