kaipakartik’s gists

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 / 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 / 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 / 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 / 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 / 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 / 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 / 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 abc

	print special()

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 / 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:

Kartik kaipakartik