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

Respuesta: 149

Conceptos:primo base numérica recursión reconocimiento de patrones

Nivel de dificultad: 3270

Pista pequeña:

Calcula

x_1

hasta

x_8

y factoriza cada uno; compara el conjunto de primos que aparecen en

x_n

con los dígitos binarios de

n

Compute

x_1

through

x_8

and factor each; compare the set of primes appearing in

x_n

with the binary digits of

n

Pista grande:

La recursión es un conteo binario: dividir entre

X(x_n)

elimina los bits finales iguales a uno, representados por primos, y multiplicar por

p(x_n)

lleva un

1

al siguiente bit

The recursion is binary counting: dividing by

X(x_n)

clears the trailing prime “ones” and multiplying by

p(x_n)

carries a

1

into the next bit

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 que representan los bits finales iguales a

1

(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

Respuesta: 149

Nivel de dificultad: 3270

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años