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.