Skip to main content

Problem 58 Project Euler Solution with python

Spiral primes

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

You can call this problem a continuation to the Problem 28. I simply have modified the problem 28 project euler Solution with python and have used to solve this problem.

 Please have a look at the solution which I have written earlier for problem 28 to understand this solution.

The algorithm is as follows:

1) Write a function to test if the given number is prime.

2) Generate all the diagonal numbers in the spiral, For each and every new layer check if the ratio of length of prime numbers to the length of all numbers is less than 10%.

3) If the length is less than 10%, break the loop and print the square root of the last number. Otherwise continue the next iteration with step1.

We are using the square root of the number as the solution because, it will be the side length of the layer.

That's it. Please make sure you have read the solution for problem 28, otherwise this solution will be somewhat tricky for you to understand.

Program

is_prime function
In this function I am not checking for any even number divisibility because, only odd numbers are generated along the diagonals.

ratio = 1
At the start of the program I am assuming that the ratio will be 100%. First reason is that the while loop will not run if we are not assuming so and the second reason, after the first iteration the value of the ratio will change to the practical real value.

present_number = 2*i+1
We know that from the program, i value generated indicates the ith odd number. So we don't need i but we need odd number. From Odd number-Wolfram, odd number will be 2*i+1. 

Remaining all are simple. I am assuming that you can understand them easily. 

As always you can download the source code from github gist 58.py

Output

Summary

As you can see, the execution time is more for this problem. The reason is that, I have used an inefficient Primality testing function. This seriously increased the execution time. I could have optimized the code by using an efficient Primality algorithm but I have left it for you. You can make some small changes and see the effect. But I am satisfied with the program which I have written. I personally liked this problem.

Please correct me and excuse me, if my grammar is wrong or in an ambiguous way. 

Comment in the comment box below, if you have any doubt or haven't understood anything. I will be glad to help you.

Please do comment in the comment box below, if you have found any typo or have a better or different program or have a suggestion. I will be glad to view each of them.

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