Project Euler Problem 26 Solution

Reciprocal cycles

Problem 26

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

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	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.

Math Concept:

The fraction of the Prime number P except 2, 5 always produce repeated cycles in fractional part, which are most likely of the factor of P-1 or at most P-1.

According to Fermat's theorem, length of the repeated part is given as follows:
10^n mod P = 1

now, this n can be either P-1 or factor of P-1

All we need to do is start from 1000 downwards looking for prime numbers, which satisfies P-1 length.


NOTE: ELEGANT EXAMPLE OF QUICK SOLUTION IF YOU KNOW MATH :)

def is_prime(n):
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i = i + 1

  return True

def generate_prime_below(n):
  l1 = []

  for i in range(n,1,-1):
    if is_prime(i):
      l1.append(i)

  return l1

for p in generate_prime_below(1000):
  c = 1
  while pow(10,c,p) != 1:
    c = c + 1

  if p-c == 1:
    break

print p 


ANSWER = 983 

Project Euler Problem 25 Solution

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?

ANSWER: 4782

Learning:

#1 Approach: Math concept

Golden Ratio for fibonacci number:

it is n'th fibonacci number, larger the value of n, better is convergence.

we know 1000 digit number is at least, 10^999

we can use the relation that,

F(n) >= 10^999

and solve the equation for n, we get 4782

#2 Approach: standard recursive fibonacci function

#function: find i'th fibonnaci number

def get_fibo(n):

  if n == 1 or n == 0 or n== 2:

    return 1

  return get_fibo(n-1) + get_fibo(n-2)

i = 1

while(1):

  j = get_fibo(i)

  if len(str(j)) == 1000:

    print j

    break

  i = i + 1

NOTE: TAKES HUGE TIME

#3 Stay Tuned to efficient programmable approach :)

Project Euler Problem 24 Solution

Lexicographic permutations

Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Answer: 2783915460

Learning:

Writing an algorithm for Permutations

#1 Recursive Approach:

def get_all_permutations(string):
  if len(string) == 1:
    return [string]

  result = []
  for i, c in enumerate(string):
    for k in get_all_permutations(string[:i] + string[i+1:]):
      result = result + [c + k]

  return result


for i, p in enumerate(get_all_permutations('0123456789')):
  if i+1 == 1000000:
    print p
    break


NOTE: When ran on large numbers,  it takes huge time to complete


 #2 Python API:
import itertools
perms = itertools.permutations('0123456789')

for i, p in enumerate(perms):
  if i+1 == 1000000:
    print ''.join(p)
    break

NOTE: It executes extremely fast, MUST SEE HOW IS IT IMPLEMENTED

Project Euler Problem 15 Solution

Lattice paths

Problem 15

Published on 19 April 2002 at 06:00 pm [Server Time]

Starting in the top left corner of a 22 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 2020 grid?

Solution = 137846528820



Explanation:

Honestly I could not solve it completely, but was on right track as I got the idea of dynamic programming and extra 1 dimension for the total points.

Nevertheless, please follow the link:
http://www.mathblog.dk/project-euler-15/

Very neatly explained!

Following is the Python implementation code:
https://github.com/dkuldeep11/project-euler/blob/master/problem15/p15.py

Factors of The Number vs Prime Factors of The Number

For the given number, num = 100

factors = [1, 100, 2, 50, 4, 25, 5, 20, 10]

prime factors = [2, 2, 5, 5]



Code For Factors:

https://github.com/dkuldeep11/project-euler/blob/master/problem12/get_factors.py




Code For Prime Factors:

https://github.com/dkuldeep11/project-euler/blob/master/problem-3/get_prime_factors.py

Project Euler Problem 13 Solution

Large sum

Problem 13

Published on 22 March 2002 at 06:00 pm [Server Time]

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629

.

.

.

.

.

Solution = 5537376230

Code = https://github.com/dkuldeep11/project-euler/tree/master/problem13

Project Euler Problem 12 Solution

Highly divisible triangular number

Problem 12

Published on 08 March 2002 at 06:00 pm [Server Time]

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?

Solution = 76576500

Code = https://github.com/dkuldeep11/project-euler/tree/master/problem12

Take Away:

1) To Find Factors of the number n:

instead of going with standard way of checking if n is divisible by every number till n, which has O(n) complexity, we can achieve O(n^0.5).

def get_factors(n):
  ans = [1,n]
  i = 2
  k = n

  while True:

    if i>=k:
      break

    if n%i == 0:
      ans.append(i)
      k = n/i
      if k!=i:
        ans.append(k)

    i = i + 1

  return ans


Explanation:

we can exploit the fact of pairs e.g. 4 is factor of 80, but (4*20) = 80, so we do consider 20 also the factor, and set 20 as threshold.
Now, we will go on increasing 4, 5, and so on, but intuitively, the other end will automatically shrink as factors, right?

4 - 20
5 - 16
8 - 10

here, threshold becomes 10,

when we go for 9, it is not a factor, and when go for 10, which is a threshold, we break, so this way we will never cross beyond square root.

Python Challenge Level 6 Solution

Problem = http://www.pythonchallenge.com/pc/def/channel.html

Solution = http://www.pythonchallenge.com/pc/def/oxygen.html
Code = https://github.com/dkuldeep11/python-challenge/tree/master/challenge-6
Explanation ::

1) Extract the file, and read README.txt

2) It says start with 90052

3) Read the file and you get the new id, and so on...

4) Automate the above process in Python so that you get the final file in which there is no ID but the answer text

5) You get the answer as: "Collect the comments."

6) This was completely new thing for me to learn. Actually it is about the ZIP concept. Whenever we make a ZIP archive, lot of information is associated with every member of archive e.g. original_size, compress_size, date, comment, etc.

7) So what "Collect the comments." means is we are supposed to extract the comment part of each member of the given ZIP file

8) We get the various characters like " ", "*", "O", "X", "Y", "\n", ....

9) Again a new riddle :) But this was simple. Just join them as a string and print it. We get:

10) Happy !!! hold on... just try http://www.pythonchallenge.com/pc/def/hockey.html , it gives you 1 more step :P

"it's in the air. look at the letters."

11) If we look at the letters, we have: O, X, Y, G, E, N  => oxygen :) finally it works.

TAKE AWAY:  zipfile module

Python Challenge Level 5 Solution

Problem = http://www.pythonchallenge.com/pc/def/peak.html

SOLUTION : http://www.pythonchallenge.com/pc/def/channel.html

CODE : https://github.com/dkuldeep11/python-challenge/tree/master/challenge-5

EXPLANATION ::

As you can see, nothing concrete hint here, all I could think of is to type "hill.html", but of course was useless :P

1) go to source code of the html page

2) there is a another image "banner.p" as mentioned below:

<peakhell src="banner.p"/>
3) click on the image, it will redirect you to the page, where scrambled data can be seen. 4) Using urllib module, download the page contents. 5) Intuitively the scrambled data seems to be serialized, let's try to deserialize it using pickle module 6) We do get meaningful data e.g.

7) only 2 types of characters, " " and "#", and their relevant count, so just form the corresponding string i.e. (' ', 5), ('#', 3) => '     ###' i.e. 5 spaces 3 pounds

8) go on printing every line in that fashion, and we get the answer as:

SOLUTION = channel

Python Pickle

How To Use Python Pickle

What is pickle module?

=> The pickle module provides serializing and de-serializing a Python object structure. “Pickling”  = Serializing 

“unpickling” = DeSerializing

To Pickle,       dump() function is used

To Un-Pickle, load() function is used 

code = https://github.com/dkuldeep11/Python-Tutorial/tree/master/pickle

Example:

import pickle

d1 = {}

d1['name'] = 'kuldeep'

d1['school'] = 'sjsu'

d1['city'] = 'san jose'

d1['id'] = 252666

print "before pickling \n",d1

#PICKLING

f1 = open("pickled_data", "wb")

pickle.dump(d1, f1)

f1.close()

#UNPICKLING

f1 =open("pickled_data", "rb")

d1 = pickle.load(f1)

f1.close()

print "after pickling \n", d1

-------------------------------------------------------------------

output:

before pickling 

{'city': 'san jose', 'school': 'sjsu', 'name': 'kuldeep', 'id': 252666}

after pickling 

{'city': 'san jose', 'school': 'sjsu', 'name': 'kuldeep', 'id': 252666}

-------------------------------------------------------------------



SOURCE = 

https://docs.python.org/2/library/pickle.html

How To Download The Web Page Data In Python

How To Download / Get The Web Page Data In Python

Let' consider you wish to download the whole contents of a web page: http://www.pythonchallenge.com/pc/def/banner.p


All you need to is use urllib module in Python.

import urllib
handle = urllib.urlopen("http://www.pythonchallenge.com/pc/def/banner.p")
print handle.read()

#You can also write the contents to the file
f1 = open("temp_data","w")
f1.write(handle.read())
f1.close()

Solution to python challenge level 4

http://www.pythonchallenge.com/pc/def/linkedlist.php

Just click on the image, it takes you to the following URL:

http://www.pythonchallenge.com/pc/def/linkedlist.php?nothing=12345

contents of the above URL: and the next nothing is 44827

As you can see, if you replace the above URL with nothing=44827, you will get a new nothing id and so on.... 

We are supposed to automate this process as follows:

- open the URL

- get the id = nothing is ####

- update the URL and continue till we get the id as number

Following is the Python Code:

import urllib2

import re

url = "http://www.pythonchallenge.com/pc/def/linkedlist.php?nothing="

id = '12345'

response = urllib2.urlopen(url + id)

text = response.read()

print text

while(True):

    response = urllib2.urlopen(url + id)

    text = response.read()

    print text

    new_id = "".join(re.findall(r'nothing is (\d*)', text))

    if new_id:

        print new_id

        id = new_id

    else:

        print "anwser = ", text

        break

-----------------------------------------------------------------------------------------

16044

Anwser =  Yes. Divide by two and keep going.

New answer = 8022

Just replace this id with the ID in above and run again

Final answer = peak.html

Next Challenge = http://www.pythonchallenge.com/pc/def/peak.html

Project Euler Problem 11 Solution

Largest product in a grid

Problem 11

Published on 22 February 2002 at 06:00 pm [Server Time]

In the 2020 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 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26  63  78  14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 2020 grid?



Answer: 70600674


Python Code = https://github.com/dkuldeep11/project-euler/blob/master/p11.py

Explanation:

how to rotate diagonal of matrix symmetrically using coding

		a				A
			b		B
				c C
			B		d
		E				e

Load Matrix Data From String To NumPy Matrix

If you are dealing with matrix computation, let it be as simple as matrix addition, NumPy is really awesome for it.

Generally we have the matrix data in following form:

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 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

In order to bring it to the form of matrix computation in any language like C, Java, we need to use 2 D array intuitively.

But, this is quite tedious as compared to Python NumPy, because we have to split 1st by "\n" and then by " " and then add elements 1 by 1.

Let's see how simple it is in NumPy

NOTE: If NumPy is not install, please install it:
http://www.scipy.org/install.html

--------------------------------------

import numpy as np

from StringIO import StringIO  #treats string as filehandle


ip1 = '''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 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'''


N = np.loadtxt(StringIO(ip1), dtype = 'int') #load the matrix :)

print N.shape  #dimensions

#iterate matrix for elements
for (x,y), value in np.ndenumerate(N):
    print x,y, " => ", N[x][y]

-------------------------------------------------------------

For other variance of inputs, please refer http://docs.scipy.org/doc/numpy/reference/generated/numpy.loadtxt.html

Pernicious Bugs

Summary: Following snippet took more than 10 hours to execute, which could be improved at amazing level by shifting just one line :)

Program is to find the sum of all prime number less than 2 million

# function to check if number is prime

def is_prime(num):
# prime numbers are greater than 1
   # check for factors
   for i in range(2,num/2 + 1):
       if (num % i) == 0:
           #print(num,"is not a prime number")
           return False
   else:
       #print(num,"is a prime number")
        return True

sum = 0
for i in range(2, 2000000):
    n = 0
    if is_prime(i):
        n = i
    sum = sum + n

print sum


IMPROVEMENT:
for i in range(2, 2000000):
    n = 0
    if is_prime(i):
        n = i
        sum = sum + n

print sum


REASON: Above shift of line inside if condition avoided the execution of statement "sum = sum +n" for all the numbers that were not prime too, which was of course undesirable.

Project Euler Problem 10 Solution

Summation of primes

Problem 10

Published on 08 February 2002 at 06:00 pm [Server Time]

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million

Python Code:

-------------------------------------

# function to check if number is prime

def is_prime(num):
# prime numbers are greater than 1
   # check for factors
   for i in range(2,num/2 + 1):
       if (num % i) == 0:
           #print(num,"is not a prime number")
           return False
   else:
       #print(num,"is a prime number")
        return True

sum = 0
for i in range(2, 2000000):
    n = 0
    if is_prime(i):
        n = i
        sum = sum + n

print sum

python challenge solution level 3

http://www.pythonchallenge.com/pc/def/equality.html


One small letter, surrounded by EXACTLY three big bodyguards on each of its sides.