'''
Group Members
=============
'''

userids = ['Thormundur15','Ernir17'] # fill in this array with strings of usernames
def m1p1(n):
    '''Project Euler Problem 1
Given a positive integer n calculate the sum of all multiples of 3 and 5 less than n.
    '''
    multiple_of_3 = [3*i for i in range(1,n) if 3*i < n]
    multiple_of_5 = [5*i for i in range(1,n) if 5*i < n]
    multiple_of_15 = [15*i for i in range(1,n) if 15*i < n]
    return (sum(multiple_of_3 + multiple_of_5) - sum(multiple_of_15))

def m1p2(n):
    '''Project Euler Problem 2.
Given a positive integer n find the sum of the even valued Fibonacci numbers less than n.
    '''
    if (n < 2) :
        return 0
    num1 = 0
    num2 = 2
    sum = num1 + num2
    while ((4 * num2 + num1) <= n) :
        num3 = 4 * num2 + num1
        num1 = num2
        num2 = num3
        sum = sum + num2

    return sum

def m1p3(n):
    '''Project Euler Problem 3.
Given an positive integer n find the largest prime factor of n
    '''
    max = -1
    while(n%2==0):
        max = 2
        n /= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while(n%i==0):
            max = i
            n /= i
    if(n > 2):
        max = n
    return int(max)

def m1p4(n):
    '''Project Euler Problem 4.
Given a positive integer n. Find the largest palindrome made from the product of two n digit numbers
    '''
    plaindormes = []
    plaindormes.append(9)
    for i in range(10**(n-1), (10**n)):
        for j in range(10**(n-1), (10**n)):
            num = str(i * j)
            if len(num) == n*2:
                for k in range(0, n):
                    if(num[k] != num[len(num)-1-k]):
                        break
                else:
                    plaindormes.append(i*j)
    return max(plaindormes)

def m1p5(n):
    '''Project Euler Problem 5.
Given a positive integer n. Find the smallest positive number evenly divisible by all numbers from 1 to n
    '''
    i = n
    n = n-1
    while (n != 0) :
        i = n * i / gcd(n, i)
        n = n - 1
    return i

def m1p6(n):
    '''Project Euler Problem 6.
Given a positive integer n. Find the difference between the square of the sum and the sum of the squares of the
first n natural numbers
    '''
    i = 0
    p = 0
    for x in range(1, n+1):
        i = i + x
        p = p + x**2
    i = i**2
    return i - p

def m1p7(n):
    '''Project Euler Problem 7.
Given a positive integer n. Find the nth Prime.
    '''
    P = Primes()
    return P.unrank(n-1)

def m1p8(n,k):
    '''Project Euler Problem 8.
Given positive integers n and k. Find the greatest product of k adjacent digits in n.
    '''
    Biggest = 0
    numStr = str(n)
    for i in range(0, len(numStr)-k):
        cnt = 0
        val = int(numStr[i])
        for j in range(0, k-1):
            val = val * int(numStr[i+j+1])
        if(val > Biggest):
            Biggest = val
    return Biggest

def m1p9(n):
    '''Project Euler Problem 9.
Given a positive integer n. Find a Pythagorean triple such that a+b+c=n
    '''
    for i in range(1, n/3 + 1):
        for j in range(i+1, n/2 + 1):
            c = n - i - j
            if(i*i + j*j == c*c):
                return (i,j,c)

def m1p10(n):
    '''Project Euler Problem 10.
Given a positive integer n. Find the sum of all primes less than n.
    '''
    P = Primes()
    i = P.first()
    nSum = 0
    while (i < n):
        nSum = nSum + i
        i = P.next(i)
    return nSum

def m1p11(M,k):
    '''Project Euler Problem 11.
Given a matrix m (as a list of lists) and integer k. Find the greatest product of k vertical, horizontal, or diagonal entries in m.
    '''

    greatest = 0
    for i in range(0, len(M)):
        for j in range(0, len(M)):
            val1 = 1
            val2 = 1
            val3 = 1
            val4 = 1
            for p in range(0, k):
                if(j<len(M)-k+1):
                    val1 = val1 * M[i][j+p]
                if(i<len(M)-k+1):
                    val2 = val2 * M[i+p][j]
                if(i<len(M)-k+1 and j<len(M)-k+1):
                    val3 = val3 * M[i+p][j+p]
                if(i<len(M)-k+1 and j>=k-1):
                    val4 = val4 * M[i+p][j-p]

            val = max(val1, val2, val3, val4)
            if(val > greatest):
                greatest = val
    return greatest

def m1p12(n):
    '''Project Euler Problem 12.
Given an integer n. Find the smallest triangular number with more than n divisors.
    '''

    def divisors(Num):
        limit = int(sqrt(Num))
        NumDiv = 0
        for i in range(1, limit):
            if Num % i == 0:
                limit = Num / i
                if limit != i:
                    NumDiv += 1
                NumDiv += 1
        return NumDiv

    for i in range(1, 65535):
        Num = i * (i + 1) >> 1
        NumDiv = divisors(Num)

        if NumDiv >= n:
            return int(Num)


def m1p13(L,k):
    '''Project Euler Problem 13.
Given a list L of integers and an integer k. Find the first k digits of the sum of the elements of L.
    '''
    ANS = sum(L)
    return int(str(ANS)[:k])

def m1p14(n):
    '''Project Euler Problem 14.
Which starting number under n produces the longest Collatz chain.
    '''
    return 0
    ''':/'''
def m1p15(n,m):
    '''Project Euler Problem 15.
How many paths are there with only steps right and down through an n*m grid.
If you use a mathematical formula as a shortcut in your solution, then justify
why it can be used.
    '''
    return 0
''':/'''