Instantly share code, notes, and snippets.

# Kartik kaipakartik

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…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 a = [] def getTriangleFromFile(): f = open("triangle.txt") for line in f: b = [int(x) for x in line.split()] a.append(b) maxPaths = dict()
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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]
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 a = str(2 ** 1000) print reduce(lambda x, y : int(x) + int(y), a)
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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:
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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],
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #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
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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()
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…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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' +\
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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: