Autor Tema: UTF por fuerza bruta !!! re bruta...

0 Usuarios y 1 Visitante están viendo este tema.

19 Diciembre, 2019, 02:32 am
Leído 1431 veces

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Hola, se me a ocurrido la feliz idea de probar unos algoritmos de suma ,resta, multiplicación y división, para números muy grandes, ahora que me creo un poco más ayornado intentar con el UTF, a ver que pasa y analizar los datos que arroje .

Pero me pregunte...porque probar con todos los números y cada uno de los \(  x,y,z , n\in \mathbb N \) si es posible, eliminar de la lista unos cuantos, e ir a los que si tienen soluciones posibles.

Para eso  me he planteado como desarrollar números que tengan dicha posibilidad.

0)eliminemos  lo obvio

\( n>2 \)
\( x,y,z\geq1 \)

1) Si \( x^n+y^n=z^n \Longleftrightarrow{}\dfrac{x^n}{z^n}+\dfrac{y^n}{z^n}=1=\left(\dfrac{x}{z}\right)^n+\left(\dfrac{y}{z}\right)^n \)

2)por aritmética modular tenemos \( n\cdot x \mod z+n\cdot y \mod z\equiv{}1 \mod z \)

3) entonces \(  \exists K,a,b \in \mathbb N / \quad n(x+y)=b=a(zK+1) \)

4) sabemos que \( z>x \) y que \( z>y \) y que como\(  x\neq y \) porque el 2 no tiene raíz enésima entera, podemos limitar la búsqueda a \( x<y \) ya que es indistinta una solución \( x=x_o \) y \( y=y_0 \) que \( x=y_0 \) e \( y=x_0 \)

5) si \( n(x+y) \) es \( 0\mod n \) entonces \( K \) es \( \dfrac{n-1}{z} \mod n \)

lo que me indica que  debo hacer una búsqueda tal que

mi variable será z como un contador empiezo en \( z=2\Rightarrow{ } \)  y \( n>3 \) , pero la idea es solo probar para \(  Kz+1 \equiv{}0 \mod n \forall K\geq 1 \) osea para valores

\( b=\dfrac{a}{n}(Kz+1) \) donde \( n|a \)

luego tenemos \( x+y=b \) y haría un bucle en \( y \) desde 2 a \( b/2 \) donde tomando \( x=b-y \) y probando sobre la fórmula del teorema...\( x^n+y^n=z^n \) para ver si la pego!!! ;D

bueno por lo pronto quisiera saber si hay error troncal.... en eliminar de este modo al resto de los candidatos a solución, o me pierdo una parte importante.

también quisiera saber  hasta donde se ha probado por fuerza bruta, es decir para que el intento tenga sentido, espero que sea menor al millón de cifras... digamos una 10-20 cifras talvez ... :-\


Saludos  \(\mathbb {R}^3\)

19 Diciembre, 2019, 09:13 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,105
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Hola, se me a ocurrido la feliz idea de probar unos algoritmos de suma ,resta, multiplicación y división, para números muy grandes, ahora que me creo un poco más ayornado intentar con el UTF, a ver que pasa y analizar los datos que arroje .

Pero me pregunte...porque probar con todos los números y cada uno de los \(  x,y,z , n\in \mathbb N \) si es posible, eliminar de la lista unos cuantos, e ir a los que si tienen soluciones posibles.

No acabo de entender del todo la filosofía de lo que quieres hacer.

Entiendo que simplemente reducir un poco las posibilidades para comprobar números que puedan cumplir la ecuación. Si todavía tienes infinitos casos por comprobar, eso más allá de una curiosidad, no tiene demasiada utilidad.

Citar
Para eso  me he planteado como desarrollar números que tengan dicha posibilidad.

0)eliminemos  lo obvio

\( n>2 \)
\( x,y,z\geq1 \)

1) Si \( x^n+y^n=z^n \Longleftrightarrow{}\dfrac{x^n}{z^n}+\dfrac{y^n}{z^n}=1=\left(\dfrac{x}{z}\right)^n+\left(\dfrac{y}{z}\right)^n \)

2)por aritmética modular tenemos \( n\cdot x \mod z+n\cdot y \mod z\equiv{}1 \mod z \)

Ahí, me perdí. ¿De donde te sacas eso?. Por ejemplo si \( n=2 \), \( x=3 \), \( y=4 \), \( z=5 \) tienes que:

\( 2\cdot 3+2\cdot 4=14\neq 1 \) mod \( 5 \)

Citar
también quisiera saber  hasta donde se ha probado por fuerza bruta, es decir para que el intento tenga sentido, espero que sea menor al millón de cifras... digamos una 10-20 cifras talvez ... :-\

No lo se, la verdad. En cuanto que el Teorema ya ha sido probado con toda generalidad, supongo que los esfuerzos por hacer experimentos con cálculos concretos ha decaído mucho.

Saludos.

19 Diciembre, 2019, 11:44 am
Respuesta #2

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Nada, debería haber buscado "aritmética modular" antes de escribir semejantes cosas.
Mas si pruebas que son ciertas las que crees recordar con el 2
 \( 2+2=2\cdot2=2^2 \) sin palabras.

Es lógico que no pudo reducir el número de intentos de infinito, pero intento llegar a checar números mas grandes en menos tiempo de pc, descartando por alguna regla sencilla de probar los que de ningún modo son resultado.

Edito: veo que si \( x \) es \( x\mod z \) e \( y \) es \( y \mod z \) no logro nada con la aritmetica como iluminado que estaba, así que a foja cero vuelvo.

saludos y gracias.
Saludos  \(\mathbb {R}^3\)

21 Diciembre, 2019, 05:11 am
Respuesta #3

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Retomo,

evaluar todo el plano (x+,y+) en búsqueda de que \( \sqrt[n]{x^n+y^n} \) sea entero lleva un cierto por calculo,

mi idea es reducir el numero de cálculos que de buenas a primeras se sabe no darán un resultado positivo porque quiebran alguna relación-

Por ello me propongo lo contrario partiendo de los \( z^n \) que debo llegar se que o bien x o y como máximo pueden tomar valor \( z-1  \)

Luego no tiene sentido probar números por debajo de \( y\geq\sqrt[n]{z^n+(z-1)^n} \) y por encima de \( y\leq z-1 \)

La idea es ir con

\( n\in[3,100] \)
\( Z\in[100, 1e50] \)
 guardar los datos en matriz de z x n
\( y\in[\lfloor\sqrt[n]{z^n\color{red}-\color{black}(z-1)^n}\rfloor+1, z-1] \)

esperando  encontrar \( z^n-y^n \)   ese entero en  la tabla  buscando en la fila o columna del valor n donde venimos almacenando las potencias  n ésimas de los z.


Saludos  \(\mathbb {R}^3\)

24 Diciembre, 2019, 04:47 pm
Respuesta #4

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,105
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Retomo,

evaluar todo el plano (x+,y+) en búsqueda de que \( \sqrt[n]{x^n+y^n} \) sea entero lleva un cierto por calculo,

mi idea es reducir el numero de cálculos que de buenas a primeras se sabe no darán un resultado positivo porque quiebran alguna relación-

Por ello me propongo lo contrario partiendo de los \( z^n \) que debo llegar se que o bien x o y como máximo pueden tomar valor \( z-1  \)

Luego no tiene sentido probar números por debajo de \( y\geq\sqrt[n]{z^n+(z-1)^n} \) y por encima de \( y\leq z-1 \)

En lo que está en rojo creo que querías poner otra cosa, pero no estoy seguro de que. Ten en cuenta que:

\( \sqrt[n]{z^n+(z-1)^n}> \sqrt[n]{(z-1)^n}=z-1 \)

Por otra parte sigo sin ver sentido a estas alturas plantearse semejantes cálculos: ¡ya sabemos que no vas a encontrar enteros que verifiquen la ecuación!.

Saludos.

24 Diciembre, 2019, 06:26 pm
Respuesta #5

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Gracias Luis , por ser tan paciente, con tu respuesta me di cuenta que efectivamente me equivoque , pero  lo que quería expresar no es lo que me indicas, fíjate que edite en rojo el signo dentro de la ecuación final de anterior post...

Te comento lo que he avanzado, he creado los cubos y las potencias cuartas del  primer millón de Naturales, eso fue fácil, unos 20 minutos,...

Pero claro ahora la fuerza bruta no sirve de mucho al checar  si la suma de dos de ellos cualesquiera pertenece a la Lista..  Pues com es un proceso de tiempo N^2 para el primer millar de datos se tomo el mismo tiempo, y para el millón la cosa se va a poner  mucho más lenta a medida que N crece.

Pero no me desanima eso ya lo sabía de entrada, por eso lo que quería era limitar las pruebas , para que no tenga que perder el tiempo checar si \( 8+27 = 1000? \)  es decir decir buscar la forma de limitar el tiempo de búsqueda del resultado suma sobre la tabla, o hacer \( z^n-x^n -y^n=0 \)   pero eso ya es un tiempo N^3... puse ejemplo para n=3 pero lo que quiero es trabajar con n mayores.

la pero fatiga viene de VBasic software bajo licencia microsoft, que no permite manejo de matrices de datos de 1000000 de datos string...luego tengo que estar continuamente leyendo archivos de datos TXT donde almaceno la lista de las potencias en orden creciente, el tema es que para leerlas siempre tengo que entrar por el primer dato  el 1 y no por el 822^3 que probablemente en algún momento sea el mínimo  entre \( z^3- (z-1)^3 \) luego me podría ahorrar de leer esos datos.

Pero estuve haciendo cuentas y el mínimo necesario esta en \( nz^{n-1} \) es decir siempre es la fraccion \( n/z \) como z siempre es mucho mayor que n entonces es muy poco lo que me puedo ahorrar respecto de lo que una programación mas sencilla.

Así que bueno antes de tirar la toalla, voy a  rebuscarmelas distinto,  sin salirme de la posibilidad de usar string para representar números largos,  ej lo hice pensando en \( 1000000^{1000} \) que tiene 6000 dígitos... la suma, la resta y la multiplicación funcionan de maravilla, y bastante rápido,  pero lo que es lento es cotejar si un numero esta en la lista de cubos, ya que debo comparar desde el principio, y no desde cierto numero mínimo inicial, o cierta cantidad de cifras del numero z.
Saludos  \(\mathbb {R}^3\)

26 Diciembre, 2019, 10:04 am
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,105
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Gracias Luis , por ser tan paciente, con tu respuesta me di cuenta que efectivamente me equivoque , pero  lo que quería expresar no es lo que me indicas, fíjate que edite en rojo el signo dentro de la ecuación final de anterior post...

Ya, ya. Lo único que yo indiqué es que lo que habías escrito no tenía sentido. Con el menos, bien.

Citar
Te comento lo que he avanzado, he creado los cubos y las potencias cuartas del  primer millón de Naturales, eso fue fácil, unos 20 minutos,...

Pero claro ahora la fuerza bruta no sirve de mucho al checar  si la suma de dos de ellos cualesquiera pertenece a la Lista..  Pues com es un proceso de tiempo N^2 para el primer millar de datos se tomo el mismo tiempo, y para el millón la cosa se va a poner  mucho más lenta a medida que N crece.

Pero no me desanima eso ya lo sabía de entrada, por eso lo que quería era limitar las pruebas , para que no tenga que perder el tiempo checar si \( 8+27 = 1000? \)  es decir decir buscar la forma de limitar el tiempo de búsqueda del resultado suma sobre la tabla, o hacer \( z^n-x^n -y^n=0 \)   pero eso ya es un tiempo N^3... puse ejemplo para n=3 pero lo que quiero es trabajar con n mayores.

la pero fatiga viene de VBasic software bajo licencia microsoft, que no permite manejo de matrices de datos de 1000000 de datos string...luego tengo que estar continuamente leyendo archivos de datos TXT donde almaceno la lista de las potencias en orden creciente, el tema es que para leerlas siempre tengo que entrar por el primer dato  el 1 y no por el 822^3 que probablemente en algún momento sea el mínimo  entre \( z^3- (z-1)^3 \) luego me podría ahorrar de leer esos datos.

Pero estuve haciendo cuentas y el mínimo necesario esta en \( nz^{n-1} \) es decir siempre es la fraccion \( n/z \) como z siempre es mucho mayor que n entonces es muy poco lo que me puedo ahorrar respecto de lo que una programación mas sencilla.

Así que bueno antes de tirar la toalla, voy a  rebuscarmelas distinto,  sin salirme de la posibilidad de usar string para representar números largos,  ej lo hice pensando en \( 1000000^{1000} \) que tiene 6000 dígitos... la suma, la resta y la multiplicación funcionan de maravilla, y bastante rápido,  pero lo que es lento es cotejar si un numero esta en la lista de cubos, ya que debo comparar desde el principio, y no desde cierto numero mínimo inicial, o cierta cantidad de cifras del numero z.

Sobre esto nada que decir.  ::)  ::)

Saludos.

26 Diciembre, 2019, 10:47 am
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 1,889
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Coincido con lo dicho por Luis sobre la inutilidad de comprobar el teorema de Fermat númericamente al estar ya demostrado. Si quieres hacer cálculos por fuerza bruta creo que sería mejor dedicarlos a algo que no esté demostrado, como la conjetura de Goldbach o la de Collatz, o a encontrar nuevos primos. Pero cada uno usa su tiempo como quiere, así que si quieres buscar soluciones de Fermat adelante.

Lo que me ha llamado muchísimo la atención es que parece que estés usando Visual Basic para esto (!!!). Por dios, ¡usa C o Fortran! Usar VBasic es ponerte restricciones adicionales. VBasic no está pensado ni preparado para hacer este tipo de cálculos y te será tremendamente ineficiente.

Por otro lado, 20 minutos para calcular los cubos y potencias cuartas del primer millón de números me parece una pasada. Debería tardar muchísimo menos. Tal vez los estés imprimiendo por pantalla o escribiendo en un fichero, como parece que he entendido. Es mejor no hacerlo y hacer directamente las comprobaciones, en otro caso no llegarás muy lejos.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

26 Diciembre, 2019, 09:28 pm
Respuesta #8

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...

Hola geómetracat, gracias por el interés,  por ahí si soy mas ingenuo de lo que creo, el UTF esta demostrado para todos los n >3? o solo para n=3 , usar los cubos es lo mas rápido que podía resolver , hacer las potencias cuartas es hacer una multiplicación mas y guardar el numero, pero recuerda que no es multiplicar  \( a\cdot a\cdot a \) para tener un cubo lo que hago , sino que uso un algoritmo de multiplicación a dos cadenas de texto de valor \( a \) y \( a^2 \)  que contiene los números de la manera tradicional (como la hicieras a mano)por recursividad ,se que los hay mas rápidos, pero no para enteros largos. Entonces esto si es mas lento que la multiplicación directa, cuya precisión se pierde después del dígito 15 en cualquier potencia,  pero yo en teoría no la puedo perder nunca.

La idea como te dije no es probar solo n=3 sino hasta n=1000 y justamente lo que estoy buscando es hacer un poco mas eficiente la tarea... y no perder el tiempo en combinaciones que a priori resulta obvias que no pueden dar resultados positivos de ningún modo.

Uso VB porque es lo que se programar, es decir no creo que cambiar el lenguaje me ayude a reducir el tiempo, si es que para escribirlo primero tengo que aprender a programar, he usado c++ , fortran, pascal, java, VBScript, asp,html,Sql, algo en unix, como gambas, pero con vbasic, estoy mas cómodo.

Soy perfectamente consiente de mis limitaciones, lo que yo haga, seguro alguien lo hizo  antes, mejor y mas rápido, pero no quita que sea interesante intentarlo, mas que nada me interesa hacer algo medianamente eficiente o que al menos no cualquier calculadora lo pueda
hacer.
 

 
Saludos  \(\mathbb {R}^3\)

27 Diciembre, 2019, 09:47 am
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,105
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Hola geómetracat, gracias por el interés,  por ahí si soy mas ingenuo de lo que creo, el UTF esta demostrado para todos los n >3? o solo para n=3 ,

El Teorema de Fermat está completamente demostrado, es decir, para todo \( n\geq 3 \).

Saludos.