Project Euler

# Multiples of 3 or 5


# Solution 1
multiples = []

for number in range(1, 1000):
    if number % 5 == 0 or number % 3 == 0:
        multiples.append(number)

print(sum(multiples))

# Even Fibonacci numbers


# Solution 1
a, b = 0, 1
maximum = 4_000_000

even_terms = []
while a + b <= maximum:
    fib = a + b
    if fib % 2 == 0:
        even_terms.append(fib)
    a, b = b, fib

print(sum(even_terms))

# Largest prime factor


# Solution 1
import math

from primePy import primes

prime = primes.factors(600851475143)
print(prime[-1])


# Solution 2
def prime_factors(num):
    largest_prime_factor = 1
    while num % 2 == 0:
        largest_prime_factor = 2
        num = num / 2

    for i in range(3, int(math.sqrt(num)) + 1, 2):
        while num % i == 0:
            largest_prime_factor = i
            num = num / i
    if num > 2:
        largest_prime_factor = num

    return largest_prime_factor


num = 600851475143
print(prime_factors(num))

# Largest palindrome product


# Solution 1
palindromes = []
products = []

for i in range(100, 1000):
    for o in range(100, 1000):
        products.append(i * o)

for product in products:
    is_palindrome = False
    product = str(product)
    reversed_product = []
    for c in reversed(product):
        reversed_product.append(c)
    reverse = "".join(reversed_product)
    if reverse == product:
        is_palindrome = True

    if is_palindrome == True:
        palindromes.append(int(product))

palindromes.sort()
print(palindromes[-1])


# Solution 2
num = 0
palindromes = []
for i in range(100, 1000):
    for j in range(100, 1000):
        num = i * j
        if str(num) == str(num)[::-1]:
            palindromes.append(num)
print(max(palindromes))

# Smallest multiple


# Solution 1
from collections import Counter

from primePy import primes


def find_primes(n):
    prime_factors = Counter()
    for i in primes.upto(n):
        while n % i == 0:
            n /= i
            prime_factors[i] += 1
    return prime_factors


factors = Counter()
for i in range(2, 21):
    _factors = find_primes(i)
    for p in _factors:
        factors[p] = max(_factors[p], factors[p])

ans = 1
for p in factors:
    ans *= p ** factors[p]

print(ans)


# Solution 2
num = 200000000
while True:
    j = 1
    for k in range(2, 21):
        if num % k:
            j = 0
            break
    if j == 1:
        print(num)
        break
    num += 1

# Sum square difference


# Solution 1
a = 0
b = 0

for i in range(1, 101):
    a = a + pow(i, 2)

for i in range(1, 101):
    b = b + i
b = pow(b, 2)

print(b - a)

# 10001st prime


# Solution 1
num = 2
primes = []


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


while len(primes) != 10001:
    if is_prime(num) == True:
        primes.append(num)
    num = num + 1
print(primes[10000])


# Solution 2
from primePy import primes

a = primes.first(10001)
print(a[-1])

# Largest product in a series


# Solution 1
digits = []
products = []

num = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""
num = num.replace("\n", "")

for char in num:
    digits.append(char)


def first_numbers(n):
    for i in range(1000):
        if i + n > 1000:
            break

        product = 1
        for o in range(n):
            product *= int(digits[i + o])

        products.append(product)

    return max(products)


print(first_numbers(13))

# Special Pythagorean triplet


# Solution 1
solved = False

for a in range(1, 1000):
    for b in range(1, 1000 - a):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a * b * c)
            solved = True
            break
    if solved:
        break

# Longest Collatz sequence


# Solution 1
from tqdm import tqdm


def chain(num):
    items = 1
    while num != 1:
        if num % 2 == 1:
            num = 3 * num + 1
        else:
            num = num / 2
        items += 1
    return items


max_items = 0
n = 0

for i in tqdm(range(1, 1000000)):
    items = chain(i)
    if items > max_items:
        max_items = items
        n = i

print(n)