Definimos $f(n)$ en los enteros no negativos de la siguiente manera: $f(0)=0$, $f(1)=0$, $f(2)=1$ y para $n\geq 3$, sea $f(n)$ el menor entero positivo que no divide a $n$.
Sea $F(n)=f(f(f(n)))$. Sea $S$ la suma de los primeros valores de $F$ aplicada a los números del $1$ al $2012$ inclusive, es decir,$$S=F(1)+F(2)+F(3)+\cdots +F(2012).$$Calcular el valor de $S$.
Primero hay que darse cuenta de que $f(f(2))=0$;
por lo que $n \equiv 1 (mod 2) \Rightarrow F(n)=0$, o sea si $n$ es impar, como $2$ es el menor numero que no lo divide:
$F(n)=f(f(f(n)))=f(f(2))=f(0)=0$
Entoces decartás de la suma a los impares.
Ahora con los pares. *Para que un numero par no sea divisible por 3, no debe ser multiplo de 6
Entonces suponiendo que $n$ es un par no multiplo de 3, entonces el menor numero que no divide a $n$ es 3
$F(n)=f(f(f(n)))=f(f(3)) = f(2) = 1$
Todos los pares no múltiplos de 6 te dan 1 si le aplicas F;
Hay $2012/2 - 2012/6 = 671$ (redondeando a menor entero) no multiplos de 6
El el caso para los multiplos de $6$, se pueden formar de 2 formas;
1) $n=k\cdot 3\cdot 2$ con k impar
2) $n=2k\cdot 3\cdot 2$ con k impar
En el primer caso, veremos que $f(n)$ será 4 porque $k$ es impar. Entonces $F(n)=f(f(4))=f(3)=2$
En el segundo caso decimos que ademas de ser múltiplo de 6, lo es también de 12
Entonces con los multiplos de 12 sería: (sindo n multiplo de 12)
$f(n)=f(2k\cdot 3\cdot 2)$
Lo que podemos ver es que, $f(n)$ no será 2,3,4,6 ni ningún componente de k.
Lo que si sabemos es que si $f(n)$ es impar: $F(n)=f(f(impar))=f(2)=1$
Y si $f(n)$ es par, $f(f(n))$ será 3, esto de debe a que $f(n)$ no puede ser un múltiplo de 3 porque $n$ es multiplo de 3
Entonces $F(n)= f(3)= 2$.
Ahora solo queda botener $S$
S= Suma de todos los F(pares no multiplos de 6) + Suma de todos los F(multiplos de 12) + Suma de todos los F(multiplos de 6 y no de 12)
Como cada 12 elementos tenemos un multiplo de 12 y otro de 6 solo no de 12 a partir de 6; tenemos $2+1=3$ cada 12
$3(2012-6)/12 = 501,5$ por lo que ese $,5$ representa 6 elementos, pero necesitamos 7 para contar al multiplo de 12 (que da 2)
Lema 1: [math]f(n)\leq 9 siempre que [math]n\leq 2012.
Demostración:
Es claro que si [math]f(n)\geq 10, como [math]f(n) es el menor entero que no divide a [math]n, tenemos en particular que todos los números naturales menores ó iguales a [math]f(n) dividen a [math]n. Como corolario de ésto, se sigue que los primero [math]f(n)-1 números naturales son divisores de [math]n, y por ende, el mínimo común múltiplo de estos números divide a [math]n. Pero, como [math]f(n)\geq 10, entonces, debe ser que [math]\mbox{mcm}[1,2,\ldots,9]=2520 divide a [math]n, pero [math]n es menor que [math]2520, absurdo.
Casos:
1) Si [math]f(n)=9, entonces [math]n=k\cdot \mbox{mcm}[1,2,\ldots, 8], donde además [math]k es tal que [math]n no es múltiplo de [math]9. En particular, [math]n=840k, y [math]k no múltiplo de 3. Es decir, [math]n puede ser [math]840 y [math]1680.
2) Si [math]f(n)=8, entonces [math]n=k\cdot \mbox{mcm}[1,2,\ldots, 7], donde [math]k es tal que [math]n no es múltiplo de 8. Es decir [math]n=420k donde [math]k es impar. En total hay [math]2 valores posibles para [math]n.
3) Si [math]f(n)=7, entonces [math]n=k\cdot \mbox{mcm}[1,2,\ldots, 6], donde [math]k es tal que [math]n no es múltiplo de 7. O sea [math]n=60k, donde [math]k no es múltiplo de 7. Como [math]60k=n\leq 2012, se tiene que [math]k\leq 33. Como los únicos múltiplos de 7 menores que 33 son 7, 14, 21 y 14, en total [math]k puede tomar [math]29 valores.
4) Si [math]f(n)=6, entonces [math]2 y [math]3 son divisores de [math]n, y por ende [math]6=f(n)\mid n, lo cual es absurdo.
5) Si [math]f(n)=5, entonces [math]n=k\cdot \mbox{mcm}[1,2,3,4], donde [math]k es tal que [math]n no es múltiplo de 5. O sea, [math]n=12k y [math]k no es múltiplo de 5. Como [math]12k=n\leq 2012, debe ser [math]k\leq 167, como hay 33 múltiplos de 5 menores que 167, en total [math]n puede tomar 134 valores.
6) Si [math]f(n)=4, entonces [math]n=6k donde [math]k es impar. De manera análoga, debe ser [math]k\leq 335 y como [math]k es impar, [math]n puede tomar [math]168 valores.
7) Si [math]f(n)=3, entonces [math]n=2k donde [math]k no es múltiplo de 3. De manera análoga, se ve que [math]k\leq 1006, y hay 335 números que son múltiplos de 3 menores que 1006, luego [math]n puede tomar 670 valores, dado que [math]k=1 no tendría sentido.
8) Si [math]f(n)=2 entonces [math]n es impar. O sea, [math]n puede tomar 1006 valores.
Ahora, [math]f_{2}(3)=f_2(5)=f_2(7)=f_2(9)=1, donde [math]f_2(x)=f(f(x)). Además, [math]f_2(4)=f_2(8)=2 y [math]f_2(2)=0. Luego, de ésto, es sencillo concluir que la suma buscada es:
Tenemos $S = F(1) + F(2) + ... + F(2012)$, notemos que $f(2k+1) = 2$ ya que $2k + 1 \equiv 1 (mod 2)$. Luego nos queda que $F(2k+1) = f(f(2)) = f(1) = 0$, por lo que todos los términos impares se cancelan, dejándonos con $S = F(2) + F(4) + ... + F(2012)$.
Ahora veamos que en la nueva suma $F'(n) = F(\frac{n}{2})$. Como todos los términos que nos quedaron en la suma son pares, entonces $min$ divisor de $(n) \neq 2$, por lo que sabemos que podemos dividir por 2 si alterar el resultado. La nueva suma: $S = F'(1) + F'(2) + ... + F'(1006)$.
Ahora tenemos que ver cuantos de estos NO son divisibles entre 3. La cuenta seria: $1006 - \lfloor \frac{1006}{3} \rfloor = 671$, es decir, al total le sacamos los múltiplos de 3 y eso nos da los que no son múltiplos de 3. Llamemos $k$ a los números que no son múltiplos de 3, luego $F'(k) = f(f(3)) = f(2) = 1$, lo cual nos deja con un total de $671$ números con un valor de 1 cada uno, por lo que la suma quedaría: $S = 671 + F'(3) + F'(6) + ... + F'(1005)$
PARA PARA PARA, seguro no te diste cuenta que hay un caso especial donde esto no se cumple. Precisamente para $F'(1) = F(2) = f(f(f(2))) = 0$ por lo que la suma en este caso no da 1, si no que da 0. Entonces la suma real es: $S = 670 + F'(3) + F'(6) + ... + F'(1005)$
Viendo que $S = 670 + F'(3) + F'(6) + ... + F'(1005)$, ahora podemos hacer $F''(n) = F'(\frac{n}{3})$, lo cual nos deja con $S = 670 + F''(1) + F''(2) + ... + F''(335)$. Podemos repetir el proceso de calcular cuantos no son múltiplos de 4 en este caso, notemos que todos estos $F''(k) = F(6k)$ por lo cual si $k \equiv 0 (mod 2) \Rightarrow 4 | n$. Entonces la cuenta nos queda: $335 - \lfloor \frac{335}{2} \rfloor = 168$ números que no son múltiplos de 4, luego $F'' = f(f(4)) = f(3) = 2$, por lo tanto la suma queda: $S = 670 + 168.2 + F''(2) + F''(4) + ... + F''(334)$.
Repetimos el proceso: $F'''(n) = F''(\frac{n}{2})$, $S = 670 + 168.2 + F'''(1) + F'''(2) + ... + F'''(167)$. Sacamos los que no son múltiplos de 5: $167 - \lfloor \frac{167}{5} \rfloor = 134$. $F''' = f(f(5)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + F'''(5) + F'''(10) + ... + F'''(165)$.
Repetimos, $F^{IV}(n) = F'''(\frac{n}{5})$, $S = 670 + 168.2 + 134 + F^{IV}(1) + F^{IV}(2) + ... + F^{IV}(33)$. Notemos que los no múltiplos de 6 ya fueron considerados al quitar los de $2$ y $3$, por lo que pasamos a sacar directamente los que no son múltiplos de 7: $33 - \lfloor \frac{33}{7} \rfloor = 29$. $F^{IV} = f(f(7)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + 29 + F^{IV}(7) + F^{IV}(14) + ... + F^{IV}(28)$.
$F^{V}(n) = F^{IV}(\frac{n}{7})$, $S = 670 + 168.2 + 134 + 29 + F^{V}(1) + F^{V}(2) + ... + F^{V}(4)$. Para quitar los no múltiplos de 8 simplemente dividimos por 2 ya que antes quitamos los no múltiplos de 4: $4 - \lfloor \frac{4}{2} \rfloor = 2$. $F^{V} = f(f(8)) = f(3) = 2$, luego $S = 670 + 168.2 + 134 + 29 + 2.2 + F^{V}(1) + F^{V}(2)$
Finalmente, nos queda quitar los no múltiplos de 9, pero como ya quitamos los de 3 antes, simplemente dividimos por 3. En este caso como solamente tenemos $F^{V}(1) + F^{V}(2)$ es fácil notar que ninguno es múltiplo de 9 y por lo tanto $F^{VI} = f(f(9)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + 29 + 2.2 + 2 \Rightarrow $
$$\boxed{S = 1175}$$
$\blacksquare Q.E.D \square .$
Y todos los fines de demostración que se puedan imaginar
Supongamos que $f(n) = c$ donde $c$ es un número con al menos dos factores primos.
Entonces es divisible por algún primo $p$. Sea $k$ el máximo natural tal que $p^k \mid c$
$c = p^k \cdot m$.
$p^{k + 1} \nmid n \Rightarrow p^{k + 1} \nmid p^k \cdot m \Rightarrow p \nmid m \Rightarrow \gcd(p^k, m) = 1 \Rightarrow \operatorname{lcm}(p^k, m) = p^k \cdot m = c$
Como $p^k < c$ y $m < c$, por definición de $f(n)$ ambos deben dividir a $n$.
Si $a \mid n$ y $b \mid n \Rightarrow \operatorname{lcm}(a, b) \mid n$. Entonces si $p^k \mid n$ y $m \mid n \Rightarrow m \mid n$ lo cual es una contradicción, por lo que la suposición inicial era falsa y $f(n)$ no puede tener dos o más factores primos, por lo que $f(n) = p^k$ con $p$ primo.
$F(n) = f(f(f(n))) = f(f(p^k))$ y como $p^k$ es una potencia de dos el menor número que no lo divide es $3$.
$F(n) = f(3) = 2$.
Entonces hay $3$ tipos de números y la suma va a ser $S=0A + 1B + 2C$ donde $A + B + C = 2012$ y $A$ son la cantidad de impares (más el 2 que también da $F(0) = 0$), $B$ es la cantidad de pares mayores a 2 tal que $f(n) = p^k$ con $p \neq 2$ y $C$ es la cantidad de pares tal que $f(n) = p^k$ con $p = 2$.
$0A + 1B + 2C = (B + C) + C = (2012 - A) + C$. La cantidad de números que $F(n) = 0$ es $A = \frac{2012}{2} + 1 = 1007$.
Ahora para contar los pares tal que $f(n) = p^k$ con $p = 2$ veamos que para que $f(n) = x$ debe suceder que $x \equiv 0 \mod \operatorname{lcm}(1, 2, \cdots, x - 1)$ pero $x \not\equiv 0 \mod \operatorname{lcm}(1, 2, \cdots, x)$
$k > 1$ porque como $n$ es par, $2^1 \mid n$
$k < 4$ ya que $\operatorname{lcm}(1, 2, \cdots, 2^4 - 1) > 2012$
Entonces solo quedan los casos $f(n) = 4$ y $f(n) = 8$
$f(n) = 4$
