Proyecto Euler.

En adelante voy a publicar, de una manera nada regular, seguramente, soluciones a problemas extraídos de Project Euler . Se trata de un sitio en el que se pueden encontrar interesantísimos problemas, habitualmente de carácter matemático, para resolver mediante algún lenguaje de programación.

En esta ocasión se trata del problema número 63:

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

Para abordar este problema es conveniente hacer previamente un pequeño análisis matemático.

Si hablamos de números de n dígitos, entonces estamos en el intervalo que va de { 10 }^{ n-1 }\quad a\quad { 10 }^{ n }, excluyendo el extremo superior, ya que, como es obvio,  { 10 }^{ n } tiene n+1 cifras. Así que tenemos que sacr información de la siguiente inecuación: { 10 }^{ n-1 }\le { x }^{ n }<\quad { 10 }^{ n }.

Lo anterior nos lleva a   { 10 }^{ \frac { n-1 }{ n }  }\le { x }\le \quad 9, sin más que tomar raíces. Ahora fijémonos en la siguiente imagen:

funcioncifras

Se trata de la gráfica de la función f(x) = 10^((n-1)/n) que, como veis, es estrictamente creciente y cuando n vale 22 toma un valor superior a 9, lo cual nos permite restringirnos a exponentes que van de 1 a 21.

El programa en Python para implementar todo esto es bien sencillo. Lo copio aquí:

cont = 0
# Un bucle para el exponente: de 1 a 21.
for n in range(1,22):
#Para cada exponente un bucle entre los valores permitidos.
for j in range(int(10**(1-1/n)+1),10):
print (j,n,j**n)
cont +=1

print (“El número de cifras es: “,cont)

Aquí os dejo el enlace: https://repl.it/HxAr/7

Si ejecutáis el programa obtenéis:

2 1 2
3 1 3
4 1 4
5 1 5
6 1 6
7 1 7
8 1 8
9 1 9
4 2 16
5 2 25
6 2 36
7 2 49
8 2 64
9 2 81
5 3 125
6 3 216
7 3 343
8 3 512
9 3 729
6 4 1296
7 4 2401
8 4 4096
9 4 6561
7 5 16807
8 5 32768
9 5 59049
7 6 117649
8 6 262144
9 6 531441
8 7 2097152
9 7 4782969
8 8 16777216
9 8 43046721
8 9 134217728
9 9 387420489
8 10 1073741824
9 10 3486784401
9 11 31381059609
9 12 282429536481
9 13 2541865828329
9 14 22876792454961
9 15 205891132094649
9 16 1853020188851841
9 17 16677181699666569
9 18 150094635296999121
9 19 1350851717672992089
9 20 12157665459056928801
9 21 109418989131512359209
El número de cifras es: 48
___________________________________________________________________________
Se entiende que, por ejemplo, la última fila hay que leerla así:
9^21 = 109418989131512359209

Nota: En realidad, la solución correcta es 49, ya que
el programa anterior no incluye 1^1=1!!!!
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s