Skip to main content

Problem 12 Project Euler Solution with python

Update: I have tried breaking numbers method but it is not as efficient as the program which we have written. It is useful when you will use it for finding divisors of a number.

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

 To solve this problem we will be using a code snippet from Problem 3 which we have solved earlier. I will first share with you the code snippet and the concept behind our program solution so that it will be easy for you to decode the code.

#A dictionary to store the powers of primes
dic = {}
#Starting with a prime number 2
i = 2
#for loop to factor a number
while i <= triangle_number:
 #If 'i' divides the number, then it is a
 #prime factor 
 if triangle_number % i == 0:
  #Changing the value of number so that
  #we will not divide it with the same
  #number again and again
  triangle_number = triangle_number/i
  #We are storing the value in terms 
  #of power of the prime number in dict
  if i in dic:
   dic[i] += 1
  else:
   dic[i] = 1
  i = i-1
 i += 1
The above factorization technique is based on Method 2 atHow to Factor a number .
The code is well commented again.

 Now to understand the program which we have written to solve problem 12, you will have to give a quick glance through these links:
  1. How many divisors does 138600 have?
  2. How to determine number of divisors of an integer
  3. 1+2+3+4+.. Wiki
  4. Python Multiply all items in a list together
  5. Efficient method to check if key exists in dictionary
That's it you are done. You are ready for takeoff 😋.

Program

Program is a follows:
 
The code is well commented again and I don't think it requires explanation. I suggest you to check out the links if you haven't yet.

 I just want to share one thing. Instead of using dic in the code you could append all the divisors to a list and then find each instance of the prime number in the list. To accomplish this you will need sets in python. I have given you one hint, now try to write the program. It will be fun.

If you want to download the program you can do it from Github Gist

Output


Summary

This problem was not really challenging, but it required a very good algorithm. As we have already solved problem 3 our program became more simple. But it had execution time greater than 1second, which I was not satisfied. But I was not able to think of another solution. I know that we are looping a lot of times but I couldn't come up with a better solution. But I promise you that if I will find a better solution then I will for sure post it.

 I found a solution but I am not sure if it will work faster than the above code. If you have a better solution then please do share it with me.

 If you haven't understood anything in this post then please do comment in the comment box below and I will be glad to help you.

 Please do comment in the comment box if you have found any typo or want me to add anything to improve this post.

 You can also contact me if you want to.

 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