Problem 26 Project Euler Solution with python

Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

¹/₂ = 0.5

¹/₃ = 0.(3)

¹/₄ = 0.25

¹/₅ = 0.2

¹/₆ = 0.1(6)

¹/₇ = 0.(142857)

¹/₈ = 0.125

¹/₉ = 0.(1)

¹/₁₀ = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.
Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

First of all I am sorry for not posting these many days. Firstly I was not able to concentrate on posting the solution because I had some other important work. Secondly as I was not really paying attention I was not able to find the solution for this problem. I was completely lost in a wrong way to solve this problem. I was thinking that I should use python decimal module to solve this problem but my assumption was wrong and I had to come all the way back and start from scratch. I started yesterday and today I present you the solution.

This post will be somewhat big because I will neatly explain each and every concept behind the scenes so that you will understand it perfectly. If you are good at directly understanding the code without reading any algorithm, then you are welcome. The code is well commented to encourage people like you. If you are going to read through this whole post, firstly be patient as I will explain even elementary methods(Skip them if you already know). Secondly stay with me and you will leave this page with lots and lots of new concepts learned and with flying colors.

Okay lets get started.

Long Divison

This is not a new concept for you, but I would just like to give you a brush up on this topic. Let us understand this concept with a few examples. Take 10/3, 100/13,1000/101.
You should have observed a pattern in the above selected numbers.

All the denominators are prime numbers.
All the numerators are multiples of 10.

I will explain it to you why.

To get a whole number as a quotient after division then the number should be greater than or equal to the number in the denominator. We are considering multiples of 10.

I have chosen prime numbers especially because they show this repeating decimal characteristics(Except 5 and 2).

Now see how I am doing the division, you should simply understand it directly seeing the image.

10 divided by 3

In the above image, as we all know that 3 times 3 is 9, after dividing it with 10 were are left with 1 as remainder. Now as you can see, if we multiply the remainder with 10 then we again arrive at the same number 10 with which we have started so now we can terminate our division and say that when 10 is divided by 3 then 3 is the repeating cycle. This is not completely true, but for your explanation I have made it simple for you. Read on to understand the perfect answer.

Now see the image 100/13:

100 divided by 13

Now in the first block we have successfully divided 100, multiplying 13-7 times. The remainder will be 9, as 9 is less than 10 we will have to multiply it by 10 to make it divisible by 13, so we will add a decimal to the number. This is also true in the case 10/3, but we have not seen this step because even though we will add the decimal, the recurring number is still 3 as there cannot be more than one decimal points. Coming back, we use 13x6 to divide 90 and the remainder is 12, which is again less than 13 so multiply it by 10 because we have already added the decimal. Next one will be 3, so multiply by 10 and we get 4 as remainder. Multiply 4 by 10 to get 40 which is more than 13 and divide it by 13 and you get 1 as the remainder. As 1 is less than 10 then we get 10 which when multiplied by 10 we get 100 and so we have again reached the starting point and the algorithm terminates.

But the repeating cycle is not just 769, it is '7690', because at the end of the algorithm we had 10, but to get 100 we need to multiply with 10 to get 100. Adding another decimal is not the solution, so simply add 0 to get 100. See 1000/101 to further understand the addition of zero after decimal.

1000 divided by 101

Now see this example to get a clear cut idea of long division for reciprocal cycles. When we started with 1000, we used 101 times 9 to get 909 and the remainder was 91. As 91 was less than 101 we added a decimal and then got it multiplied by 10 which gave us 910. Divide it again by 909 to get 1. As we have a decimal we multiply it by 10 to get 10. Now we need another 100(10x10) to prove that we have come to the starting point and we can eliminate the algorithm. To get first 10 I will add a 0 to the quotient and so I can multiply it by 10. So now my remainder is 100 and thus the algorithm terminates.

Finally as discussed in the previous example, my recurring cycle is not just 990 but 9900, as we are multiplying it with 10 to get 1000(100x10).

Hope you have understood this. If you have understood this properly then you have understood almost the underlying algorithm of the program.

Prime Sieve(Sieve of Eratosthenes)

I have used the same code from Problem 7 Project Euler Solution with python. Of course there are many other places where you can learn about this concept. You can visit Wikipedia- Sieve of Eratosthenes, Geeks of Geeks - Sieve of Eratosthenes.

Greatest Common Divisor of two numbers

As the name suggests, if we consider two numbers the largest number that can divide both the numbers evenly is called as greatest common divisor of that two numbers or GCD in short. For example consider two numbers 6,12, the largest number which can divide both the numbers is 6.

The best way to find GCD of two numbers is to make use of Euclid Algorithm. To learn more you can visit: How to Find the Greatest Common Divisor of two numbers - Wikihow.

Least Common Multiple of two numbers

Least common multiple also called as LCM is the smallest number that is a multiple of both the numbers. For example consider 6 and 12, the smallest number which is a multiple of both of them is 12. If you want to know more about LCM then you can visit: How to find the Least Common multiple of two numbers - Wikihow. For our program I have used the code snippet from Problem 5 Project Euler Solution with python.

the last part....

Properties of Repeating decimals

Consider a number 'n', the maximum number of repeating decimals it can have is 'n-1'.

If a number say 'n' is co-prime to 10(not divisible by either 2 or 5 or both 2 and 5), and the number 'n' can be written as n = axb, then the length of repeating decimals is equal to the LCM of number of repeating decimals of a,b.

This can be written mathematically as:

number of repeating decimals of a = x(say)

number of repeating decimals of b = y(say)

number of repeating decimals of n(axb) = LCM(x,y)

This is where we will use the LCM which we have found out in the previous section.

If number say 'n' is not co-prime to 10(divisible by either 2 or 5 or both 2 and 5), and the number after prime factorization can be written as n = 2^a5^bp^cq^d , where p, q are prime numbers and a,b,c,d are the powers of the 2, 3, p, q respectively, then number of repeating decimals of n is equal to the number of repeating decimals of p^cq^d.

For example consider 28 which can be written as 2²x7¹, then the number of repeating decimals of 28 is 6(repeating decimals of 7). to be for this kind of numbers, take the number and divide it until it not divisible by 2, divide it by 5 until it is not divisible by 5 and the length of the repeating numbers of the remaining number is the length of repeating number of the given number.

From the above paragraph(s), you can see that if we find the length of the repeating decimals of the prime numbers then we can use the same for finding the length of the upcoming composite numbers.

One final thing to remember is that the last two properties explained above are not valid for numbers 2 and 5😛.

Finally we have seen all the underlying concepts of the program. Let's see the program.

Program

Like the algorithm the program also looks big, but it is very easy.

File: pep26.py ------------------------- #http://radiusofcircle.blogspot.com #time module for calculating execution time import time #time at the start of execution start = time.time() #long division as explained #https://www.mathsisfun.com/long_division.html def recurring_decimal(divisor): if divisor <10: divident = 10 elif divisor >=10 and divisor <100: divident = 100 else: divident = 1000 value_to_check = divident #10 or 100 or 1000 string = '' for i in xrange(divisor): string += str(divident/divisor) divident = divident%divisor if divident < divisor:#adding decimal divident *= 10 if divident < divisor:#adding zero after decimal divident *= 10 string += '0' if divident < divisor:#adding another decimal after 0 divident *= 10 string += '0' if divident == value_to_check: return string #sieve of Eratosthenes #https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): is_prime = [True]*n is_prime[0] = False is_prime[1] = False for i in xrange(2,int(n**0.5+1)): index = i*2 while index < n: is_prime[index] = False index = index+i prime = [] for i in xrange(n): if is_prime[i] == True: prime.append(i) return prime #We have used euclid Algorithm to find the #lcm also called smallest multiple #gcd function for calculating lcm def gcd(n1,n2): remainder = 1 while remainder != 0: remainder = n1%n2 n1 = n2 n2 = remainder return n1 #lcm of two numbers using euclid Algorithm #lcm = (number1*number2)/GCD(number1,number2) def lcm(n1,n2): return (n1*n2)/gcd(n1,n2) #generating the primes primes = sieve(1000) #assuming all the numbers have no repetition d = {n: 0 for n in range(1,1000)} #Adding the value for 1/3 d[3] = 1 #generating the length of repeating decimals #for prime numbers excluding 2, 3 and 5 for i in primes[3:]: d[i] = len(recurring_decimal(i)) #looping for numbers greater than 5 #using the properties of repeating decimals; #https://en.wikipedia.org/wiki/Repeating_decimal for i in xrange(6,1000): if not d[i]: if i % 2!= 0 and i%5!= 0: #number coprime to 10 for j in primes: if i%j == 0: number1 = d[j] number2 = d[i/j] d[i] = lcm(number2,number1) break else: #number not coprime to 10 number = i while number%2 == 0: number = number/2 while number%5 == 0: number = number/5 d[i] = d[number] #printing the largest value #as the index starts from 0, adding 1 ;) print d.values().index(max(d.values()))+1 #time at the end of execution stop = time.time() #printing the total time for execution print stop- start

I think you might have confused with the for loop used in Line 79 and Line 85. I will explain it to you.

We know that, when we call sieve(1000), we will get a list like [2,3,5,7,11,13......], but if you remember the long division algorithm which we framed will return None when the number will evenly divide the numerator(if there is no repeating decimal). So we can say that out of all the prime numbers 2,5 will return None. But we just want 0 which means that there is no repeating decimals. Adding an if else statement to check this is inefficient because all the prime numbers except 2 and 5 will return some value. So what I simply did was to start my loop from 7 or primes[3:] and manually added the value for 3.

In a similar way in Line 85 the numbers which we have left are 1,2,3,4,5. While 1, 2, 4, 5 will divide 1 evenly and we have already added the value for 3 in the previous for loop, so there was no need for extra looping, wasting the resources.

If you want you can download the source code from Github Gist pep26.py

Output

Summary

This problem took around 1 day for me to solve and post. But framing the algorithm took few days, because I was searching for Diamonds when I had to search for gold. When I realized that I had to find gold which I have already seen somewhere when I was searching for diamonds it became easy for me. No problem being lost in a wrong way had given me some benefits like, I came to know about the suffix trees, the python decimal module and some regular expressions. This may be helpful for me in the future.

As always if you have any doubt or didn't understand anything then comment in the comment box below and I will be glad to help you.

Also please don't hesitate to comment if you have any suggestions, or have a better program, then please do share it with the community.

You can also contact me.

Thank you. Have a nice day😄.

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

RADIUS OF CIRCLE

Search This Blog