2

Necesito hacer un programa que consiste en un numero N como caso de entrada y elevar 6 a la 0, a la 1, a la 2... hasta llegar a N. Para cada caso en el que el numero se eleve debo hallar los divisores, el problema que tengo es que al elevar el 6 a N y N sea un numero muy grande el numero que obtendre no se podra almacenar en ningun tipo de dato, solo en string pero, ¿Como hago las respectivas operaciones con string en este caso?

Un ejemplo seria:

Input: 3.

Output: 1, 4, 9, 14.

Obtenemos el 1 del numero de divisores de 6^0. Obtenemos el 4 del numero de divisores de 6^1. Obtenemos el 9 del numero de divisores de 6^2. Obtenemos el 14 del numero de divisores de 6^3.

Mi codigo es el siguiente:

#include<iostream>
#include <math.h>
using namespace std;

int main(){
    int nVeces;
    cin>>nVeces;
    int pot=0;

    int n;
    while(nVeces>=0){
    int divisores=0;
    n=1;    
    int nElevado = pow (6,pot);
    for(n; n<=nElevado ;n++){
        if(nElevado%n==0){
            divisores++;    
            }
        }
        cout<<divisores<<endl;
    pot++;
    nVeces--;
    }
}
4
  • 1
    El tipo long long puede almacenar enteros hasta 18.446.744.073.709.551.615, de verdad que no es suficiente? Commented el 2 nov. 2019 a las 11:01
  • ¿En tu ejemplo dices que 4 es divisor de 6? No entiendo bien a qué estás llamando divisores. ¿Podrías aclarar un poco más el asunto? Commented el 2 nov. 2019 a las 14:29
  • @RogerTorné, no es lo suficiente debido a que el 6 podira estar elevado a 100. Eso superaria el unsigned long long Commented el 2 nov. 2019 a las 15:57
  • @MauricioContreras, no 4 no es divisor de 6, 4 seria el numero de divisores que tiene 6 elevado a la 1 Commented el 2 nov. 2019 a las 15:58

1 respuesta 1

4

No necesitas calcular el valor de 6^N, ya que es un gasto inútil de recursos.

Muchos ejercicios requieren más matemática que códigos o algoritmos.

La solución parte de encontrar un patrón el momento de calcular los valores que son divisores de la potencia de 6.

Veamos un ejemplo en JavaScript ya que podemos usarlo aquí como código ejecutable:

La idea es calcular los valores de las potencias de 6 y buscar una relación en la cantidad de divisores de acuerdo a la potencia calculada, usaré un bucle for para calcular las primeras 10 potencias de 6 (de 0 a 9) y veremos el resultado en pantalla de la cantidad de divisores de dichas potencias. Para ello, me basaré en tu algoritmo.

Aunque tienes un error dado que la cantidad de divisores de 6^N cuando N=3, es 16 y no 14 como lo pones en tu pregunta.

// esta variable almacenará la cantidad de divisores de la iteración previa
let prev = 0;

// calculamos las primeras 10 potencias
for(let j = 0; j < 10; j++) {
  let power = 6**j;
  //variable para contar los divisores
  let count = 0;
  // comprobamos desde 1 hasta power cada número
  // si el número divide a power aumentamos count
  for(let i = 1; i <= power; i++) {
    if(power % i === 0) {
      count++;
    }
  }
  // mostramos los resultados
  console.log(`N: ${j}, divisores: ${count}, diferencia: ${count - prev}`);
  //guardamos la cuenta previa para la siguiente iteración
  prev = count;
}
.as-console-wrapper { max-height: 100% !important; top: 0; }

Como puedes observar, de acuerdo al incremento de N, la cantidad de divisores de la potencia 6^N crece de una forma que podemos calcular. Es una progresión aritmética, y debemos obtener su fórmula.

Realmente es una fórmula simple, dado que es la suma de todos los impares entre 1 y 2N+1.

Existe una fórmula para calcular la suma de todos los elementos consecutivos de una progresión:

S = ((a1 + an)*n)/2

En este caso, tenemos que empezar en a0 = 1 ; an = 2N+1 y n = N + 1 (recordemos que empezamos en 0).

Por lo tanto la fórmula se puede escribir así:

S = ((a0 + ((2*N)+1))*(N+1))/2
=> S = (((2*N) + 2)*(N+1))/2
=> S = ((2*(N+1))*(N+1))/2
=> S = (N+1)*(N+1)
=> S = (N+1)^2

Y así podemos calcular la cantidad de divisores de 6^N que existen entre 1 y 6^N, sin necesidad de calcular 6^N.

Probemos el cálculo:

// esta variable almacenará la cantidad de divisores de la iteración previa
let prev = 0;

// calculamos las primeras 10 potencias
for(let j = 0; j < 10; j++) {
  let power = 6**j;
  //variable para contar los divisores
  let count = 0;
  // comprobamos desde 1 hasta power cada número
  // si el número divide a power aumentamos count
  for(let i = 1; i <= power; i++) {
    if(power % i === 0) {
      count++;
    }
  }
  // mostramos los resultados
  console.log(`N: ${j}, divisores: ${count}, diferencia: ${count - prev}`);
  //guardamos la cuenta previa para la siguiente iteración
  prev = count;
  
  // usamos la fórmula para contrastar:
  let cantDivisors = (j + 1)**2;
  console.log(`Divisores calculados con la fórmula: ${cantDivisors}`);
}
.as-console-wrapper { max-height: 100% !important; top: 0; }

Ahora, en una sola línea de código, usando una fórmula matemática para progresión aritmética se resuelve el problema que presentabas, y calcular la cantidad de divisores de números tan grandes como 6^100 se reduce a calcular 101^2, lo cual es fácilmente manejable por un tipo long.

¿Cómo se escribe en C++?

Sencillo, es una sola línea la que debemos escribir:

#include<iostream>
#include <math.h>
using namespace std;
int main(){
    long nVeces;
    long i;
    cout<<"Ingrese N:"<<endl;
    cin>>nVeces;
    for(i=0;i<=nVeces;i++) {
      //esta es la única línea
      long divisores=pow(i+1, 2);
      cout<<"Divisores para 6^"<<i<<": "<<divisores<<endl;
    }
}

Espero que la respuesta te sea de ayuda.

tl;dr

EXPLICACIÓN

Como bien mencionas en tu comentario, la sucesión de los valores obtenidos (cantidad de divisores de 6^N) es una sucesión cuadrática.

Una Sucesión Matemática es simplemente una aplicación de N en X, donde a cada natural n le corresponde un único elemento an de la sucesión.

Una Sucesión Cuadrática es un caso particular de Sucesión.

Si calculamos la diferencia entre los elementos de una sucesión puede que la misma sea constante, cuando esto sucede, decimos que la Sucesión es una Progresión Aritmética

Pero si la diferencia no es constante, podemos calcular la diferencia entre estas primeras diferencias y si la misma es constante, estamos ante una Sucesión de Segundo Orden o Segundo Grado, también conocida como Sucesión Cuadrática.

Vamos a observar una tabla con los valores de N, los valores de la cantidad de divisores de 6^N, la diferencia entre estos valores, y la diferencia entre las diferencias. Lo haremos para N=9, empezando desde 0.

| N | Nro. Divisores de 6^N | Primera Diferencia | Segunda Diferencia |
|---|-----------------------|--------------------|--------------------|
| 0 |          1            |          1         |          -         |
| 1 |          4            |          3         |          2         |
| 2 |          9            |          5         |          2         |
| 3 |         16            |          7         |          2         |
| 4 |         25            |          9         |          2         |
| 5 |         36            |         11         |          2         |
| 6 |         49            |         13         |          2         |
| 7 |         64            |         15         |          2         |
| 8 |         81            |         17         |          2         |
| 9 |        100            |         19         |          2         |

Claramente se observa que los valores de la segunda diferencia son constantes, por lo tanto la sucesión formada por:

[1, 4, 9, 16, 25, 36, ...]

es una Sucesión de segundo grado o cuadrática.

Primeras diferencias

En mi respuesta, dije:

es la suma de todos los impares entre 1 y 2N+1

Y es que me refería a los valores de la sucesión calculados a partir de la primera diferencia.

El valor de an (número de divisores de 6^N) viene dado por la suma de los impares desde 1 hasta 2N+1

Lo podemos apreciar en la tabla anterior, por ejemplo, para el caso N=3, tenemos que los impares entre 1 y 2N+1 son:

[1, 3, 5, 7]

Dado que 2N+1 = 7 cuando N = 3

Si sumamos estos números el resultado es 16, que se corresponde con el número de divisores de 6^N en dicha tabla.

De esa forma realicé los cálculos para hallar la suma de los elementos entre a0 y an.

Entre a0y an hay exactamente n+1 elementos.

Por lo tanto es el valor n+1 el que voy a usar para el cálculo de la cantidad de divisores.

La fórmula de la suma de elementos contínuos de una serie viene dada por:

S = ((a1+an)*n)/2

esto es para n elementos.

Pero nosotros estamos calculando n+1 elementos, ya que empezamos en 0 y vamos hasta n.

Por eso la fórmula ha de ser reescrita como:

S = ((a0+an)*(n+1))/2

Esto aclara el porqué usé esta fórmula. Y en este caso uso n = N. Tal vez eso es lo que confunde un poco, ya que en mi respuesta sustituí directamente n por N+1.

El resultado de esta fórmula es:

S = (n+1)^2

Segundas diferencias

Si usamos la regla de las sucesiones cuadráticas:

Xn = an^2 + bn + c

debemos determinar los valores de a, b y c a partir de los valores de las diferencias obtenidas.

Esto es para n elementos de una sucesión, pero nosotros estamos calculando n+1 elementos, por lo tanto sólo debemos hacer la sutitución:

Xn = a(n+1)^2 + b(n+1) + c

Como esto no es un blog de matemáticas ni mucho menos, sólo bosquejaré los pasos necesarios para hallar dichos valores, sin entrar en los detalles de dónde provienen dichos pasos.

Calculo de a

Debemos igualar 2a con el valor de la segunda diferencia (el cual es constante), entonces:

2a = 2 => a = 1

Ya tenemos el valor para a

Calculo de b

Usaremos la siguiente fómula para hallar b:

3a + b = diff_1

donde diff_1 es el valor de la primera diferencia de la sucesión

3a + b = 3 => b = 0

recordemos que el primer par de términos de la sucesión son 1 y 4, cuya diferencia es 3.

Cálculo de c

Para hallar el valor de c debemos usar la fórmula:

a + b + c = 1 => c = 0

el primer término de la sucesión es 1 y la formula es la suma de a, b y c igualada al primer término de la sucesión.

Por lo tanto, la fórmula para Xn viene dada por:

Xn = a(n+1)^2 + b(n+1) + c => 1*(n+1)^2 + 0*(n+1) + 0

=> Xn = (n+1)^2

Como puedes observar el resultado es el mismo que el dado en mi respuesta.

Ya sea que uses un método u otro, los resultados han de coincidir.

Espero que esto aclare aún más tus dudas.

2
  • 1
    Excelente tu respuesta, me quedan algunas dudas. Analizando mejor el problema se puede hacer como la sucesión de los cuadrados que es a lo que llegaste al final de la formula, eso es lo que hiciste. Pero en la formula porque an = 2N+1 y n = N+1? y porque hablas de los impares? Podrias explicarme eso? Commented el 2 nov. 2019 a las 20:15
  • 1
    @FelipeAlferez, acabo de editar mi respuesta con la explicación que pediste, espero que sea lo que buscas. Saludos Commented el 3 nov. 2019 a las 10:48

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.