My solutions to Project Euler in python
#1
def sum_div_by(n, stop):
p = (stop-1) // n
return n * p * (p+1) // 2
stop = 1000
print('#1:', sum_div_by(3, stop) + sum_div_by(5, stop) - sum_div_by(15, stop))
#2
def fib(stop):
a, b = 0, 1
while a < stop:
yield a
a, b = b, a + b
print('#2:', sum(x for x in fib(4000000) if x%2==0))
#3
from math import sqrt
from itertools import chain, count
def largest_prime_factor(n):
for factor in chain([2], count(3, 2)):
while(n % factor == 0):
n //= factor
if n == 1:
return factor
if factor > sqrt(n):
return n
print('#3:', largest_prime_factor(600851475143))
#4
from itertools import combinations
def is_pal(n):
n = str(n)
l = len(n)
return n[:l//2] == n[l//2:][::-1]
print('#4:', max(a*b for a, b in combinations(range(1000), 2) if is_pal(a*b)))
#5
from functools import reduce
from fractions import gcd
def lcm(a, b):
return (a * b) // gcd(a, b)
print('#5:', reduce(lcm, range(1, 21)))
#6
print('#6:', sum(range(1, 101))**2 - sum(x*x for x in range(1, 101)))
#7
from math import sqrt
def is_prime(n):
if n == 1: return False
if n < 4: return True # 2, 3
if n % 2 ==0: return False
if n < 9: return True # 5, 7
if n % 3 ==0: return False
else:
root = int(sqrt(n))
divisor = 5
while divisor <= root:
if n % divisor ==0: return False
if n % (divisor+2) ==0: return False
divisor += 6
return True
def nth_prime(stop):
i = n = 0
while n < stop:
i += 1
if is_prime(i):
n += 1
return i
print('#7:', nth_prime(10001))
#8
from functools import reduce
def n_adj_digits(n):
data = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
i = 0
while i < len(data) - n + 1:
yield data[i: i+n]
i += 1
def product(s):
return reduce(lambda a, b: int(a)*int(b), s)
print('#8:', max(product(n) for n in n_adj_digits(13)))
9
from functools import reduce
from math import sqrt
from operator import mul
def hyp(a, b):
return sqrt(a**2 + b**2)
def py_triplet_less_than(stop):
for a in range(stop//2, 0, -1):
for b in range(stop//2, 0, -1):
c = hyp(a, b)
if a + b + c == 1000:
return a, b, c
print('#9:', int(reduce(mul, py_triplet_less_than(1000))))
#10
from math import sqrt
def sum_primes(stop):
# Sieve of Eratosthenes
sieve = list(range(stop+1))
sieve[1] = 0
for n in range(2, int(sqrt(stop))+1):
if sieve[n] > 0:
for i in range(n*n, stop+1, n):
sieve[i] = 0
return sum(sieve)
print('#10:', sum_primes(2000000))
#11
import numpy as np
from itertools import chain
data = np.array([[8, 2, 22, 97, 38, 15, 0, 4, 0, 75, 4, 5, 7, 78, 52, 12, 5, 77, 91, 8],
[49, 49, 99, 4, 17, 81, 18, 57, 6, 87, 17, 4, 98, 43, 69, 48, 4, 56, 62, 0],
[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 4, 67, 53, 88, 3, 3, 49, 13, 36, 65],
[52, 7, 95, 23, 4, 6, 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, 4, 4, 28, 66, 33, 13, 8],
[24, 47, 32, 6, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 2, 35, 17, 12, 5],
[32, 98, 81, 28, 64, 23, 67, 1, 26, 38, 4, 67, 59, 54, 7, 66, 18, 38, 64, 7],
[67, 26, 2, 68, 2, 62, 12, 2, 95, 63, 94, 39, 63, 8, 4, 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, 2, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
[78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 8, 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, 6, 21, 58, 51, 54, 17, 58],
[19, 8, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 4],
[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, 2, 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, 4, 62, 76, 36],
[2, 69, 36, 41, 72, 3, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
[2, 73, 35, 29, 78, 31, 9, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
[1, 7, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]])
def diags(data):
height, width = data.shape
diags = (data.diagonal(i) for i in range(-height+1, width))
diags = chain(diags, (np.rot90(data).diagonal(i) for i in range(-width+1, height)))
return diags
def product_four(line):
if len(line) < 4:
return ()
def mul_four(i, x):
if i+4 > len(line):
return -float('inf')
else:
#print 'four:', line[i], line[i+1], line[i+2], line[i+3]
return line[i] * line[i+1] * line[i+2] * line[i+3]
return (mul_four(i, x) for i, x in enumerate(line))
all_directions = chain(data, data.T, diags(data))
nested_products = map(product_four, all_directions)
products = chain.from_iterable(nested_products)
print('#11:', max(products))
#12
from math import sqrt
def primes_to(stop):
# Sieve of Eratosthenes
sieve = list(range(stop+1))
sieve[1] = 0
for n in range(2, int(sqrt(stop))+1):
if sieve[n] > 0:
for i in range(n*n, stop+1, n):
sieve[i] = 0
return list(filter(lambda x: x>0, sieve))
def get_num_divisors(n):
if n % 2 == 0: n = n//2
result = 1
for p in primes:
if n == 1: break
p_count = 0
while n % p == 0:
p_count += 1
n //= p
result *= p_count+1
return result
def get_n(num_divisors, stop):
i = 1
a, b = 1, 1 # = get_num_divisors(1), # get_num_divisors(1+1)
while a*b <= stop:
i += 1
a, b = b, num_divisors[i+1]
return i
primes = primes_to(1000)
num_divisors = {i: get_num_divisors(i) for i in range(1, 20000)}
n = get_n(num_divisors, 500) # as in sum(ap) == n*(n + 1) // 2
triangular = n*(n + 1) // 2
print('#12:', triangular)
#13
data = [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]
print '#13:', str(sum(data))[:10]
#14
collatz = {}
def collatz_steps(n):
original_n = n
i = 0
while n is not 1:
if collatz.get(n):
i += collatz.get(n)
break
if n % 2 == 0:
n /= 2
i += 1
else:
n = 3*n + 1
i += 1
collatz[original_n] = i
return i
collatz_seq = ((i, collatz_steps(i)) for i in xrange(1, 1000000))
print '#14:', max(collatz_seq, key=lambda x: x[1])
#15
mem = {}
def lattice(x, y):
if mem.get((x, y)):
return mem.get((x, y))
if x == 0 or y == 0:
return 1
mem[x, y] = lattice(x-1, y) + lattice(x, y-1)
return mem[x, y]
print '#15:', lattice(20, 20)
#16
print '#16:', sum(int(x) for x in str(2**1000))