Project Euler (Python)

print(sum(x for x in range(1000) if (x % 3 == 0 or x % 5 == 0)))

limit = 4000000
x, y = 1, 2
total = 0
while (x <= limit):
    if x % 2 == 0:
        total += x
    x, y = y, x + y
print(total)

def find_largest_prime_factor(number):
    largest_prime_factor = 0
    divisor = 2
    while divisor <= number:
        if number % divisor == 0:
            largest_prime_factor = divisor
            number = number / divisor
        else:
            divisor = divisor + 1
    return largest_prime_factor
 
 
print(find_largest_prime_factor(600851475143))

def palindrome(number):
    """ determine if palindrome """
    digits = str(number)
    size = len(digits)
    for i in range(size // 2):
        if digits[i] != digits[size - 1 - i]:
            return False
    return True
 
 
solution=0
for x in range(100, 1000):
    for y in range(100, 1000):
        product = x * y
        if palindrome(product):
            if product > solution:
                solution = product
print(solution)

pals=[]
for i in range(100, 1000):
    for j in range(100, 1000):
        if str(i * j) == str(i * j)[ : : -1]:
            pals.append(i * j)
print(max(pals))

candidates = (i * j for i in range(100, 1000) for j in range(100,1000))
palindromes = [x for x in candidates if str(x) == str(x)[::-1]]
print(max(palindromes))

print(max(i * j for i in range(100, 1000) for j in range(100, 1000) if str(i * j) == str(i * j)[ : : -1]))

import functools
import operator
 
target = 20
prime_factors = []
for i in range(2, target + 1):
    q = i
    for p in prime_factors:
        if q % p == 0:
            q //= p
    if q != 1:
        prime_factors.append(q)
print(functools.reduce(operator.mul, prime_factors, 1))

import math
 
ans = 1
for i in range(1, 21):
    ans *= i // math.gcd(i, ans)
print(ans)

n = 100
s1 = (sum(i for i in range(1, n + 1)))**2
s2 =  sum(i**2 for i in range(1, n + 1))
print(str(s1 - s2))

import math
 
def is_prime(number):
    if number > 2 and number % 2 == 0:
        return False
    for factor in range(3, int(math.sqrt(number)) + 1, 2):
        if number % factor == 0:
            return False
    return True
 
 
count = 10001
i = 1
while count > 1:
    i += 2
    if is_prime(i):
        count -= 1
print(i)

from sympy import prime
print(prime(10001))

import math
 
data = open('input').read().strip()
data = [int(d) for d in data]
digits = 13
prod = []
for i in range(len(data) - digits - 1):
    prod.append( math.prod(data[i:i + digits]) )
print(max(prod))

sumabc = 1000
for a in range(1, sumabc + 1):
    for b in range(a + 1, sumabc + 1):
        c = sumabc - a - b
        if a * a + b * b == c * c:
            # It is now implied that b < c, because we have a > 0
            print(a, b, c, a * b * c)

import sympy
print(sum(sympy.primerange(2000000)))

def compute():
    # We visit each grid cell and compute the product 
    # in the 4 directions starting from that cell.
    ans = -1
    width = len(grid[0])
    height = len(grid)
    for y in range(height):
        for x in range(width):
            if x + num <= width:
                ans = max(grid_product(x, y,  1, 0, num), ans)
            if y + num <= height:
                ans = max(grid_product(x, y,  0, 1, num), ans)
            if x + num <= width and y + num <= height:
                ans = max(grid_product(x, y,  1, 1, num), ans)
            if x - num >= -1    and y + num <= height:
                ans = max(grid_product(x, y, -1, 1, num), ans)
    return str(ans)
 
 
def grid_product(ox, oy, dx, dy, n):
    result = 1
    for i in range(n):
        result *= grid[oy + i * dy][ox + i * dx]
    return result
 
 
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],
]
 
num = 4
 
print(compute())

import math
 
def factors(number):
    """ calculate factors """
    fs = {1, number}
    for f in range(2, int(math.sqrt(number)) + 1):
        q, r = divmod(number, f)
        if r == 0:
            fs.add(f)
            fs.add(q)
    return fs
 
 
i = 1
triangle = 1
target = 500
 
while True:
    i += 1
    triangle += i
    if len(factors(triangle)) > target:
        break
 
print(triangle)

data = open("input").read().splitlines()
data = [int(x) for x in data]
total = 0
for d in data:
    total+=d
print(str(total)[:10])

def collatz(num):
    n = num
    yield n
    while n !=1:
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3 * n + 1
        yield n
 
 
i = 1
imax = 1000000
lmax = 0
ans = 0
while i < imax:
    seq = list(collatz(i))
    l = len(seq)
    if l > lmax:
        lmax = l
        ans = i
    i += 1
 
print(ans)

def collatz(n) -> int:
    global cache
 
    while n not in cache:
        if n % 2 == 0:
            cache[n] = 1 + collatz(n // 2)
        else:
            cache[n] = 1 + collatz(3 * n + 1)
    return cache[n]
 
 
cache = {1: 0}
limit = 1000000
 
for i in range(1, limit):
    collatz(i)
 
v = list(cache.values())
k = list(cache.keys())
print(k[v.index(max(v))])
# or
print(max(cache, key=cache.get))
print(max(cache, key=lambda k: cache.get(k)))

size = 20
 
grid = [[0 for x in range(size + 1)] for y in range(size + 1)]
 
for y in range(size + 1):
    for x in range(size + 1):
        match x, y:
            case 0, y:
                grid[y][0] = 1
            case x, 0:
                grid[0][x] = 1
            case _:
                grid[y][x] = grid[y][x - 1] + grid[y - 1][x]
 
print(grid[size][size])
 
# Rotating the grid clockwise by 45 degrees shows that the number of paths to
# any point in the lattice matches Pascal's triangle.

answer = 0
n = 2 ** 1000
while n > 0:
    n, d = divmod(n, 10)
    answer += d
print(answer)

n = 2**1000
print (sum(int(c) for c in str(n)))

'''
- For the numbers 0 to 19, we write the single word:
  {zero, one, two, three, four, five, six, seven, eight, nine,
  ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen}.
- For the numbers 20 to 99, we write the word for the tens place:
  {twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety}.
  Subsequently if the last digit is not 0, then we write the word for the ones place (one to nine).
- For the numbers 100 to 999, we write the ones word for the hundreds place followed by "hundred":
  {one hundred, two hundred, three hundred, ..., eight hundred, nine hundred}.
  Subsequently if the last two digits are not 00, then we write the word "and"
  followed by the phrase for the last two digits (from 01 to 99).
- For the numbers 1000 to 999999, we write the word for the three digits starting at the
  thousands place and going leftward, followed by "thousand". Subsequently if the last three
  digits are not 000, then we write the phrase for the last three digits (from 001 to 999).
'''
 
def to_english(n):
	if 0 <= n < 20:
		return ONES[n]
	elif 20 <= n < 100:
		return TENS[n // 10] + (ONES[n % 10] if (n % 10 != 0) else "")
	elif 100 <= n < 1000:
		return ONES[n // 100] + "hundred" + (("and" + to_english(n % 100)) if (n % 100 != 0) else "")
	elif 1000 <= n < 1000000:
		return to_english(n // 1000) + "thousand" + (to_english(n % 1000) if (n % 1000 != 0) else "")
	else:
		raise ValueError()
 
 
ONES = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
 
TENS = ["", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
 
ans = sum(len(to_english(i)) for i in range(1, 1001))
print (str(ans))

triangle = [
	[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],
]
 
for i in reversed(range(len(triangle) - 1)):
    for j in range(len(triangle[i])):
        triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])
print (str(triangle[0][0]))

import datetime
 
ans = sum(1
for y in range(1901, 2001)
	for m in range(1, 13)
		if datetime.date(y, m, 1).weekday() == 6)
print (str(ans))

import math
n = math.factorial(100)
ans = sum(int(c) for c in str(n))
print (str(ans))

# Compute sum of proper divisors for each number
divisorsum = [0] * 10000
for i in range(1, len(divisorsum)):
	for j in range(i * 2, len(divisorsum), i):
		divisorsum[j] += i
# Find all amicable pairs within range
ans = 0
for i in range(1, len(divisorsum)):
	j = divisorsum[i]
	if j != i and j < len(divisorsum) and divisorsum[j] == i:
		ans += i
print(str(ans))

data = open("input").read().split(",")
data = [x.strip('"') for x in data]
ans = sum((i + 1) * (ord(c) - ord('A') + 1)
for (i, name) in enumerate(sorted(data))
	for c in name)
print (str(ans))

LIMIT = 28124
divisorsum = [0] * LIMIT
for i in range(1, LIMIT):
	for j in range(i * 2, LIMIT, i):
		divisorsum[j] += i
abundantnums = [i for (i, x) in enumerate(divisorsum) if x > i]
 
expressible = [False] * LIMIT
for i in abundantnums:
	for j in abundantnums:
		if i + j < LIMIT:
			expressible[i + j] = True
		else:
			break
 
ans = sum(i for (i, x) in enumerate(expressible) if not x)
print(str(ans))

import itertools
arr = list(range(10))
temp = itertools.islice(itertools.permutations(arr), 999999, None)
print("".join(str(x) for x in next(temp)))

import itertools
 
DIGITS = 1000
prev = 1
cur = 0
for i in itertools.count():
    # At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
    if len(str(cur)) > DIGITS:
        print("Not found")
        exit()
    elif len(str(cur)) == DIGITS:
        print(str(i))
    # Advance the Fibonacci sequence by one step
    prev, cur = cur, prev + cur

import itertools
 
def reciprocal_cycle_len(n):
    seen = {}
    x = 1
    for i in itertools.count():
        if x in seen:
            return i - seen[x]
        else:
            seen[x] = i
            x = x * 10 % n
 
ans = max(range(1, 1000), key=reciprocal_cycle_len)
print(str(ans))

import itertools
 
def count_consecutive_primes(ab):
    a, b = ab
    for i in itertools.count():
        n = i * i + i * a + b
        if not isprime(n):
            return i
 
 
def isprime(number):
    """ is number prime """
    if number < 2:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    d = 3
    while d * d <= number:
        if number % d == 0:
            return False
        d += 2
    return True
 
 
ans = max(((a, b) for a in range(-999, 1000) for b in range(2, 1000)),
    key=count_consecutive_primes)
print(str(ans[0] * ans[1]))

size = 1001
ans = 1
ans += sum(4 * i * i - 6 * (i - 1) for i in range(3, size + 1, 2))
print(ans)

seen = set(a**b for a in range(2, 101) for b in range(2, 101))
print(str(len(seen)))