Cargando...
 
Imprimir

Divisores de un entero y la función divisor

Image
Cuando dividimos un número entero entre otro, lo podemos hacer de dos formas: mediante una división exacta o mediante una división entera o euclidea.

El resultado de la división exacta de dos enteros es, con carácter general, un número real... (mejor dicho, racional) y el resultado de una división euclidea es otro entero. Si tengo que repartir 7 manzanas entre 2 personas, tocan a 3.5 manzanas cada una si realizo una división exacta, y si no puedo o no quiero partir una manzana, tendré que repartilas por unidades enteras (división entera o euclidea): tocan a 3 cada persona (cociente entero) y sobra una (resto).

Considerando sólo la división entera, decimos que un número entero k es divisor de otro entero n si existe un tercer entero a tal que n=k·a. Dicho de otro modo, al dividir de manera entera el número n entre k, el resto es 0. En matemáticas suelen expresar esta relación entre un número n y uno de sus divisores k como k|n y se suele leer "k divide a n" o "k es divisor de n", aunque también puede interpretarse como que "n es múltiplo de k". A los divisores de un número n también se les suele llamar factores propios o divisores propios pero de esta denominación queda excluido el propio número n.

Los divisores de un número entero han sido objeto de estudio de múltiples matemáticos a lo largo de la historia -podemos remontarnos hasta el propio Euclides(external link), y es probable que no fuera el primero-. Siempre se han buscado en los números enteros propiedades y cualidades que fueran prácticas, curiosas o incluso mágicas. En la actualidad, este estudio forma parte de la teoría elemental de números(external link).

En este artículo vamos a intentar implementar un par de algoritmos sencillos para obtener todos los divisores de un número, y hablaremos de alguna que otra cosa más con relación a ellos.



La mayoría de los lenguajes de programación permiten el manejo de variables que almacenan números enteros (sin decimales) y de variables que almacenan números reales (con decimales). Ésta distinción se debe principalmente a que la circuitería que realiza las principales operaciones aritméticas con ambos tipos de datos suele ser radicalmente distinta. En la memoria principal, durante la ejecución de un programa, los números enteros suelen codificarse utilizando el complemento a 2? (o con menos mucha frecuencia, otros sistemas como BCD? o signo/magnitud?)), y por tanto, cuando entran a la ALU? lo hacen en este formato y la circuitería de la ALU opera con ellos utilizando ese mismo formato. Sin embargo, los reales (bueno los reales de los lenguajes de programación no son exactamente reales, ya que se realizan redondeos... por ejemplo, una variable de tipo real en C no puede almacenar el valor exacto de pi, pero con carácter general les seguiremos llamando "reales") se almacenan normalmente utilizando la codificación conocida como coma flotante? (con menos frecuencia se utilizan otras como la coma fija? o el BCD?).

El caso es que esa distinción afecta a la operación de división en los lenguajes de programación: entre dos variables de tipo real (con decimales) se aplica una división exacta (bueno... lo más exacta que se pueda) y el resultado es un cociente exacto (con decimales). Sin embargo, entre dos enteros se suele aplicar una division entera, y el resultado es también un entero. Además, también será posible aplicar la operación "modulo" (o resto) de la división.

En lenguajes como C/C++/C#/Java el operador de la división es "/" (binario e infijo) y se comporta de la manera descrita: cuando se aplica a reales hace una división exacta y cuando se aplica a enteros, hace una división entera y devuelve un cociente entero. Además, existe un operador binario e infijo "%" aplicable sólo a enteros que nos devolverá el resto de la división entera.

¿Y que pasa si se divide un real entre un entero o un entero entre un real? Bueno... depende. Cada lenguaje -incluso distintas implementaciones del mismo lenguaje- pueden comportarse de maneras distintas, aunque en general, en el momento en que se ve implicado un real sea dividendo o divisor se aplica la división exacta. La mayoría de compiladores o intérpretes utilizan el mecanismo comunmente llamado coerción, que consiste en una conversión automática de tipos cuando son compatibles y ésta conversión es razonablemente necesaria y sensata. En el caso de la división, si uno de los operandos es real y el otro no, se suele forzar la conversión automática -y transparente para el programador- del operando entero a real, sólo a efectos de realizar la división.

En lenguajes como Pascal/Delphi y similares existen dos operadores binarios infijos distintos para las divisiones: el operador "/" que implica que se desea una división exacta y el operador "DIV" que implica que se desea una división entera. El operador "MOD" (también binario e infijo) devuelve el módulo o resto de la división entera.

Bueno... dicho todo esto, está claro que vamos a trabajar con variables enteras, utilizando divisiones enteras y restos -módulos- de las divisiones. Como de costumbre, el lenguaje utilizado será C#.

Pero vamos a meternos en harina....

Algortimo para obtener los divisores de un número entero.


Vamos a ver un par de formas de obtenerlos.

Primer método: probando posibles divisores

Dado un número entero positivo n, lo primero que se nos ocurre es para obtener sus divisores es ponernos a dividir por cualquier número entero positivo k tal que k<=n, y si el resto de la división es 0, entonces ese k es un divisor.

Vamos a probar, por ejemplo, con n=6

6%1 es 0 → 1 es divisor
6%2 es 0 → 2 es divisor
6%3 es 0 → 3 es divisor
6%4 es 2 → 4 NO es divisor
6%5 es 1 → 5 NO es divisor
6%6 es 0 → 6 es divisor

Eso está muy bien... buena idea, pero podemos mejorarlo. Por un lado, podemos darnos cuenta de que 1 y n siempre son divisores de n. Aunque con esto sólo no mejoramos mucho.

Observemos sin embargo el 2. 2 es un divisor. Eso significa que 6=2·a, siendo a un entero cualquiera... peeeeero a entonces, también es un divisor de 6, porque existe un entero (el 2) tal que multiplicado por a da 6. ¿Y cual es ese entero a? pues obviamente 6/2... es decir, 3.

Eso quiere decir que cada vez que encontramos un divisor, automáticamente encontramos otro más. Por ejemplo, si consideramos n=14... y probamos si 2 es divisor 14%2 es 0, por lo tanto sí es divisor. Entonces 14/2, es decir, 7 también es divisor. Por lo tanto, no necesitamos probar todos los enteros entre 1 y n. ¿Cuales son, entonces, los que debemos revisar? Gracias a los trabajos del matemático Al-Marrakushi ibn Al-Banna, del siglo XIII y a otros matemáticos posteriores sabemos que basta con probar los números comprendidos entre 1 y la raíz cuadrada de n.

En el caso de n=6, la raíz cuadrada es 2 y pico, así que sólo hay que probar el 1 y el 2. En el caso de n=14, la raíz cuadrada es 3 y pico, así que sólo hay que probar entre 1 y 3. Cada divisor de n menor que la raíz cuadrada de n que encontremos nos dará también otro mayor que la raíz cuadrada de n.

Tan sólo hay que tener especial cuidado cuando la raiz cuadrada de n no tiene decimales, porque podríamos obtener un divisor por partida doble. Por ejemplo, si n=900, la raíz cuadrada de n es exactamente 30... así que probaremos a ver si son divisores los números entre 1 y 30. Cuando lleguemos al 5, por ejemplo, comprobaremos que 900%5 es 0, con lo cual 5 es divisor, y por lo tanto, también lo es 900/5, es decir 180... vale... ningún problema. Cuando lleguemos al 30 -el último a probar-, veremos que es divisor, y por lo tanto también será 900/30... pero 900/30 es también 30... así que hay que llevar cuidado con no anotarlo dos veces.

Con esto, ya nos podemos lanzar a la piscina y obtener un algoritmo tal que le pasemos un entero positivo n y nos devuelva una lista con los divisores de n ordenados de menor a mayor.

C#
static List<long> DivisoresProbando(long n)
{
   //Lista para almacenar los resultados
   List<long> lista_divisores=new List<long>();
   //Probaremos con valores entre 1 y éste valor
   long ultimo_a_probar=(int)Math.Sqrt(n);
   //variable para almacenar el cociente
   long cociente;
 
   for (long i=1;i<=ultimo_a_probar;i++)
   {
      //si i|n
      if (n%i==0)
      {
         cociente=n/i; //hallamos también n/i
         //i es un divisor
         lista_divisores.Add(i);
         //y cociente también lo es. Pero con este if 
         //nos aseguramos de no meter el mismo divisor
         //dos veces.
         if (cociente > i)
         {
            lista_divisores.Add(cociente);
         }
 
      };
   }
   //ordenamos los divisores de menor a mayor
   lista_divisores.Sort();
   return lista_divisores;
}


Segundo método: a partir de los factores primos

El teorema fundamental de la aritmética (también conocido como teorema de la factorización única) nos dice que todo número puede ser representado mediante el producto de una serie de factores primos. A la operación de obtener los factores primos de un número se le llama factorización, y ya le dedicamos otro artículo hace algún tiempo.

Un número primo es aquel que sólo tiene dos divisores: el 1 y él mismo. Todo número natural o es primo o puede ser representado como producto de factores primos (en cuyo caso decimos que es compuesto).

Por ejemplo, el 300 es un número compuesto que se puede representar como el producto de cinco factores primos: 2·2·3·5·5.

Así pues, si contamos con la descomposición en factores primos de un número podemos obtener la lista de todos sus divisores. Cada uno de los factores primos será un divisor. En el caso del 300, el 2, el 3 y el 5 son divisores, pero también lo será el producto de dos de ellos cualesquiera, y también el producto de tres y de cuatro, y el de los cinco, que nos dará 300.

Si encontramos un método ingenioso de hacer todas los productos distintos de dos elementos y de tres y de cuatro y de todos sin repetirnos iremos encontrando todos los factores.

Este método es el siguiente: Tomamos la lista de factores primos ordenados de un número (la llamaremos LP), y por otro lado la lista de divisores, inicialmente vacía (la llamaremos LD), que intentaremos rellenar.

Metemos un 1 en ld y recorremos la lista LP de principio a fin. Para cada elemento x de LP hacemos lo siguiente:


  • Si estamos en el primer elemento de LP multiplicamos cada elemento de LP por x -solo habrá un elemento en LP- y lo añadimos a la lista LD -realmente, estamos añadiendo x a LD-.
  • Si estamos en el segundo elemento de LP o superior y es distinto del elemento anterior de LP también multiplicamos cada elemento que haya en LD por x y lo añadimos a la lista LD.
  • Si estamos en el segundo elemento de LP o superior y es igual al elemento anterior de LP también multiplicamos los elementos de LD añadidos en la iteración anterior por x y lo añadimos a la lista LD.

Eso es todo. Vamos a hacer una prueba. A ver si encontramos los divisores del 300 a partir de su descomposición.

Vamos por pasos

LP=2 2 3 5 5
LD=1

Cogemos el primer elemento de LP x=2. Como es el primero, multiplicamos cada elemento de LD por x (es decir, por 2) y los añadimos a la lista.

LP=2 2 3 5 5
LD=1 2

Está marcado en rojo el elemento que estamos contemplando al recorrer LP, y el azul los añadidos en esta iteración a la lista LD.

Pasamos al siguiente. x=2. Como es igual que el anterior, multiplicamos por x (por 2) sólo los añadidos en la iteración anterior, y los añadimos también a LD.

LP=2 2 3 5 5
LD=1 2 4

Pasamos al siguiente. x=3. Como es distinto del anterior, multiplicamos por x (por 3) todos los de LD, y los añadimos también a LD.

LP=2 2 3 5 5
LD=1 2 4 3 6 12

Pasamos al siguiente. x=5. Como es distinto del anterior, multiplicamos por x (por 5) todos los de LD, y los añadimos también a LD.

LP=2 2 3 5 5
LD=1 2 4 3 6 12 5 10 20 15 30 60

Por último, pasamos al siguiente. x=5. Como es igual que el anterior, multiplicamos por x (por 5) los elementos de LD añadidos en la iteración anterior, y los añadimos también a LD.

LP=2 2 3 5 5
LD=1 2 4 3 6 12 5 10 20 15 30 60 25 50 100 75 150 300

Ya está. Tenemos en LD todos los divisores de 300. Si queremos tenerlos en orden, sólo necesitamos ordenarlos:

LD=1 2 3 4 5 6 12 10 15 20 25 30 50 60 75 100 150 300

Son 18 en total. Podríamos haberlo sabido a priori mediante una curiosa regla: La descomposición de 300 es 2·2·3·5·5, que podíamos haber expresado como 22·31·52. Cojamos sólo los exponentes: 2, 1 y 2... sumemos uno a cada uno: 3, 2 y 3, y ahora multipliquémoslos: 3·2·3=18. Curioso ¿verdad?... cosas de la combinatoria.

El caso es que ya tenemos otro algoritmo para hallar los divisores de un número... pero esta vez no partimos de ese número, sino de su descomposición en factores primos.

C#
List<long> DivisoresDeFactores(List<long> lfp)
{
   //El parámetro de entrada lfp es la lista de factores primos
 
   //la lista de divisores
   List<long> lista_divisores = new List<long>();
   //Inicialmente, solo el 1.
   lista_divisores.Add(1);
 
   //almacenaremos la posición siguiente a la de la última iteración
   int ultima_posicion = 0;
   //el factor de la iteración anterior, para comparar.
   long ultimo_factor=1;
 
   foreach (long factor in lfp)
   {
      //empezamos por el principio si el factor es distinto de
      //la iteración anterior, o por la posición de la última
      //iteración si no es así.
      int posicion_inicial=(ultimo_factor!=factor)?0:ultima_posicion;
      //nos quedamos uno antes que este.
      ultima_posicion = lista_divisores.Count();
      //dejamos preparado cuál es éste factor para la vuelta
      //siguiente
      ultimo_factor = factor;
 
      //iteramos por la lista de divisores multiplicando
      //por el factor y añadiendo.
      for (int j = posicion_inicial ; j < ultima_posicion; j++)
      {
         lista_divisores.Add(lista_divisores[j] * factor);
      };
   }
//Un poco de orden antes de salir
lista_divisores.Sort();
return lista_divisores;
}


Otras cosillas curiosas y vistosas sobre números naturales y sus divisores.

LA FUNCION DIVISOR y otras yerbas similares

Se define la función divisor de un entero n σx(n) como la suma de las x-ésimas potencias de los divisores positivos de n. Se representa con la letra griega sigma minúscula (σ).
Image

De éste modo, σ0(n) nos devuelve el número de divisores de de n, y σ1(n) nos devuelve la suma de todos los divisores.

Por ejemplo, σ0(6)=10+20+30+60=1+1+1+1=4; σ1(6)=11+21+31+61=1+2+3+6=12

Cuando x es 1, a menudo se omite el subíndice, así que se interpreta que σ(n)=σ1(n).

A veces se usa también la notación d(n) o τ(n) para referirse a σ0(n). (τ es la letra tau del alfabeto griego).

La función de suma alícuota de los divisores de n, que se suele denotar como s(n) es la suma de todos los divisores propios, es decir, todos los divisores excepto el propio número n. Así pues, s(n) = σ(n)-n.

A partir de la lista de divisores generada por alguno de los algoritmos comentados hasta ahora, podemos hallar τ(n), s(n), σ(n) y en general, σx(n) con algunos métodos sencillos en C#. Nótese que no aceptan un número entero n como parámetro, sino directamente la lista de divisores ordenada, tal como la devuelven los métodos DivisoresProbando o DivisoresDeFactores de la sección anterior.

C#
static long FuncionSigma(List<long> ld, int x)
{
   long resultado;
   //si x es 0, mejor contamos en lugar de hacer potencias
   if (x == 0)
   {
      resultado = ld.Count();
   }
   else
   {
      resultado = 0;
      foreach (long divisor in ld)
      {
         long sumando = divisor;
         //si x>2 vamos calculando la potencia
         //del sumando
         for (int i = 2; i <= x; i++)
         {
            sumando *= divisor;
         }
         resultado += sumando;
      } //foreach
   } //else
return resultado;
}
 
//-------------------------------------------------
 
//sobrecarga de la función sigma. Si no se pone el
//segundo parámetro, se interpreta un 1.
static long FuncionSigma(List<long> ld)
{
    return FuncionSigma(ld,1);
}
 
//-------------------------------------------------
 
//La funcion tau cuenta los divisores
static long FuncionTau(List<long> ld)
{
   return FuncionSigma(ld, 0);
}
 
//-------------------------------------------------
 
//La funcion suma alícuota devuelve la suma de todos
//menos de n. n está el último de la lista.
 
static long FuncionSumaAlicuota(List<long> ld)
{
    return FuncionSigma(ld, 1)-ld[ld.Count()-1];
}


NÚMEROS DEFICIENTES, PERFECTOS Y ABUNDANTES... o de cómo poner apellidos a los números según su divisibilidad.

Se atribuye al matemático del siglo I, Nicómaco de Gerasa estas curiosas clasificaciones de los números naturares.

Se dice que un entero n es

  • deficiente si s(n) <n
  • perfecto si s(n)=n
  • abundante si s(n)>n

s(n) denota la suma alícuota de los divisores de n. Es decir, la suma de los divisores excluido n.

C#
enum Perfeccion { deficiente, perfecto, abundante };
 
static Perfeccion ObtenerPerfección(List<long> ld)
{
   long n = ld[ld.Count() - 1];
   long sa = FuncionSumaAlicuota(ld);
   Perfeccion resultado;
   if (sa > n)
   {
      resultado = Perfeccion.abundante;
   }
   else if (sa < n)
   {
      resultado = Perfeccion.deficiente;
   }
   else
   {
      resultado = Perfeccion.perfecto;
   };
   return resultado;
}


Sorprendente ¿verdad? Pues aún hay mucho más: fíjate en éste enlace de la wikipedia(external link) -en inglés-, especialmente en la barra de navegación que aparece a la derecha.... hay números amigos, colosalmente abundantes, sociables, quasiperfectos, extraños, extravagantes...

...¿Y para que vale todo esto?...

Nunca se sabe ;-)


Ultima edición por vic .
Página última modificacion en Miércoles 22 de Agosto, 2012 12:15:40 CEST.



¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)

Este sitio web usa cookies para su funcionamiento. Navegar por éste sitio supone la aceptación de la política de cookies -
Política de cookies +