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 a0
y 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.
long long
puede almacenar enteros hasta 18.446.744.073.709.551.615, de verdad que no es suficiente?