Skip to main content

Project Euler Problem 63 solution with python

Powerful digit counts

The 5-digit number, $16807=7^5$, is also a fifth power. Similarly, the 9-digit number, $134217728=8^9$, is a ninth power. How many n-digit positive integers exist which are also an nth power?

This problem is very simple. Just a bit of rough paper scratching will give you the answer.

Let us consider a single digit number - 9. Few powers of the number are as follows:
$9^1 = 9$
$9^2 = 81$
$ 9^3 = 729$..
If you have observed, the power of these numbers correspond to the length of the number.

If you consider any two digit numbers, then
$10^1 = 10$
$10^2 = 100$
$10^3 = 1000$..
As you can see, the length of the number is more than the power, so no two digit numbers will satisfy your answer.

In a similar way, at no point does three, four, five etc. digit numbers satisfy the condition. So we only are left with the two digit numbers. Even in two digit numbers, there should be some point of deflection. Lets consider the number 2 $2^1 = 2$
$2^2 = 4$
So far so good, but further on, we will observe that the the power of the number will out weigh the length of the value. $2^3 = 8$
In similar way at some point each of the single digit numbers will not be able to handle this condition and will give up. After that point the condition will never be satisfied. We will stop there and continue with the next number. Have a look at the program and you will understand everything clearly.

Program

In [ ]:
# http://radiusofcircle.blogspot.com

# import time module
import time

# time at the start of program execution
start =  time.time()

# counter to count the number of instances
counter = 0

# for loop to loop from 1 to 9
for i in xrange(1, 10):
    power = 1
    while True:
        if power == len(str(i ** power)):
            counter += 1
        else:
            break
        power += 1

# print the number of instances found
print counter

# time at the end of program execution
end = time.time()

# total time taken for the program execution
print end - start

I don't think there is anything more to explain because I have already explained everything in the algorithm part. The program is just an implementation.

If you want you can download this program from Github gist pep63.py

Output

Summary

This problem was an easy one. It only took a few minutes for me to get to the solution. As we are not doing any extra loops I think that this one will be the perfect solution(may be). But I am really satisfied with the output and the execution time.

If you have any doube or didn't understand anything, comment in the comment box below and I will be glad to help you.

If you have any feedback or suggestions, you are welcome. If you have found any typo or have a different or better program comment in the comment box below. I will be very happy to see your comment.

You can also contact me.

Thank you. Have a nice day😃.

Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more