lunes, 24 de mayo de 2010

Solucion al problema del 19 de mayo

Sea f(n)=[1,2,...,n]
Demostrare que f(n) menor 10^n, con lo que quedara demostrado el problema. Llamemos S al conjunto de numeros que cumple esa propiedad. Si 2k+1 esta en S,entonces tenemos que f(2k+2) menor o igual a 2*f(2k+1) menor 10*(10^(2k+1))=10^(2k+2), asi que 2k+2 esta en S.
( f(2k+2) menor o igual a 2*f(2k+1) porque la unica diferencia es el 2k+2 y si no es potencia de un primo, entonces es igual a f(2k+1), y como es par el 2k+2 solo puede ser igual a una potencia de 2, con lo que f(2k+2)=2f(2k+1) )
Es claro que f(n)=(producto de primos menores a n) (p^( pisode(log_p(n) ) )
Tenemos que
f(2n-1)/f(n)=(producto de primos menores a 2n-1)(p_i^r_i)=(Prod p menor o igual a raizde(2n-1))[p_i^r_i](Prod raizde(2n-1) menor p menor o igual a n)[p_i^r_i](Prod n menor p menor o igual a 2n-1)[p_i^r_i]
Donde p_i es el i-esimo primo de menor a mayor.

Tenemos que 0 menor o igual a r_i= PISO(log_{p_i} (2n-1) ) -PISO(log_{p_i} (n) ) menor log_{p_i} (2n-1) - (log_{p_i} (n)+1) menor log_{p_i} (2n)-log_{p_i} (n)+1=
(log_{p_i} (2)+log_{p_i} (n))-log_{p_i} (n)+1 =log_{p_i} (2)+1 menor o igual a 2, asi que r_i menor 2, y como es entero 0 menor o igual a r_i menor o igual a 1, para todo i.

Si r_i=1, y p_i menor o igual a n, entonces p_i^2 menor o igual a p_i^(PISO( log_{p_i} (n) ) + 1) menor o igual a 2n-1 y porlotanto p menor o igual a raizde(2n-1).
Porlotanto
f(2n-1)/f(n)=(Prod p menor o igual a raizde(2n-1))[p_i^r_i](Prod raizde(2n-1) menor p menor o igual a n)[p_i^r_i](Prod n menor p menor o igual a 2n-1)[p_i^r_i]
= (Prod p menor o igual a raizde(2n-1))[p_i^r_i](Prod n menor p menor o igual a 2n-1)[p_i^r_i] menor o igual a (Prod p menor o igual a raizde(2n-1))[p_i](Prod n menor p menor o igual a 2n-1)[p_i].
Es conocido que (Prod p primo menor x)[p] menor 4^x. Tenemos que para todo p primo entre n y 2n-1, p divide a (2n-1)Cn, entonces
(Prod n menor p menor o igual a 2n-1)[p_i] menor o igual a (2n-1)Cn=(2n-2)Cn+(2n-2)C(n-1) menor (1+1)^(2n-2)=4^(n-1), entonces
f(2n-1)/f(n) menor 4^(raizde(2n-1) +n-1)=e^((raizde(2n-1) +n-1)ln4)=A. Comparemoslo con B=10^(n-1)=e^((n-1)ln10)
asi que
A menor a B si y solo si (raizde(2n-1) +n-1)ln4 menor a (n-1)ln10 , y eso se cumple cuando n=7 y como el lado derecho crece mas rapido que el izquierdo, entonces se cumple para n mayor a 7 tambien.

Se comprueba facil que con n=1,2,...,10 cumple, asi que usando induccion, para todos los numeros es verdadera la desigualdad.

6 comentarios:

Quique12 dijo...

Esta difícil de seguir la solución pero parece correcta.

En un momento mencionas que es conocido que (Prod p<=n)[p] < 4^n. La misma demostración que usas para demostrar que ese producto es menor a 4^n, se puede usar para demostrar que f(n) < 4^n.

Muy bien.

Diego627 dijo...

creo que es posible demostrar que (Prod p<=n)[p] < 3^n pero no encuentro como demostrarlo.
(Dehecho creo que lo mejor que puedes demostrar es (Prod p<=n)[p]<e^n )

Quique12 dijo...

Demostrar 3^n es posible, pero necesitas checar los primeros 600 casos.
La técnica usa varias cosas creativas, es genial.

No creo que puedas demostrar menor a e^n.
En el limite es e^n, pero me parece que oscila entre poquito abajo de e^n y poquito arriba de e^n.

Quique12 dijo...

El hecho de que en el límite sea e^n es equivalente al teorema de los números primos.

Diego627 dijo...

podrias dar una pista de como demostrar lo de (Prod p<=n)[p]<3^n, ya lo intente por mucho tiempo pero no sale

Quique12 dijo...

Pues está complicada la solución, así que te paso el link.

Demostración de que es menor a 3^n.

Publicar un comentario