import math

def multiple35(n):
    n3 = (n - 1) // 3
    sum3 = 3 * n3 * (n3 + 1) // 2
    n5 = (n - 1) // 5
    sum5 = 5 * n5 * (n5 + 1) // 2
    n15 = (n - 1) // 15
    sum15 = 15 * n15 * (n15 + 1) // 2
    return sum3 + sum5 - sum15

print(multiple35(1000))

"""
Explanation: Problem 1 - Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
End of explanation
"""


def fib(limit):
    a = 1
    b = 2
    while b <= limit:
        a, b = b, a + b
    return [a, b]

"""
Explanation: Problem 2 - Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
End of explanation
"""


def even_sum(limit):
    a, b = fib(limit)
    if a % 2:
        if b % 2:
            ## odd, odd
            return (b - 1) // 2
        ## odd, even
        return (a - 1) // 2
    ## even, odd
    return (a + b - 1) // 2 

fib(100)

even_sum(100)

print(even_sum(4000000))

"""
Explanation: While k = 1, 2, 3...
F(3k - 2) and F(3k): odd value items
F(3k - 1): even value items
F(2) +     F(5) +        F(8) +        ... + F(3k - 1)                (even values = SE(3k - 1))
= 1 + F(1) + F(3) + F(4) + F(6) + (F7) + ... + F(3k - 3) + F(3k - 2)    (odd values + 1)
Add up:
2 * SE(3k - 1) = 1 + F(1) + F(2) + ... + F(3k - 1) = 1 + S(3k - 1) = F(3k + 1) - 1
SE(3k - 1) = (F(3k + 1) - 1) / 2
End of explanation
"""


def check_divisor(n, i):
    while not n % i:
        n //= i
    return n

def largest_prime_factor(n):
    n = check_divisor(n, 2)
    if n == 1:
        return 2
    i = 3
    while i <= math.sqrt(n):
        n = check_divisor(n, i)
        i += 2
    if n > 2:
        return n
    return i - 2

print(largest_prime_factor(600851475143))

"""
Explanation: Problem 3 - Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
End of explanation
"""


def isPal(s):
    return s == s[::-1]

def firstPal(n):
    

def largestPal(n):
    for i in range(100, 1000):
        if n % i == 0 and n / i >= 100 && n / i < 1000:
            return n
    return largestPal(firstPal(n - 1))

# pals = []
# for num in range(101101, 1000000):
#     if not isPal(str(num)):
#         continue
#     for i in range(100, int(math.sqrt(num) + 1)):
#         if num / i > 999:
#             continue
#         if num % i == 0:
#             pals.append(num)
#             break;

# pals = []
# for i in range(100, 1000):
#     for j in range(100, 1000):
#         ij = i * j
#         if isPal(str(ij)):
#             pals.append(ij)

n = 1000000

print(max([pal for pal in pals if pal < n]))

"""
Explanation: Problem 4 - Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
End of explanation
"""


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def smallest_multiple(n):
    s_m = 1
    for num in range(1, n + 1):
        s_m = lcm(s_m, num)
    return s_m

print(smallest_multiple(20))

"""
Explanation: Problem 5 - Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
End of explanation
"""


def sum_square_diff(n):
    return n * (n + 1) * (n - 1) * (3 * n + 2) // 12

print(sum_square_diff(100))

"""
Explanation: Problem 6 - Sum square difference
The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 55^2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Sol
1^2 + 2^2 + ... + n^2 = n * (n + 1) * (2 * n + 1) / 6  
1 + 2 + ... + n = n * (n + 1) /2  
difference = n * (n + 1) * (n - 1) * (3 * n + 2) / 12
End of explanation
"""


