Foros de matemática
18/11/2017, 01:37:54 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: 1 ... 8 9 [10]   Ir Abajo
  Imprimir  
Autor Tema: Anatomía-II de los Números Primos. Una Factorización Estructural.  (Leído 14687 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #180 : 04/05/2016, 08:27:45 pm »

Buenas Feriva....



Cita
Tú no tiene problema para averiguar sin un número de 200 cifras o así es primo, tu programa lo hace en un tiempo despreciable (es así, ¿no?). Bien pues si es así mi proposición es que pruebes esto...

• En PRIMALIDAD no hay ningún problema en determinar naturales de hasta 1.250 digitos si son o no primos, con un tiempo de menos de medio segundo, es decir menos de 500 milisegundos y hasta naturales de 2.500 digitos, el tiempo maximo será hasta 1 segundo y ya para naturales de hasta 5.000 y un poco mas de digitos, cada evaluación se lo hará entre 1 a 2 segundos.


* Bueno, respecto a la metodología que planteas, probando evaluaciones, recién me di cuenta de lo que tratas de decir, con que si "k" es primo y divide a su reciproco [texx]m=2n-k[/texx] entonces también dividiría a [texx]2n[/texx] asi como sucede en tu ejemplo.
→ Luego de volver a ler lo que dijiste, comprendí que se debería partir de la raiz cuadrada de "2n" que para este caso, debe ser impar y algo que no dijiste, que este debe ser compuesto, pues intentamos factorizarlo con la metodología de intervalos de Feriva... por lo que no nos sirve el Sprimo 2, al no ser divisor de ningún natural compuesto impar y respecto al Sprimo 3, tampoco nos sirve, pues vasta con determinar a su primo PIG de origen, que si no es: {5,7,11,13} el natural impar es divisible entre el Sprimo 3 y esto es para cualquier enésimo natural impar que no pertenezca al Conjunto FV... asi de simple y sencillo.

* El problema que le veo a tu metodología, aunque estoy agradecido por las excelentes sugerencias que siempre tienes, es que si [texx]2n[/texx] es producto de dos primos solamente, siendo esto de igual tamaño en digitos, estos estarán próximos a la raiz cuadrada, siendo uno menor y el otro mayor a la raiz, donde sería lo mismo que evaluar la divisibilidad de [texx]2n[/texx] directamente con los primos dados desde la raiz hasta el primer primo PIG y esto es lo mismo de lo que digo es la Factorización por fuerza bruta, algo que no me dijiste si se dice asi o de otra manera.
→ Comencé evaluando compuestos al azar de 200 digitos, sin nada de resultados, luego pase a 50 digitos y nada, luego a 20 digitos que es algo muy simple de factorizar y nada, al final me quedé evaluando compuestos de 18 digitos, algo realmente simplísimo de hacerlo y mira que nada...

* Es justamente por esto que quiero que intercambiemos criterios en un nuevo hilo, ya que factorizar compuestos de 18 digitos, es ridiculamente simple, haciendolo con la Factorización de Divisores Seleccionados, no necesitando saber primero los primos que se dan hasta la raiz cuadrada del compuesto, sino, primero deben ser seleccionados como "divisores potenciales" en base a los Primos Relacionados, que nos dicen en que Grupo PIG se darán los divisores de un "nb" compuesto, según el Grupo PIG al que pertenezca este compuesto, asi de simple.
→ Este condicionante no lo cumplen todos los "nb" que se generan hasta la raiz cuadrada, sino cuando mucho, aproximadamente el 13% de los naturales "nb" generados, los que ni siquiera debemos comprobar que sean primos, puesto que al ser pocos, la complejidad operacional no se ve afectada en nada, donde si sería mas complejo el operar determinando la primalidad de estos divisores potenciales seleccionados, es por eso que desde el primo 5 y hasta el ultimo natural "nb" generado de 9 digitos, que sería la raiz de un compuesto de 18 digitos, no nos cuesta nada... es mas, la seleccion de los divisores potenciales lo hago por "lineas de generación" al encontrar, que hay secuencias entre lineas de generacion con divisores potenciales y lineas de generacion sin divisores potenciales... deviendo tratar ampliamente todo esto, en otro hilo, no te parece..?

○ Luego que termine la evaluación con tu metodología de un compuesto de 18 digitos, lo volveré a evaluar con los divisores seleccionados y te mostraré los reportes de ambas evaluaciones... Ok.



Saludos...
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.646



Ver Perfil
« Respuesta #181 : 05/05/2016, 04:12:11 am »



Hola, Víctor, buenos días.

A lo que me refería con lo de usar los pares era a esto:

[texx]0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,-,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33
 [/texx]

Para verlo bien haría falta un número más grande, pero con éste puede servir de ejemplo si no empezamos desde el “k” menor o igual que la raíz de 33; empezamos por 16 para tener más “terreno” y analizar la cuestión que quiero que sea vea:

En el lado izquierdo sí podemos decirle al ordenador que se salte los pares directamente, y también los múltiplos de 3 si quieres. Pero en el lado derecho no.

Entonces llegamos a 13, que es primo y no divide a su compañero, 20. Y después a 11, que si divide a sus compañero, 22. Éste es el primo más grande que compone a 33 y para comprobarlo el ordenador ha tenido que dividir un número menor que 33; pero ese número es par. Cuando el número que queremos descomponer sea semiprimo, tendrá sólo dos múltiplos en el segundo intervalo, y esos múltiplos serán pares; y serán más pequeños que “n”.

Imagina que nos dicen “este número es semiprimo, factorícelo”. Entonces podemos prescindir de dividir entre los impares del intervalo de la derecha y probar a dividir sólo los pares, ya que el único múltiplo impar en ese caso será el propio “n”, que es más grande y supone una división más costosa.

Fíjate que esto es lo mismo que decir “usamos sólo los impares en el primer intervalo”, lo que ya hemos dicho. Claro, porque los impares solamente suman “n” con pares; luego es imposible quitar los pares del todo si lo hacemos de esta forma, hay que dejar los del intervalo de la derecha.

Si un número es muy grande, el ordenador tendrá que hacer miles o millones de divisiones para ir comprobando; con este método las hace siempre tomando dividendos menores que “n” y en principio debería tardar un poquito menos, aunque quizá no sea apreciable salvo en números muy, muy grandes, no sé.

Un cordial saludo.
En línea

Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #182 : 05/05/2016, 07:30:05 pm »

Buenas Feriva...


Spoiler (click para mostrar u ocultar)

* Como podrás observar, evalué el compuesto m=630313191744440473 de 18 digitos, determinando primos que se dan, desde la raiz cuadrada hacia el menor de los primos que es el 5.
Luego de haber evaluado con mas de 12 millones de primos como divisores, ninguno resultó ser el específico para el compuesto, lo que de cierta forma, es una evaluación inutil, razón por el cual detuve el proceso.


* Implementé un programa, para realizar la factorización del mismo compuesto, seleccionando divisores desde la raiz cuadrada hasta el primo 5, donde seguro se dará el divisor especifico del compuesto.

Spoiler (click para mostrar u ocultar)

→ Como observarás en el reporte, luego de 8 minutos, se determinó al divisor p=7103821 el cual es primo, y el segundo divisor es el cociente de dividir al compuesto. Notarás que la primera evaluación, por ser lento, se tomó lineas de control de 50.000 mientras que en la evaluación con divisores seleccionados, tuve que tomar lineas de control de 1 millón, por ser demasiado rápido el proceso.

○ Esta diferencia, se dá no solo porque determinamos primos como divisores, sino porque el hecho de que un natural sea primo, no le faculta a ser "divisor universal" de los naturales compuestos, por lo que es un error decir, que la factorización por fuerza bruta, se la haría con solo los primos o algo semejante a esto.


• Respecto a lo que dices, tienes toda la razón, ya que [texx]11 | 22[/texx] donde 22 está en (n,2n) y por lo tanto, tenemos que [texx]11 | 33[/texx] lo que sería una forma mas de encontrar al divisor específico de un compuesto...

* PERO... es impráctico, para factorizar un compuesto algo grande, como el de 18 digitos, donde apliqué lo que dijiste, determinando primos en (0,n) desde la raiz cuadrada, donde al dar con un primo, evaluamos si éste divide a su sumando recíproco de (n,2n) donde está claro que [texx]q=630313191744440473-7103821=630313191737336652[/texx] es el recíproco del divisor primo, que esta en (n,2n) donde se verifica que [texx]630313191737336652 \equiv{0} (mod \ 7103821)[/texx] lo divide exactamente.

→ Mas fíjate que [texx]\displaystyle\frac{630313191744440473}{7103821}=88728754813[/texx] es el "divisor compuesto" de nuestro natural factorizado, donde [texx]q=630313191744440473-88728754813=630313103015685660[/texx] es su recíproco en (n,2n) donde se verifica que [texx]630313103015685660 \equiv{0} (mod \ 88728754813)[/texx] y como dijimos, [texx]88728754813[/texx] no es primo, sino un divisor compuesto... por lo que está mal en buscar tan solo, única y exclusivamente primos, dados, considerados, por tal y cual razón que haya sido, como los uniquísimos "divisores de los compuestos" que de seguro es porque nos lo dice el TFA... y bueno, asi es pero tampoco es...  :sonrisa_amplia:

* En la Factorización con divisores seleccionados, e probado tomar de estos a los que son primos, resultando ser un proceso operacional inútil, puesto que los naturales que se seleccionan, sean primos ó compuestos, entre estos, se dan los "Divisores Específicos" que dividen exactamente al compuesto, lo que es suficiente para demostrar que efectivamente el natural que determinamos su primalidad como no primo, es así, al darse un natural que lo divide exactamente, donde aparte también lo divide el 1 y si mismo, y al tener mas de dos divisores, no es primo, siendo compuesto.
→ Entonces, por qué siempre se separa drásticamente a los primos y compuestos, para entender a los compuestos desde los primos, sin siquiera tener mas herramientas que la divisibilidad, la coprimalidad y ahora esto de los "semiprimos" ?  Qué es un semiprimo ?

Cita
En matemáticas, un número semiprimo, también llamado biprimo, es un número natural que es producto de dos números primos no necesariamente distintos. Los semiprimos menores que 100 son 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, y 95. (sucesión A001358 en OEIS). Los semiprimos que no son cuadrados perfectos se denominan discretos, o directamente semiprimos.
Ref: https://es.wikipedia.org/wiki/N%C3%BAmero_semiprimo

○ No comprendo, el porqué se les dice asi... Tu metodología funciona, pero es muy complejo considerar a solo los primos del intervalo (0,n)... quizás si se evalúa la divisibilidad entre sumandos recíprocos, al darse esto, se encontraría a un divisor de [texx]2n[/texx] donde como dices, el reciproco de (n,2n) es mas pequeño, por lo que en algo se simplificaría la complejidad operacional... tendría que comprobarlo, comparando si esto es mas directo que seleccionar naturales como divisores potenciales... será así ?



Saludos...
En línea
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.059


Ver Perfil
« Respuesta #183 : 06/05/2016, 03:27:31 am »

Buenos Días Feriva...



• Estaba viendo de analizar la metodología que dijiste, para encontrar algo que se relacione con los ciclos de compuestos, puesto que estos, están en relación proporcional al ciclo de sus divisores, donde para algunos compuestos, así parecía darse; pero no para otros.

* Recurrí a la hoja y lapiz, que es lo mejor para un analisis, escribiendo rangos e intervalos, buscando algo que indique una aproximación al ciclo de un compuesto, donde ya con una idea, me fui a Excel, para que se extiendan los intervalos de un natural impar compuesto y al mismo tiempo, se valore su estructura y comparar ambos datos.
→ Al no tener nada claro, crucé mas datos, del compuesto con sus divisores tanto primos como compuestos, donde del ciclo que buscaba, me pasé la Factorización, ya que se repetían los datos que crucé, siendo estos los divisores del compuesto, lo que me llamó la atención y probando con otros compuestos, sucedía lo mismo, de donde saqué unas cuantas reglas ó criterios, para intentar factorizar compuestos con esto.

* Después de implementar los criterios, probé con naturales de 10 digitos, dándose todos aparentemente factorizados, pero revisando, encontré errores, como que se le había tomado al 1 como divisor, cosa que corregí, aprovechando de exportar mas datos y al volver a factorizar los compuestos, era evidente que se habían factorizado correctamente.
→ Implementé una lista de compuestos de 15 digitos, conformados por solo dos primos de igual tamaño en digitos, lo que se considera es mas difícil de factorizar y en esto, medio que se demoró su tiempito, donde habiéndolo dejado que trabaje, me fije luego, encontrando que todos los compuestos habían sido factorizados.

Spoiler (click para mostrar u ocultar)


* Fue genial... luego probé factorizar compuestos de 16 digitos, donde me puse a depurar los procedimientos implementados y tener mas claro como acelerar el proceso, donde probando y probando limites, di con una proporción donde se debía comenzar a evaluar para dar mas directamente con la factorización de los compuestos, es decir, para dar con sus divisores primos como compuestos.


Spoiler (click para mostrar u ocultar)

→ En promedio, cada compuesto se factorizó en un tiempo de 1-2 minutos, que no es algo muy rápido, pero tampoco es tan lento que se diga, siendo que solo tomé unos cuantos criterios para implementarlo en la metodología del programa. Como ya sabes lo medio impaciente que soy, me lancé a intentar factorizar el compuesto de 42 digitos que me diste, cosa que está procesando y eportando datos para analizarlos, donde con un calculo previo que hice, pude ver que si se puede factorizar con esta metodología, que por supuesto falta ajustarla para que sea eficiente en factorizar compuestos mas grandes como los que me dio El_Manco.

○ Ahora veo que el rango y sus intervalos que analizabas, tienen no mas, criterios de primalidad, ya que los primos no se pueden factorizar con esto, por lo que podemos sospechar que el Postulado de Bertrand se cumpliría, aunque los múltiplos de primos dados en los intervalos, no son tanto asi como lo que tu indicas en tus explicaciones... pero en fin, algo de cierto deberá tener, al estar relacionado con la primalidad y la factorización.

☼ Con razón Fermat podía factorizar, por decirlo así, directa y mentalmente, eso que se indica en las publicaciones, donde le dió la factorización, casi de inmediato a su colega Mersenne.



Saludos...
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.646



Ver Perfil
« Respuesta #184 : 06/05/2016, 07:34:38 am »



Hola, Víctor Luis, buenos días.

En principio hay un problema con la factorización debido a que la cantidad de primos que componen a un número no tiene límite; pero este problema desaparece usando una de las ideas que he ido contando a lo largo de este hilo; eso no quiere decir que vaya a ser más rápido factorizar un número (o sí, no sé, dependerá de cómo se aplique).

En principio nos encontramos ante un problema de orden, un problema que parece muy engorroso.

Sea, por ejemplo, el número 26. Tenemos que 25, osea, 5 al cuadrado, es el mayor compuesto que nos entra hasta 26 (quitando el propio 16, que sería el número a factorizar). Entonces, cómo organizamos estos compuestos en orden de menor a mayor atendiendo a los factores elementales (llamados primos, aunque lo digo así por tu idea personal del 2 y el 3)

4,6,8,9,10,12,14,15,16,18,20,21,22,24,25

Veamos:

[texx]2*2=4
 [/texx]

[texx]2*3=6
 [/texx]

[texx]2*2*2
 =8[/texx]

Y aquí ya aparece el lío; cuando entra un factor más de los que íbamos metiendo anteriormente; luego, vuelven a ser dos

[texx]3*3=9
 [/texx]

[texx]2*5=10
 [/texx]

[texx]2*2*3=12
 [/texx]

Y otra vez tres.

No es fácil extraer una regla debido a que la cantidad de factores no es fija y debido además a que los primos que aparecen (por primera vez, como primos que son) no son múltiplos de ninguno de los de detrás (claro, si son primos, cómo van a serlo, qué redundancias digo).

Pero pensemos que cualquier número impar se puede multiplicar por dos y analizar su doble, lo que nos permite considerar los intervalos [texx](0,n) [/texx] y
[texx](n,2n) [/texx]; si conseguimos factorizar “2n”, pues evidentenmente conseguimos también factorizar “n”, pues son los mismos factores pero con el 2 añadido.

Entonces la idea que usaba sirve para organizarnos teóricamente (no estoy proponiendo esto como método, que quizá no arregle nada para dar más velocidad, te lo propongo como idea a analizar que te puede llevar a otras ideas).

Volvamos a tomar esos compuestos

[texx]2*2=4[/texx]

[texx]2*3=6[/texx]

[texx]2*2*2=8[/texx]

pero esto es

[texx]2*4=8[/texx]

y, como dije, siempre se va a poder hacer, siempre podremos asociar todos los factores menos uno, sean lo que sean y obtener el producto de sólo dos números; si tenemos

[texx]a*b*c*d*e[/texx]

pues es también

[texx]a*(b*c*d*e)[/texx]

siendo [texx](b*c*d*e)[/texx], con los factores asociados que sean (aunque sean miles) menor que [texx]2n[/texx]; porque, si no, como ya expliqué, el producto [texx]a*(b*c*d*e)[/texx] sería mayor que [texx]2n[/texx] por la ya famosa desigualdad que he venido utilizando.


Y entonces, con dos factores nada más, sí que nos podemos organizar para dar un cierto orden a los números; no exactamente a los números, a las combinaciones posibles de los números de [texx](0,n)[/texx] donde están representados, con otros más añadidos) todos los productos posibles que suponen todos los posibles compuestos del [texx](0,n)[/texx].

Los compuestos son factores combinados en forma de producto; y lo que buscas es alguna regla o ley que te ayude a resolver más deprisa el problema que supone saber cuáles son esos factores; bien, pues es claro que es una cuestión de combinatoria y que utilizar combinaciones de sólo dos elementos es mucho más sencillo que usar combinaciones de muchos elementos.

Cuando un número es muy difícil de factorizar, se trata de hallar algún factor para romper el hielo, el que sea, aunque sea compuesto y grande; siempre será menor que “n” y, por supuesto, ese factor se compondrá a la vez de primos que compondrán a “n”. Así pues, esta idea quizá pueda servir para ahorrar tiempo; pensemos entonces en números, primos y compuestos, en los productos de sus combinaciones, no sólo en los productos de primos.

Vamos a ver otra vez hasta que punto podemos ordenar esos productos.

El número más pequeño (distinto de 1, el factor más pequeño que no es neutro) es el 2; pero también podrías tomar a partir del 5 en las combinaciones y quitar el 2 y el 3 y sus múltiplos, también nos saldrían productos relativamente ordenados. Yo lo voy a hacer sin quitar el 2 y el 3, para que se vea desde el principio:

 Así pues, estos productos

[texx]2*2[/texx]
[texx]2*3 [/texx]
[texx]2*4[/texx]



nos dan números ordenados de menor a mayor.

Luego, seguimos con esta tanda, la del siguiente más pequeño

[texx]3*3[/texx]
[texx]3*4 [/texx]
[texx]3*5[/texx]

Buscando los primeros de cada tanda, comparamos

[texx]2*2<3*3[/texx]

y a su vez tenemos que

[texx]2*3<3*4 [/texx]... etc.

Los de la segunda tanda nunca son relativamente menores que los de la primera; y así, ya tomemos los primos consecutivos que sean, 5,7... etc.

Sí que va a haber números repetidos en las tandas

[texx]2*6=3*4[/texx] por ejemplo.

Y, vuelvo a repetir, te sirve también quitando pares y múltiplos de 3, ese orden relativo se da igual:

[texx]5*5[/texx]
[texx]5*7 [/texx]
[texx]5*11[/texx]

[texx]7*7[/texx]
[texx]7*11 [/texx]
[texx]7*13[/texx]


Lo repito porque sé que esto se adapta más a tu idea de trabajar, para que veas que te sirve.

Y como ves, por muy “mutlicomunes” que sean siempre los compuestos de (n,2n) siempre los podrás representar con sólo dos factores y usando ese orden relativo a partir de los números que haya en (0,n).

Ya digo que la idea está muy relacionada con la factorización, pues todo el rato estamos hablando de factores de números, si bien hay que reconocer que esto tiene más utilidad en cuanto a estudiar la cantidad de compuestos y primos,  y la posición que ocupan éstos, en el intervalo (n,2n), que es para lo que “yo” lo inventé.


Así pues y en resumen, los compuestos del intervalo (n,2n) son siempre representados por combinaciones de dos elementos; y estos elementos son siempre, números (compuestos o primos) del intervalo (0,n).

Por eso, al ordenarse así esos compuestos que nos dan las combinaciones, sólo los productos de las más “centradas”, como dije, caben en (0,n); esto no necesita mayor demostración, con la explicación que di creo que resulta obvio; se puede decir incluso que puede constituir un teorema, por lo claro, no creo que me equivoque.

Spoiler (click para mostrar u ocultar)


Creo que es completamente necesario establecer una relación de orden que atienda a los factores para poder intentar buscar un método que acorte la factorización de la forma que tú quieres hacerlo; y, bueno, ésta es la idea que puedo darte, un poco la de siempre, pero no se me ocurre nada más de momento, cuando se me ocurra algo más “nuevo” te lo digo.

Un cordial saludo.
En línea

Páginas: 1 ... 8 9 [10]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!