Question

Define la función $f_1$ en los enteros positivos poniendo $f_1(1) = 1$ y, si $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ es la factorización en primos de $n \gt 1,$ entonces $\begin{aligned} &f_1(n) = (p_1 + 1)^{e_1 - 1}(p_2 + 1)^{e_2 - 1} \\ &\quad \cdots (p_k + 1)^{e_k - 1}. \end{aligned}$ Para cada $m \ge 2,$ sea $f_m(n) = f_1(f_{m-1}(n)).$ ¿Para cuántos $N$ en el rango $1 \le N \le 400$ la sucesión $(f_1(N), f_2(N), f_3(N), \ldots)$ es no acotada? Nota: una sucesión de números positivos es no acotada si para cada entero $B,$ hay un miembro de la sucesión mayor que $B.$

Define the function $f_1$ on the positive integers by setting $f_1(1) = 1$ and if $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ is the prime factorization of $n \gt 1,$ then $\begin{aligned} &f_1(n) = (p_1 + 1)^{e_1 - 1}(p_2 + 1)^{e_2 - 1} \\ &\quad \cdots (p_k + 1)^{e_k - 1}. \end{aligned}$ For every $m \ge 2,$ let $f_m(n) = f_1(f_{m-1}(n)).$ For how many $N$ in the range $1 \le N \le 400$ is the sequence $(f_1(N), f_2(N), f_3(N), \ldots)$ unbounded? Note: a sequence of positive numbers is unbounded if for every integer $B,$ there is a member of the sequence greater than $B.$

$15$

$16$

$17$

$18$

$19$

Respuesta: D

Conceptos:factorización en primos divisibilidad recursión

Nivel de dificultad: 2520

Pista pequeña:

Si $N_2$ es múltiplo de $N_1$ entonces $f_1(N_2)$ es múltiplo de $f_1(N_1),$ así que la no acotación la heredan los múltiplos; halla el $N$ “esencial” mínimo

If $N_2$ is a multiple of $N_1$ then $f_1(N_2)$ is a multiple of $f_1(N_1),$ so unboundedness is inherited by multiples; find the minimal “essential” $N$

Pista grande:

Un $N$ esencial tiene todos los exponentes al menos $2$ y a lo sumo dos factores primos; analiza primero las potencias de $2,3$ , y luego las pocas potencias de primos y parejas de primos restantes por debajo de $400$

An essential $N$ has every exponent at least $2$ and at most two prime factors; analyze powers of $2,3$ first, then the few remaining prime powers and prime pairs below $400$

Solución:

Si $N_2$ es múltiplo de $N_1$ , entonces $f_1(N_2)$ es múltiplo de $f_1(N_1),$ así que si $S_{N_1}$ es no acotado, también lo es $S_{N_2}.$ Llamemos esencial a $N$ si es no acotado pero ningún divisor propio lo es. Un $N$ esencial debe tener todos los exponentes al menos $2,$ y $(p_1\cdots p_k)^2\le400$ obliga a que haya a lo sumo dos primos.

Para $n=2^a3^b,$ dos iteraciones llevan el par de exponentes a $(2a-4,2b-3).$ Por tanto, la órbita es no acotada exactamente cuando $a\ge5$ o $b\ge4,$ lo que produce los valores esenciales $2^5=32$ y $3^4=81.$ Para un solo primo distinto, la cota deja únicamente $5^2,5^3,7^2,7^3,11^2,13^2,17^2,19^2;$ al aplicar directamente $f_1$ , solo $7^3=343$ queda esencial. Con dos primos, $p_1p_2\le20$ deja los pares $(2,5),(2,7),(3,5)$ además de $(2,3).$ Al aplicar $f_1$ a sus posibles productos potentes, solo queda $2^4\cdot5^2=400.$

Sus múltiplos hasta $400$ son $\lfloor\frac{400}{32}\rfloor=12,$ $\lfloor\frac{400}{81}\rfloor=4,$ $\lfloor\frac{400}{343}\rfloor=1,$ y $\lfloor\frac{400}{400}\rfloor=1,$ sin intersecciones, para un total de $12+4+1+1=18.$

Por lo tanto, la respuesta correcta es D.

If $N_2$ is a multiple of $N_1$ then $f_1(N_2)$ is a multiple of $f_1(N_1),$ so if $S_{N_1}$ is unbounded so is $S_{N_2}.$ Call $N$ essential if it is unbounded but no proper divisor is. An essential $N$ must have all exponents at least $2,$ and $(p_1\cdots p_k)^2\le400$ forces at most two primes.

For $n=2^a3^b,$ two iterations send the exponent pair to $(2a-4,2b-3).$ Thus the orbit is unbounded exactly when $a\ge5$ or $b\ge4,$ producing the essential values $2^5=32$ and $3^4=81.$ For a single other prime, the bound leaves only $5^2,5^3,7^2,7^3,11^2,13^2,17^2,19^2;$ direct application of $f_1$ leaves only $7^3=343$ essential. With two primes, $p_1p_2\le20$ leaves the pairs $(2,5),(2,7),(3,5)$ besides $(2,3).$ Applying $f_1$ to their possible squareful products leaves only $2^4\cdot5^2=400.$

Their multiples up to $400$ number $\lfloor\frac{400}{32}\rfloor=12,$ $\lfloor\frac{400}{81}\rfloor=4,$ $\lfloor\frac{400}{343}\rfloor=1,$ and $\lfloor\frac{400}{400}\rfloor=1,$ with no overlaps, for a total of $12+4+1+1=18.$

Thus, the correct answer is D.

2012 AMC 12B Problema 24

Respuesta: D

Nivel de dificultad: 2520

Pista pequeña:

Pista grande:

Solución:

El Problema 24 en otros años