Project Euler solutions

001.py

#s = 0
#for i in range(1000):
#	if i % 3 == 0 or i % 5 == 0:
#		s += i
#print s

# one-liner
print sum( i for i in range(1000) if i % 3 == 0 or i % 5 == 0 )

# ANSWER: 233168

002.py

s = 0
i0 = 1
i1 = 2
while i1 < 4000000:
	if i1 % 2 == 0:
		s += i1
	temp = i1
	i1 = i1 + i0
	i0 = temp
	
print s

# ANSWER: 4613732

003.py

from math import sqrt

def lpf(number):
	for i in range(2, int(sqrt(number))):
		if number % i == 0:
			return lpf(number / i)
	return number

print lpf(600851475143)

# ANSWER: 6857

004.py

def max_palindrome(min=100, max=999):
	largest = 0
	for a in range(max, min-1, -1):
		for b in range(a-1, min-1, -1):
			m = a*b
			if m > largest and str(m) == str(m)[::-1]:
				largest = m
	return largest
print max_palindrome()

# ANSWER: 906609

005.py

def smallest_multiple(n):
	nums = range(1,n+1)
	primes = []
	for i in nums:
		# overlap the prime list with the prime factors for each number 1-20
		primes = overlap_list( primes, prime_factors(i) )
	
	return reduce((lambda x,y: x*y), primes ) # multiply each item in the list together

# figure out how many of each number should be in the list
def overlap_list(orig, factors):
	for i in set(factors):	# for each unique prime number
		add = factors.count(i) - orig.count(i)	# difference in number of given factors
		orig.extend([i] * add)	# add any missing factors (ignores negatives, so that's nice)
	return orig

def prime_factors(n):
	primfac = []
	d = 2
	while d*d <= n:
		while (n % d) == 0:
			primfac.append(d) # repeat multiple factors
			n //= d
		d += 1
	if n > 1:
	   primfac.append(n)
	return primfac

print smallest_multiple(20)

# ANSWER: 2 2 5 3 3 4 19 17 13 11 7 = 232792560

006.py

max = 100

sumsquare = 0
squaresum = (max * (max + 1) / 2) ** 2
for i in range(max+1):
	sumsquare += i ** 2
print (squaresum - sumsquare)

# ANSWER: 25164150

007.py

def nth_prime(n):
	# create arbitrarily high upper limit
	limit = (n * 100) + 1
	
	# start building the prime list
	primes = [True] * limit
	primes[0], primes[1] = [None] * 2
	
	count = 0
	for i,val in enumerate(primes):
		if val is True:
			# sieve out non-primes (iterate thru list by multiples of found primes)
			primes[i*2::i] = [False] * (((limit-1) // i) - 1)
			count += 1
		if count == n:
			return i
	return None

print nth_prime(10001)

# ANSWER: 104743

008.py

target = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
digits = [int(i) for i in target]
highest = 0

for i in range(0, len(digits)-13):
	test = reduce((lambda x,y: x*y), digits[i:i+13] )
	if test > highest:
		highest = test

print highest

# ANSWER: 23514624000

009.py

def PythTrip(n):
	for a in range(1, n+1):
		for b in range(a, n+1):
			c = n - a - b
			if a**2 + b**2 == c**2:
				print a,b,c
				return a*b*c
			
print PythTrip(1000)

# ANSWER: 31875000

010.py

def primesum(limit):
	# start building the prime list
	primes = [True] * limit
	primes[0], primes[1] = [None] * 2
	
	sum = 0
	for i,val in enumerate(primes):
		if val is True:
			# sieve out non-primes (iterate thru list by multiples of found primes)
			primes[i*2::i] = [False] * (((limit-1) // i) - 1)
			
			# add our prime to the sum
			sum += i
	return sum

print primesum(2000000)

# one-liner
#print sum([x for x in range(2, 2000000) if all([x%i != 0 for i in range(2,int(x**0.5)+1)])])

# ANSWER: 142913828922

011.py

grid = [
[ 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],
[21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95],
[78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92],
[16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57],
[86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58],
[19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40],
[ 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66],
[88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69],
[ 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36],
[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16],
[20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54],
[ 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48] ]



def product_in_direction(grid, start, direction, steps):
    x0, y0 = start
    dx, dy = direction

    if  not(0 <= y0                  < len(grid) and
            0 <= y0 + (steps - 1)*dy < len(grid) and
            0 <= x0                  < len(grid[y0]) and
            0 <= x0 + (steps - 1)*dx < len(grid[y0])):
        return 0

    product = 1
    for n in range(steps):
        product *= grid[y0 + n*dy][x0 + n*dx]
    return product

largest = 0
#horizontal and vertical
for y in range(len(grid)):
    for x in range(len(grid[y])):
        largest = max(
            product_in_direction(grid, (x, y),   (1,  0), 4), # horizontal
            product_in_direction(grid, (x, y),   (0,  1), 4), # vertical
            product_in_direction(grid, (x, y  ), (1,  1), 4), # right diagonal
            product_in_direction(grid, (x, y+3), (1, -1), 4), # left diagonal
            largest,
        )

print largest

# ANSWER: 70600674

012.py

def num_divisors(n):
    if n % 2 == 0: n = n/2
    divisors = 1
    count = 0
    while n % 2 == 0:
        count += 1
        n = n/2
    divisors = divisors * (count + 1)
    p = 3
    while n != 1:
        count = 0
        while n % p == 0:
            count += 1
            n = n/p
        divisors = divisors * (count + 1)
        p += 2
    return divisors
 
def find_triangular_index(factor_limit):
    n = 1
    lnum, rnum = num_divisors(n), num_divisors(n+1)
    while lnum * rnum < 500:
        n += 1
        lnum, rnum = rnum, num_divisors(n+1)
    return n

index = find_triangular_index(500)
print (index * (index + 1)) / 2

# ANSWER: 76576500

013.py

nums = [
37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690 ]

res = sum(nums)
print str(res)[:10:]

# ANSWER: 5537376230

014.py

def collatz(n, count=1):
	while n > 1:
		if n % 2 == 0:
			n = n / 2
		else:
			n = (3*n) + 1
		count += 1
	return count

longest = [0,0]
for i in range(1000000):
	c = collatz(i)
	if c > longest[0]:
		longest[0] = c
		longest[1] = i
print longest

# ANSWER: 837799

015.py

from math import factorial as f

def nCr(n,r):
    return f(n) / f(r) / f(n-r)

print nCr(40, 20)

# ANSWER: 137846528820

016.py

s = [int(i) for i in str(2**1000)]
print sum(s)

# ANSWER: 1366

017.py

# construct our words based on the rules provided
digit = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
tens = ['', 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']
hundred = 'hundred'
thousand = 'onethousand'

count = 0
for i in  range(1,1000):
	s = ''
	
	# if it's in the hundreds, construct that part first
	if i > 99:
		s += digit[i/100] + hundred
		if i % 100 != 0:
			s += 'and'
	
	# 1-20 are special cases
	if i % 100 < 20:
		s += digit[i%100]
	# otherwise construct it normally (tens & ones places)
	else:
		s += tens[(i/10)%10] + digit[i%10]
	
	# total up the number of letters
	count += len(s)
	print s

# 1000 can be a special case too, since there's only 1 of it
print thousand
count += len(thousand)

print count

# ANSWER: 21124

018.py

def buildSums(data, rowNum):
	for i in range( len(data[rowNum]) ):
		data[rowNum][i] += max( [data[rowNum+1][i], data[rowNum+1][i+1]] )
	if len(data[rowNum]) == 1:
		return data[0][0]
	else:
		return buildSums(data, rowNum-1)

rows = [[75],
		[95, 64],
		[17, 47, 82],
		[18, 35, 87, 10],
		[20,  4, 82, 47, 65],
		[19,  1, 23, 75,  3, 34],
		[88,  2, 77, 73,  7, 63, 67],
		[99, 65,  4, 28,  6, 16, 70, 92],
		[41, 41, 26, 56, 83, 40, 80, 70, 33],
		[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
		[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
		[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
		[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
		[63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
		[ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]]


print buildSums(rows, len(rows)-2)

# ANSWER: 1074

019.py

import datetime as dt

sundays = 0
for year in range(1901, 2001):
	for month in range(1, 13):
		if dt.date(year, month, 1).weekday() == 6:
			sundays += 1
print sundays

# ANSWER: 171

020.py

from math import factorial

num = factorial(100)
digits = [int(i) for i in str(num)] # convert number to a list of digits
print sum(digits)

# ANSWER: 648

021.py

from math import sqrt

def totalDivisors(n):
	total = 1 # counts 1 but not the number itself, plus all other divisors
	for i in range( 2, int(sqrt(n)) + 1 ):
		if n % i == 0:
			total += i + (n/i)
	return total

total = 0
i = 1
while i < 10000:
	a = totalDivisors(i)
	if i != a and totalDivisors(a) == i:
		print i, a
		total += a + i
		i = a+1
	else:
		i += 1
print total

# ANSWER: 31626

022.py

def wordValue(word):
	return sum([ord(x)-64 for x in word])

with open('names.txt', 'r') as fstream:
	list = [x.strip('"') for x in fstream.read().split(',')]
	list.sort()

total = 0
for i in range(len(list)):
	total += wordValue( list[i] ) * (i+1)
	
print total

# one-liner
print sum( [sum([ord(x)-64 for x in list[a]])*(a+1) for a in range(len(list))] )

# ANSWER: 871198282

023.py

from math import sqrt

def isAbundant(n):
	total = 1 # counts 1 but not the number itself, plus all other divisors
	for i in range( 2, int(sqrt(n)) + 1 ):
		if n % i == 0:
			total += i + (n/i)
	if float( sqrt(n) ) == int( sqrt(n) ):
		total -= sqrt(n)
	return total > n

def getAbunds(limit=28123):
	abunds = []
	for i in range(12, limit):
		if isAbundant(i): abunds.append( i )
	return abunds

def abundantSums(limit=28123):
	# get the abundant numbers
	abunds = getAbunds(limit)

	# figure out the numbers that can be written as the sum of abundant numbers
	written = [False] * (limit+1)
	for x in abunds:
		for y in abunds:
			if x + y <= limit:
				written[x+y] = True
			else:
				break
	return written

total = 0
limit = 28123
ab_sums = abundantSums(limit)
for i in range(limit+1):
	if not ab_sums[i]:
		total += i
print total

# ANSWER: 4179871

024.py

from itertools import permutations
num = list(permutations(range(10)))[999999]
print ''.join( [str(x) for x in num] )

# ANSWER: 2783915460

025.py

f0, f1 = 1, 1
index = 2

while len(str(f1)) < 1000:
	f1, f0 = f1+f0, f1
	index += 1

print index

# ANSWER: 4782

026.py

""" 1/d has a cycle of n digits if (10^n - 1) % d = 0 (for any given prime d) """
def recurring_cycle(n):
    for length in range(1, n):
        if 10**length % n == 1:
            return length
    return 0

d = 0
longest = 0
for i in range(1, 1000):
	test = recurring_cycle( i )
	if test > longest:
		longest = test
		d = i
print d

# ANSWER: 983

027.py

quad = (lambda a,b,n: (n**2) + (a*n) + b)

def isPrime(n):
	for i in range(2, int(abs(n)**0.5) + 1):
		if n % i == 0: return False
	return True

def test(a, b):
	n = 0
	while isPrime( quad(a,b,n) ):
		n += 1
	return n

highest = 0
value = 0
for a in range(-1000, 1000):
	for b in range(-1000, 1000):
		n = test(a, b)
		if n > highest:
			highest = n
			value = a * b
print value, "with", highest, "primes"

# ANSWER: -59231

028.py

# 1
# 3 5 7 9 
# 13 17 21 25
# 31 37 43 49
# ...

sum, num = 1, 1
iterator = 2

for i in range(500):	# 1001 x 10001 means from center, each will extend 500 numbers out
	for z in range(4):	# for each of the edges
		num += iterator	# advance our simulated edge by the length of a side (iterator)
		sum += num		# add that edge to our sum
	iterator += 2		# iterator increases by 2 for each new layer (4 edges = 1 layer)
	
print sum

# ANSWER: 669171001

029.py

list = set()
for a in range(2, 101):
	for b in range(2, 101):
		list = list.union([a**b])
print len(list)

# ANSWER: 9183

030.py

total = 0
for i in range(2,354294):
	digits = [int(x) for x in str(i)]

	test = sum([x**5 for x in digits])
	if test == i:
		print i
		total += i
print "answer: ", total

# ANSWER: 443839

031.py

target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [1] + [0]*target

for coin in coins:
    for i in range(coin, target+1):
        ways[i] += ways[i-coin]

print ways[target]

# ANSWER: 73682

032.py

def isPan(a, length=9):
	return (len(a) == length) and all( [(str(x) in a) for x in range(1, length+1)] )

total = set()
for a in range(10000):
	for b in range(100):
		if len( str(a) + str(b) + str(a*b) ) > 9:
			break
		if isPan( str(a) + str(b) + str(a*b) ):
			total |= {a*b}  # union operator for sets
			print a, b, a*b
print sum(total)

# ANSWER: 45228

033.py

from fractions import gcd

def same(a, b):
	try:
		return list( set(a).intersection(b) )[0]
	except IndexError:
		return ''

def digit_cancel(a, b):
	a, b = str(a), str(b)
	s = same(a,b)
	a_mod = a.replace(s, '', 1)
	b_mod = b.replace(s, '', 1)
	
	# {shared digit exists} and {is not trivial fraction} and {no divide by zero}
	if s and s != '0' and b_mod != '0':
		#print a,b,'\t',a_mod, b_mod
		test1 = float(a) / float(b)
		test2 = float(a_mod) / float(b_mod)
		if test1 == test2:
			print a, b
			return True
	return False

num = 1
den = 1
for a in range(10,100):
	for b in range(a+1, 100):
		if digit_cancel(a,b):
			num *= a
			den *= b

print den / gcd(num, den)

# ANSWER: 100

034.py

from math import factorial

def isDigitFactorial(n):
	return n == sum( [factorial(int(x)) for x in str(n)] )

total = 0
prev = 0
for i in range(3, 362880):
	if isDigitFactorial(i):
		total += i
print total

# ANSWER: 40730

035.py

from math import sqrt

def isPrime(n):
	for i in range(2, int(sqrt(n))+1):
		if n % i == 0:
			return False
	return True

def isCirc(n):
	orig = str(n)
	n = str(n)
	while True:
		# each rotation must be prime
		if not isPrime(int(n)):
			return False
		else:
			# rotate and continue testing
			n = n[1:len(n)] + n[0]
		
		# end loop condition (simulates a do-while loop)
		if orig == n: break
	return True

count = 0
for i in range(2, 1000000):
	if isCirc(i):
		print i
		count += 1
print "count: ", count

# ANSWER: 55

036.py

bin = (lambda x: "{0:b}".format(x))

def isPalindrome(n):
	return str(n) == str(n)[::-1]

total = 0
for i in range(1000000):
	if isPalindrome(i) and isPalindrome( bin(i) ):
		print i
		total += i
print total

# ANSWER: 872187

037.py

from math import sqrt
root = (lambda x: int(sqrt(x)))
conv = (lambda x: int(str(x)))

def isPrime(n):
	if n == 1: return False
	for i in range(2, root(n) + 1):
		if n % i == 0: return False
	return True

def isTruncatable(n):
	i = 1
	while i < len(str(n)):
		if not isPrime( int(str(n)[i:: ]) ) or not isPrime( int(str(n)[:-i:]) ):
			return False
		i += 1
	return True

i = 11 # 2, 3, 5, 7 don't count
count = 0
total = 0
while count < 11:
	if isPrime(i) and isTruncatable(i):
		print i
		total += i
		count += 1
	i += 1
print 'sum', total

# ANSWER: 748317

038.py

def construct(a):
	list = ''
	i = 1
	while len(list) < 9:
		list += str(a*i)
		i += 1
	return list

def isPan(a, length=9):
	return (len(a) == length) and all( [(str(x) in a) for x in range(1, length+1)] )

largest = 0
for i in range(9123, 9877):
	# multiple i by (1,2,3,4,5...n) until combine
	pan = construct(i)
	if isPan(pan):
		print pan
		if pan > largest: largest = pan
print "ans: ", largest

# ANSWER: 932718654

039.py

''' worked most of this out with math beforehand
a^2 + b^2 = c^2
a + b + c = p
...
b = p(p - 2a) / 2(p-a)
a <= b < c  -->  a < p/3
'''
result = 0
solutions = 0
for p in range(2, 1001, 2):
	num = 0
	for a in range(2, p/3):
		if (p*(p-(2*a))) % (2*(p-a)) == 0:
			num += 1
		
	if num > solutions:
		solutions = num
		result = p
print result, solutions

# ANSWER: 840

040.py

digits = [1, 10, 100, 1000, 10000, 100000, 1000000]

def champernowne(limit=1000000):
	part = '.'
	i = 1
	while len(part) < limit + 1:
		part += str(i)
		i += 1
	return part

#print reduce(lambda x,y: x,y, [int(x) for x in 
s = champernowne()
print reduce( (lambda x,y: x*y), [int(s[i]) for i in digits] )

# ANSWER: 210

041.py

from math import sqrt

def isPan(a, length=9):
	s1 = (len(str(a)) == length)
	s2 = all( [(str(x) in str(a)) for x in range(1, length+1)] )
	return s1 and s2

def nextPandigital(a, length=7):
	for i in range(a-1, 0, -1):
		if isPan(i, 7):
			return i
		if i == 1:
		 return i

def isPrime(n):
	for i in range( 2, int(sqrt(n))+1 ):
		if n % i == 0: return False
	return True

# 8- or 9-digit pandigital numbers can't be prime (sum of digits is divisible by 3, meaning they are divisible by 3)
target = 7654321
while True:
	if isPrime(target):
		print target
		break
	target = nextPandigital(target)

# ANSWER: 7652413

042.py

triangles = [sum(range(x)) for x in range(100)]

def wordValue(word):
	return sum([ord(x)-64 for x in word])

def isTriangleValue(n):
	return n in triangles

list = []
with open('words.txt', 'r') as fstream:
	for line in fstream:
		words = line.split(',')
		list.extend( [x.replace('"','') for x in words] )

count = 0
for word in list:
	if isTriangleValue( wordValue( word ) ):
		count += 1
print count

# ANSWER: 162

043.py

from itertools import permutations
digits = [(1,4,2), (2,5,3), (3,6,5), (4,7,7), (5,8,11), (6,9,13), (7,10,17)]
length = 9
ps = '0123456789'[:length+1]

s = 0
for px in permutations(ps, length+1):
	q = ''.join(px)
	qs = 0
	for d in digits[:length-2]:
		qs += int(q[d[0]:d[1]]) % d[2]
	if qs == 0:
		s += int(q)

print s

# ANSWER: 16695334890

044.py

# takes ridiculously long

def pentagonal(n):
	return n * (3*n - 1) / 2

def pentagon():
	pents = [pentagonal(x) for x in range(1, 5000)]
	for j in range(len(pents)):
		for k in range(len(pents[j::])):
			if pents[j]+pents[k] in pents and pents[k]-pents[j] in pents:
				print j,k
				return abs(pents[k] - pents[j])
print pentagon()

# ANSWER 5482660

046.py

from math import sqrt

def isPrime(n):
	for i in range(2, int(sqrt(n))+1):
		if n % i == 0: return False
	return True

def containsGoldbach(i):
	for num in range(2, i):
		if isPrime(num):
			x = 0
			while num + (2 * x**2) < i:
				x += 1
			
			if num + (2 * x**2) == i:
				print "{0} = {1} + 2*{2}^2".format(i,num,x)
				return True
	
	return False

def GoldbachConj():
	for i in range(3, 1000000, 2):
		if not isPrime(i): # i is odd and non-prime, so it's a Goldbach number
			if not containsGoldbach(i):
				print i, "cannot be expressed"
				return i

print GoldbachConj()

# ANSWER: 5777

047.py

def isPrime(n):
	for i in range(2, n):
		if n % i == 0: return False
	return True

def dpf(n):
	factors = set()
	for i in range(2, int(n**0.5)+1):
		if n % i == 0:
			if isPrime(i):
				factors = factors.union( set([i]) )
			if isPrime(n/i):
				factors = factors.union( set([n/i]) )
	return list(factors)

count = 0
target = 2*3*5*7
while count < 4:
	if len(dpf(target)) == 4:
		count += 1
	else:
		count = 0
	
	target += 1
print target-4

# ANSWER: 134044

048.py

x = 0
for i in range(1, 1001):
	x += i**i
print str(x)[-10::]

# ANSWER: 9110846700

049.py

<<<<<<< HEAD
def isPrime(n):
	for i in range(2, int(n**0.5)+1):
		if n % i == 0: return False
	return True

def permutations(word):
	word = str(word)
	if len(word) <= 1:
		return [word]

	#get all permutations of length N-1
	perms=permutations(word[1:])
	char=word[0]
	result=[]
	#iterate over all permutations of length N-1
	for perm in perms:
		#insert the character into every possible location
		for i in range(len(perm)+1):
			result.append(perm[:i] + char + perm[i:])
	return result

def isPermutation(word, test):
	return str(test) in permutations(word)

inc = 3330
a = 1487
while True:
	a += 2
	b, c = a + inc, a + 2*inc

	if isPrime(a) and isPrime(b) and isPrime(c):
		if isPermutation(a,b) and isPermutation(a,c):
			print 'solved',a,b,c
			break
print str(a) + str(b) + str(c)

# ANSWER: 296962999629
=======
def isPrime(n):
	for i in range(2, int(n**0.5)+1):
		if n % i == 0: return False
	return True

def permutations(word):
	word = str(word)
	if len(word) <= 1:
		return [word]

	#get all permutations of length N-1
	perms=permutations(word[1:])
	char=word[0]
	result=[]
	#iterate over all permutations of length N-1
	for perm in perms:
		#insert the character into every possible location
		for i in range(len(perm)+1):
			result.append(perm[:i] + char + perm[i:])
	return result

def isPermutation(word, test):
	return test in permutations(word)

print isPermutation('abc', 'bfac')

n, f = 1487, 1 	# start search with prime from description
while True:
	n += 3-f	# generates prime candidates faster than checking odd numbers
	f = -f
	b, c = n+3330, n+6660
	if isPrime(n) and isPrime(b) and isPrime(c) \
		and isPermutation(n,b) and isPermutation(b,c): break

print "Project Euler 49 Solution =", str(n)+str(b)+str(c), n, b, c
>>>>>>> 1dd1702304c8af17de22fc0f1ddca382c718f2b4

050.py

def isPrime(n):
	for i in range(2, int(n**0.5)+1):
		if n % i == 0: return False
	return True

def sieve(limit):
	# start building the prime list
	nums = [True] * limit
	nums[0], nums[1] = [False] * 2
	
	primes = []
	for i,val in enumerate(nums):
		if val is True:
			# sieve out non-nums (iterate thru list by multiples of found nums)
			nums[i*2::i] = [False] * (((limit-1) // i) - 1)
			
			# add the newly found prime to the list
			primes.append(i)
	return primes

target = 1000000

# generate a very long sum of prime numbers (less than 1 million)
i, total = 0, 0
primes = sieve(5000)
while total < target:
	print primes[i],
	total += primes[i]
	i += 1
total -= primes[i-1] # adjust for going over
print '=', total

# remove smaller primes until we reach a prime for the total
i = 0
while not isPrime(total):
	print primes[i],
	total -= primes[i]
	i += 1
print '=', total

# ANSWER: 997651

051.py

def isPrime(n):
	for i in range(2, int(n**0.5)+1):
		if n % i == 0: return False
	return True

def proc(i):
	family = 0
	if isPrime(i):
		s = str(i)
		for digit in range(1,10):
			for d in s:
				d = s[0]
				temp = s.replace(d, str(digit))
				print temp,
				if isPrime(int(temp)):
					family += 1
					print '+1',
				print
	return family

print proc(13)

052.py

from __future__ import print_function

def isPermutation(word, test):
	word, test = str(word), str(test)
	return len(word) == len(test) and sorted(word) == sorted(test)

a = 10
while True:
	a += 1
	print(a,end='\r')
	if isPermutation(a, a*2) and isPermutation(a, a*3) and isPermutation(a, a*4) and isPermutation(a, a*5) and isPermutation(a, a*6):
		print('\nans =', a)
		break

# ANSWER: 142857

053.py

from math import factorial as f

def choose(n, r):
	return f(n) / (f(r) * f(n-r))

total = 0
for n in range(1, 101):
	for r in range(1, n+1):
		if choose(n, r) > 1000000:
			total += 1
print total

# ANSWER: 4075

054.py

from collections import Counter

with open('poker.txt', 'r') as fstream:
	hands = (line.split() for line in fstream.readlines())

values = {r:i for i,r in enumerate('23456789TJQKA', start=2)}
straights = [(v, v-1, v-2, v-3, v-4) for v in range(14, 5, -1)] + [(14, 5, 4, 3, 2)]
ranks = [(1,1,1,1,1),(2,1,1,1),(2,2,1),(3,1,1),(),(),(3,2),(4,1)]

def hand_rank(hand):
	score = zip(*sorted(((v, values[k]) for
		k,v in Counter(x[0] for x in hand).items()), reverse=True))
	score[0] = ranks.index(score[0])
	if len(set(card[1] for card in hand)) == 1: score[0] = 5  # flush
	if score[1] in straights:
		score[0] = 8 if score[0] == 5 else 4  # str./str. flush
	return score

print sum(hand_rank(hand[:5]) > hand_rank(hand[5:]) for hand in hands)

055.py

def isPalindrome(n):
	return str(n) == str(n)[::-1]

def reverse(n):
	return int(str(n)[::-1])

def isLychrel(n, depth=50):
	for i in range(depth):
		test = n + reverse(n)
		if isPalindrome(test):
			print test
			return False
		n = test
	return True

count = 0
for i in range(10000):
	count += isLychrel(i)
print count

# ANSWER: 249

056.py

def digitSum(n):
	return sum( [int(x) for x in str(n)] )

max = 0
for a in range(1, 100):
	for b in range(1, 100):
		d = digitSum(a**b)
		if d > max:
			max = d
print max

# ANSWER: 972

057.py

from math import log10 as log
def slen(a):
	return len(str(a))

count = 0
den, num = 2,3
for z in range(1000):
	num += 2 * den		# n[k+1] = n[k] + 2*d[k]
	den = num - den		# d[k+1] = n[k] + d[k]   = n[k+1] - d[k]
	
	if slen(num) > slen(den):
		count += 1

print(count)

# ANSWER 153

058.py

'''
65 64 63 62 61 60 59 58 57
66 37 36 35 34 33 32 31 56
67 38 17 16 15 14 13 30 55
68 39 18  5  4  3 12 29 54
69 40 19  6  1  2 11 28 53
70 41 20  7  8  9 10 27 52
71 42 21 22 23 24 25 26 51
72 43 44 45 46 47 48 49 50
73 74 75 76 77 78 79 80 81
'''

def isPrime(n):
	for i in range(2, int(n**0.5)+1):
		if n % i == 0: return False
	return True

num = 1
mod = 2
count_prime = 0
count_all = 1

while True:
	for i in range(4):
		num += mod
		if isPrime(num):
			count_prime += 1
		count_all += 1
	
	ratio = float(count_prime) / float(count_all)
	if ratio <= 0.10:
		break
	
	mod += 2

print(mod+1)

# ANSWER: 26241

059.py

key = (lambda a: [ord(x) for x in a])

def decrypt(msg, key):
	i = 0
	final = ''
	for a in msg:
		final += chr(msg[i] ^ key[i%3])
		i += 1
	
	return final

msg = []
with open('cipher.txt', 'r') as fstream:
	msg = [int(x) for x in fstream.read().split(',')]

result = decrypt(msg, key('god')) # key was computed manually from assumptions on the cipher

print result, sum(key(result))

# ANSWER: 107359

062.py

cubes = {}

def order(a):
	return ''.join(sorted(str(a)))

n = 0
while True:
	n += 1
	q = order(n**3)
	
	if q not in cubes:
		cubes[q] = 1
	else:
		cubes[q] += 1
	
	if cubes[q] == 5:
		print('found:', q)
		for a in range(n):
			if order(a**3) == q:
				print('soln:', a**3)
				break
		break

# ANSWER: 127035954683

063.py

total = 0
for i in range(1,10):
	for power in range(1, 100):
		digits = len(str(i**power))
		if digits == power:
			total += 1
			print i,power,i**power
		if digits > power:
			break
print total

# ANSWER: 49

065.py

from fractions import Fraction

def get_digit(n):
    if n % 3 == 2: return 2*((n+1)//3)
    return 1

def a_e_r(s, n):
    if s > n: return 0
    return Fraction(1, get_digit(s) + a_e_r(s+1,n))

def e_of(m):
    return 2 + a_e_r(1, m-1)

f = str(e_of(100).numerator)
end = 0
for i in f:
	end += int(i)
print(end)

# ANSWER: 272

067.py

def buildSums(data, rowNum):
	for i in range( len(data[rowNum]) ):
		data[rowNum][i] += max( [data[rowNum+1][i], data[rowNum+1][i+1]] )
	if len(data[rowNum]) == 1:
		return data[0][0]
	else:
		return buildSums(data, rowNum-1)

rows = []
with open('triangle.txt') as fstream:
	for line in fstream:
		rows.append([int(i) for i in line.rstrip('\n').split(" ")])

print buildSums(rows, len(rows)-2)

# ANSWER: 7273

069.py

def sieve(limit):
	# start building the prime list
	nums = [True] * limit
	nums[0], nums[1] = [False] * 2
	
	primes = []
	for i,val in enumerate(nums):
		if val is True:
			# sieve out non-nums (iterate thru list by multiples of found nums)
			nums[i*2::i] = [False] * (((limit-1) // i) - 1)
			
			# add the newly found prime to the list
			primes.append(i)
	return primes

target = 1000000
result = 1
i = 0

primes = sieve(int(target**0.5))
while result < target:
	result *= primes[i]
	i += 1
result /= primes[i-1]
print result

# ANSWER: 510510

071.py

a = 3
b = 7
n = 0
d = 1
limit = 1000000

for q in range(limit, 2, -1):
	p = (a * q - 1) // b
	if p*d > n*q:
		n = p
		d = q
print(n,d)

074.py

from math import factorial

limit = 1000000
count = 0

def calc_link(n):
	return sum( [factorial(int(x)) for x in str(n)] )

for i in range(limit):
	chain = []
	link = i
	link_count = 0
	while True:
		print(i, link, link_count)
		if link not in chain:
			chain.append(link)
			link_count += 1
		else:
			break
			
		link = calc_link(link)

	if link_count == 60:
		count += 1

print(count)

# ANSWER: 402

076.py

'''
0 1 2 4 6 10 14 ...
Integer Partitions of N - 1 (https://oeis.org/A000065) - N. J. A. Sloane
'''

table = [[0 for a in range(100)] for j in range(100)]

def partition(sum, largest):
	if largest == 0 or sum < 0:
		return 0
	if sum == 0:
		return 1

	if table[sum-1][largest-1] != 0:
		return table[sum-1][largest-1]

	table[sum-1][largest-1] = partition(sum,largest-1) + partition(sum-largest,largest)
	
	return table[sum-1][largest-1]

print(partition(100, 99));

# ANSWER: 190569291

079.py

orig = [319, 680, 180, 690, 129, 620, 762, 689, 762, 318, 368, 710, 720, 710, 629, 168, 160, 689, 716, 731, 736, 729, 316, 729, 729, 710, 769, 290, 719, 680, 318, 389, 162, 289, 162, 718, 729, 319, 790, 680, 890, 362, 319, 760, 316, 729, 380, 319, 728, 716]


codes = list(set().union( set(orig) ))
print sorted(codes)

''' output gives us the list in sorted order, makes it easier to compute
129 160 162 168 180 289 290 316 318 319 362 368 380 389 620 629 680 689 690 710 716 718 719 720 728 729 731 736 760 762 769 790 890

ans: 73162890
'''

# ANSWER: 73162890

081.py

def min_path_sum(matrix):
	n, m = len(matrix), len(matrix[0])
	for i in range(n):
		for j in range(m):
			if i*j > 0:
				matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
			elif i:
				matrix[i][j] += matrix[i-1][j]
			elif j:
				matrix[i][j] += matrix[i][j-1]
	return matrix[-1][-1]

matrix = []
with open('matrix.txt', 'r') as fstream:
	matrix = [line.rstrip('\n') for line in open('matrix.txt')]
	matrix = [map(int, row.split(',')) for row in matrix]

print min_path_sum(matrix)

# ANSWER: 427337

085.py

target = 2000000
closest = 0
area = 0

def calc(m,n):
	return m * (m+1) * n * (n+1) // 4

for m in range(1,100):
	for n in range(1,100):
		guess = calc(m, n)
		if abs(target - guess) < abs(target - closest):
			closest = guess
			area = m * n

print(area, closest, abs(target-closest))

# ANSWER: 2772

089.py

from re import sub

rows = []
with open('roman.txt', 'r') as fstream:
	rows = fstream.read()

# substitute 4 consecutive characters as 2 characters (i.e. IIII => IV)
print len(rows) - len(sub("DCCCC|LXXXX|VIIII|CCCC|XXXX|IIII", '  ', rows))

# ANSWER: 743

092.py

def proc(n):
	while n != 1 and n != 89:
		#print n,
		digits = [int(x) for x in str(n)]
		n = sum([i**2 for i in digits])
	#print n
	if n == 89: return 1
	return 0

count = 0
for i in range(1, 10000000):
	count += proc(i)
	print i, count
print count

# ANSWER: 8581146

097.py

a = pow(2, 7830457, 10000000000) * 28433 + 1
print str(a)[-10::]

# ANSWER: 8739992577

099.py

from math import log

high_value = 0
high_pair = ''
list = []

with open('base_exp.txt', 'r') as fstream:
	list = [x.strip() for x in fstream.readlines()]

for pair in list:
	x,y = [int(x) for x in pair.split(',')]
	calc = y * log(x) # log_a(x**y) = y * log_a(x)
	
	if calc > high_value:
		high_value = calc
		high_pair = pair

print(list.index(high_pair)+1)

euler.py

import os
from time import sleep

# title
print("Project Euler Problem Interface - Matt \'TheFrostlixen\' Fredrickson - 2016")

# main loop
while True:
	euler_id = input('Euler #')
	if len(euler_id) > 0:
		filename = '{0}.py'.format(euler_id.replace('e','').replace(' ',''))
		if euler_id.startswith('e'):
			os.system( 'notepad++ ' + filename )
		if os.path.isfile( filename ):
			os.system( filename )
		else:
			file( filename, 'w+' )
			os.system( 'notepad++ ' + filename )
			input()
			os.system( filename )
	print('')