Skip to content

Instantly share code, notes, and snippets.

@TheFrostlixen

TheFrostlixen/001.py

Last active April 26, 2017 22:08
Show Gist options
  • Save TheFrostlixen/c3a282719c4b1ce27329 to your computer and use it in GitHub Desktop.
Save TheFrostlixen/c3a282719c4b1ce27329 to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler solutions
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
016.py
s = [int(i) for i in str(2**1000)]
print sum(s)
# ANSWER: 1366
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
024.py
from itertools import permutations
num = list(permutations(range(10)))[999999]
print ''.join( [str(x) for x in num] )
# ANSWER: 2783915460
Raw
025.py
f0, f1 = 1, 1
index = 2
while len(str(f1)) < 1000:
f1, f0 = f1+f0, f1
index += 1
print index
# ANSWER: 4782
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
048.py
x = 0
for i in range(1, 1001):
x += i**i
print str(x)[-10::]
# ANSWER: 9110846700
Raw
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
Raw
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
Raw
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)
Raw
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
Raw
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
Raw
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)
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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)
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
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
Raw
097.py
a = pow(2, 7830457, 10000000000) * 28433 + 1
print str(a)[-10::]
# ANSWER: 8739992577
Raw
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)
Raw
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('')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment