Skip to content

Instantly share code, notes, and snippets.

View kaipakartik's full-sized avatar

Kartik kaipakartik

View GitHub Profile
@kaipakartik
kaipakartik / problem21_euler.py
Created January 11, 2014 17:39
Amicable numbers Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220…
amicable = {}
d = [0 for x in xrange(10000)]
def getSumOfDivisors(n):
divisors = [1]
i = 2
while n / i > i:
if n % i == 0:
divisors.append(i)
@kaipakartik
kaipakartik / problem18_euler.py
Created January 11, 2014 16:12
Maximum path sum I and II By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 + 9 = 23.
a = []
def getTriangleFromFile():
f = open("triangle.txt")
for line in f:
b = [int(x) for x in line.split()]
a.append(b)
maxPaths = dict()
@kaipakartik
kaipakartik / problem17_euler.py
Created January 11, 2014 15:36
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
singleDigits = ["zero","one","two","three","four","five","six","seven","eight","nine"]
tens = ["zero","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"]
teens = ["zero"] * 11 + ["eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"]
hundredLength = len("hundred")
andLength = len("and")
singleDigits = [len(x) for x in singleDigits]
@kaipakartik
kaipakartik / problem16_euler.py
Created January 11, 2014 02:14
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 2^1000?
a = str(2 ** 1000)
print reduce(lambda x, y : int(x) + int(y), a)
@kaipakartik
kaipakartik / problem15_euler.py
Created January 11, 2014 02:14
Starting in the top left corner of a 2×2 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 20×20 grid?
short = dict()
def getPaths(x, y):
if x == 0 and y == 0:
return 0
if x == 0:
return 1
if y == 0:
return 1
if (x,y) in short:
@kaipakartik
kaipakartik / problem11_euler.py
Created January 10, 2014 03:03
In the 20×20 grid below, four numbers along a diagonal line have been marked in red. What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
a = [
[8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8],
[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0],
[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],
[52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,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,3,45,2,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,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],
[24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
@kaipakartik
kaipakartik / problem10_euler.py
Created January 10, 2014 02:19
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
#We take the opposite approach here and find all the composite numbers
# upto 2 million and then we sum what is not composite(prime).
def prime(n):
composite = range(n)
for a in xrange(2, n):
b = a
for b in xrange(a * a, n, a):
composite[b] = 0;
sum = 0
@kaipakartik
kaipakartik / problem9_euler.py
Created January 10, 2014 01:30
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
def special():
for a in xrange(1, 1001):
for b in xrange(1, 1001):
c = 1000 -a -b;
if c < 0:
break;
if a * a + b * b == c * c:
return a*b*c
print special()
@kaipakartik
kaipakartik / problem8_euler.py
Created January 10, 2014 01:20
Find the greatest product of five consecutive digits in the 1000-digit number. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 6222989342338…
def largest_product(number):
maxProduct = 1
for i in range(len(number) - 5):
product = reduce(lambda x,y : int(x) * int (y), number[i: i + 5])
if product > maxProduct:
maxProduct = product
return maxProduct
a = \
'73167176531330624919225119674426574742355349194934' +\
@kaipakartik
kaipakartik / problem7_euler.py
Last active January 2, 2016 18:39
Problem 7 Project Euler By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?
def prime(n):
primes = [2]
start = 3
while len(primes) <= n:
isPrime = True;
for prime in primes:
if start % prime == 0:
isPrime = False;
break;
if isPrime: