CyM98 << Factorizando al azar >>
Dificultad: Computación Computación Matemática Matemática

Conviene repasar algunos de los conocimientos de computación y de matemática de las lecciones anteriores.

Lecciones anteriores:

Los Números Primos Computación Matemática Matemática

 
Google
Web www.oma.org.ar


Resumen:

El método clásico de factorización consiste en ir probando todos los posibles divisores en orden, de menor a mayor. La factorización también se puede hacer en forma desordenada, siempre y cuando uno siga factorizando los números hasta obtener primos. Vamos a ver un programa que factoriza los números de esta manera, y algunos trucos para ayudarnos a factorizar números a mano.

Factorizando (versión clásica):

Para factorizar un número en primos el método más conocido consiste en tratar de dividirlo por 2, luego por 3, luego por 4 y así sucesivamente. Al encontrar uno que lo divida anotarlo y reemplazar al número original por el cociente. Al aplicar este método, al número 60 queda :

 60|2
 30|2
 15|3
  5|5
  1|

60=22*3*5

Con este método uno siempre obtiene primos. Para demostrarlo llamemos n al número a factorizar y q al menor número que lo divide, o sea n=q*otro. Si q no es primo entonces se puede factorizar, por ejemplo q=x*y. Pero x es menor que q y x divide a n (porque n = x*(y*otro) ). Por lo tanto llegamos a una contradicción y entonces q debe ser primo.

Factorizando (versión al azar):

Otra forma posible es probar al azar si se puede dividir a n en dos factores, y luego tratar de subdividir de esta manera a los factores y seguir así hasta obtener primos. Por ejemplo de aplicando este método al número 60 nuevamente obtenemos :

        60
=  15    *    4
= 3 * 5  *  2 * 2

Pero también podríamos obtener

               60
=   30          *    2
= 5  *    6     *    2 
= 5  *  2 * 3   *    2 

Como vemos en ambos casos el resultado final es el mismo, aunque los números aparecen en otro orden. También coincide con el obtenido antes. Todo estas factorizaciones coinciden porque la factorización de los enteros es única.

O sea que si se toma un numero fijo (por ejemplo 60) y dos personas lo factorizan como un producto de primos, las dos obtienen la misma factorización final. En vez de dos persnas, puede ser la misma persona en dos días diferentes, o una persona y una computadora, o una persona usando dos algoritmos diferentes, o una persona usando biromes de distinto color, o ... Lo importante es que al final la factorización en primos es la misma (salvo el orden).

(Esto vale para los números, pero no es algo tan obvio. ver Ejemplo de factorización no única).

 

  

Para poder ver más ejemplos podemos hacer un programa que realice estas operaciones. Para ello definimos una función recursiva que divide el número en dos partes al azar y luego se llama a si misma para subdividir a las partes.

DefLng A-Z
Const MeAburro =5 'ver nota
Randomize Timer
Print 'Nueva linea
Input"Numero: ", n
PartirEnDos n
End


Sub PartirEnDos (Numero)
   Raiz = Int(Sqr(Numero))-1
   'Prueba solo hasta la raiz cuadrada
   'Pero no con 1
   otro = 1
   For i = 1 To Meaburro*Raiz
      'Prueba muchas veces factorizarlo
      factor = 2 + Int(Rnd*Raiz)
      If Numero Mod factor = 0 Then
         otro = Numero \ factor
         Exit For
      End If
   Next i
   If otro=1 Then
      'Se aburio, quizas Numero es primo
      For factor = 2 To Raiz+1
         If Numero Mod factor = 0 Then
            otro = Numero \ factor
            Exit For
         End If
      Next factor
   End If
   If otro=1 Then
      'Numero es primo
      Print Numero;
   Else
      'Numero = factor * otro
      Print"(" ;
      PartirEnDos factor
      Print" * " ;
      PartirEnDos otro
      Print" )" ;
   End If

(nota : a veces es difícil factorizar el número probando al azar. Si prueba muchas veces (MeAburro*Raiz(Numero)) y no lo logra entonces quizás el número sea primo, así que prueba dividirlo por todos los números menores para estar seguro)

Si ejecutan el programa varias veces, siempre poniendo el mismo número, van a ver que cada vez aparecen los primos en ordenes distintos, o agrupados en distinta forma. Pero si miran cuáles son los que aparecen y cuántas veces se repite, van a ver que solamente cambia el orden.

Factorizando a mano:

Este método no es muy eficiente en la computadora. Pero a veces es bueno para trabajar a mano. Se puede usar una idea parecida al factorizar astutamente un número, cuando encontramos un factor a ojo (la diferencia es que la computadora no tiene "ojo").

Por ejemplo 37730 es claramente múltiplo de 10 y podemos escribir 37730=10 * 3773. Al ver que también es múltiplo de 11 uno puede seguir con la misma idea y obtener 37730=2*5*11*343, pero 343 es 73 así que queda 37730=2*5*11*73. Con el método clásico, que explicamos al principio, hay que dividir varias veces por 7, así que es más engorroso.

Con este mismo método se puede factorizar por ejemplo 324324. A ojo nos damos cuenta de que es 1001*324. Ahora factorizamos 1001=11*91=11*7*13 y también 324=4*81=22*34. Así que ahora sabemos que 324324=22*34*7*11*13. Este resultado lo obtuvimos casi sin hacer cuentas (probar con el otro método y ver que es más largo).

Encontrando números irracionales:

En algunos problemas esto también resulta útil. Por ejemplo queremos saber si Raiz(2) es racional. O sea si existe una fracción a/b tal que a/b=Raiz(2) .

Entonces al elevar al cuadrado quedaría a2/b2=2 o lo que es lo mismo a2=2*b2.

Ahora es un problema de enteros, así que podemos utilizar factorización única.

Para obtener la factorización de a2 factorizamos a. No sabemos exactamente cuál es su factorización, pero al elevarla al cuadrado la cantidad total de veces en que aparece 2 es par (el doble que en a).

Pero el mismo número se puede factorizar como 2*b*b. La cantidad de veces que aparece el 2 en b2 también es par, y al multiplicarlo por 2, aparece uno más así que obtenemos una cantidad impar de 2.

Así que del lado izquierdo la cantidad de 2 es par y del derecho es impar, pero como la factorización es única la cantidad de 2 debería ser igual de ambos lados. Así que no es posible que exista una fracción como la pedida.


Ejercicios:

  1. Se tienen dos números enteros positivos n y m tales que 669240*n=m2. ¿Puede ser n menor que 100?

  2. En una fabrica llenaron 70551 cajas llenas de galletitas (en todas la misma cantidad). Al comprobar que las cajas estaban mal fabricadas sacaron las galletitas de las cajas y armaron 139113 paquetes (en todas la misma cantidad). Si eran menos de 100000000 galletitas, ¿cuántos paquetes y cuántas cajas llenaron?

  3. Modificar el programa para que los primos aparezcan ordenados.

  4. ¿Es posible factorizar 55555555 como producto de dos números de cuatro cifras? ¿Y a 5555555555 como producto de dos números de 5 cifras?

Lecciones siguientes:

Por ahora ninguna

 

 


La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

¿Cuál es tu calificación general de esta clase?

No entendí nada   Mala   Regular   Buena   Muy buena

El contenido de esta clase te resultó:

Nuevo   Conocido en parte   Conocido

El contenido de esta clase te pareció:

Difícil   Regular   Fácil

Los ejercicios de esta clase te parecieron:

Difíciles   Regulares   Fáciles

Comentarios, preguntas, sugerencias:

Agregar más información o una nueva lección sobre:

Funciones (Function)

Factorización única

Nombre y apellido (opcional):

E-mail (opcional):

    


OmaNet   Curso CyM98 OmaNet - Educación Interactiva
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar
duty free alcohol canada buy duty free cigarettes online duty free cigars online duty free cosmetic brands where to buy perfume buy tobacco duty free