project_euler_01.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 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.\n",
    "\n",
    "Find the sum of all the multiples of 3 or 5 below 1000.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of all the multiples of 3 or 5 below 1000 is : 233168\n"
     ]
    }
   ],
   "source": [
    "def find_multiple(number):\n",
    "    n=0\n",
    "    for i in range(1,number):\n",
    "        if i % 3 == 0 or i % 5 == 0:\n",
    "            n +=i\n",
    "        \n",
    "    return n\n",
    "number=1000\n",
    "print(f'The sum of all the multiples of 3 or 5 below {number} is : {find_multiple(number)}')        \n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 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:\n",
    "\n",
    "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
    "\n",
    "By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of all even-valued fibonacci numbers lower than 4000000 is: 4613732\n"
     ]
    }
   ],
   "source": [
    "def fibonacci_sum(n):\n",
    "    sum,x,y=0,0,1\n",
    "    while True:\n",
    "        x,y=y,x+y\n",
    "        if x%2==0:\n",
    "            sum +=x\n",
    "        if sum>=n:\n",
    "            break\n",
    "\n",
    "    return sum\n",
    "\n",
    "# Change next line for different results\n",
    "n = 4000000\n",
    "print(f'The sum of all even-valued fibonacci numbers lower than {n} is:',fibonacci_sum(n))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. The prime factors of 13195 are 5, 7, 13 and 29.\n",
    "\n",
    "What is the largest prime factor of the number 600851475143 ?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The largest prime factor of the number 600851475143 is 6857\n"
     ]
    }
   ],
   "source": [
    "def factor(n):\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        if n % i > 0:\n",
    "            i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "    return n\n",
    "\n",
    "# Change next line for different results\n",
    "n = 600851475143\n",
    "print(f'The largest prime factor of the number {n} is {factor(n)}')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.\n",
    "\n",
    "Find the largest palindrome made from the product of two 3-digit numbers.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The largest palindrome made from the product of two 2-digit numbers is 906609 = 913 * 993 \n"
     ]
    }
   ],
   "source": [
    "def palindrome(x, y):\n",
    "    largeest_palindrome = 0\n",
    "    for i in range(1, x + 1):\n",
    "        for j in range(1, y + 1):\n",
    "            palindrome = i * j\n",
    "            if str(palindrome) == str(palindrome)[::-1]:\n",
    "                if largeest_palindrome < palindrome:\n",
    "                    largeest_palindrome = palindrome\n",
    "                    a,b=i,j\n",
    "    return largeest_palindrome,a,b\n",
    "# Change x and y for different results\n",
    "x = 999\n",
    "y = 999\n",
    "result=palindrome(x,y)\n",
    "print(f'The largest palindrome made from the product of two 2-digit numbers is {result[0]} = {result[1]} * {result[2]} ')\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.\n",
    "\n",
    "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The smallest positive number that is evenly divisible by all of the numbers from 1 to 20 is:232792560\n"
     ]
    }
   ],
   "source": [
    "def check_num(n, n_divisible):\n",
    "    n -=1\n",
    "    while True:\n",
    "        if n_divisible % n > 0:\n",
    "            return False\n",
    "        else:\n",
    "            if n > 2:\n",
    "                n -= 1\n",
    "            else:\n",
    "                break\n",
    "    return True\n",
    "\n",
    "def increment(n):\n",
    "    number = n\n",
    "    while True:\n",
    "        if check_num(n, number):\n",
    "            break\n",
    "        else:\n",
    "            number += n\n",
    "    return number\n",
    "# Modify limit to  check a different number(it is efficient under 23)\n",
    "# limit =  22 result is   232 792 560\n",
    "# limit =  22 result is 5 354 228 880\n",
    "limit=20\n",
    "\n",
    "print(f'The smallest positive number that is evenly divisible by all of the numbers from 1 to {limit} is:{increment(limit)}')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385\n",
    "\n",
    "The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)^2 = 3025\n",
    "\n",
    "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\n",
    "\n",
    "Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The difference between the sum of the squares of the first 100 natural numbers and the square of the sum is: 25164150\n"
     ]
    }
   ],
   "source": [
    "def difference(n):\n",
    "    sum1,sum2=0,0\n",
    "    for i in range(1,n+1):\n",
    "        sum1 +=i**2\n",
    "        sum2 += i\n",
    "    return sum2**2-sum1\n",
    "# Modify l to check a different number.\n",
    "l=100\n",
    "print(f'The difference between the sum of the squares of the first {l} natural numbers and the square of the sum is: {difference(l)}')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.\n",
    "\n",
    "What is the 10001st prime number?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The 10001st prime number is: 104743\n"
     ]
    }
   ],
   "source": [
    "# This example use brute force and is not as efficient as number 9 example which use Sieve of Eratosthenes algorithm\n",
    "def prime(n):\n",
    "    count=0\n",
    "    num=2\n",
    "    prime_num=1\n",
    "    prime_list=[]\n",
    "    while True:\n",
    "        prime = True\n",
    "        for j in range(2, num):\n",
    "            #print(j)\n",
    "            #print(num)\n",
    "            if (num % j == 0):\n",
    "                prime = False\n",
    "        if prime:\n",
    "            prime_num = num\n",
    "            count +=1\n",
    "            prime_list.append(prime_num)\n",
    "        num +=1\n",
    "        if count>=n:\n",
    "            break\n",
    "\n",
    "    print(f'The {count}st prime number is: {prime_num}')\n",
    "    # Uncomment next line to see a list of all prime numbers\n",
    "    #print('All '+ str(count)+' are: ', *prime_list, end=\" \")\n",
    "\n",
    "# Modify this line for different result\n",
    "prime(10001)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8. A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,\n",
    "a^2 + b^2 = c^2\n",
    "\n",
    "For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.\n",
    "\n",
    "There exists exactly one Pythagorean triplet for which a + b + c = 1000.\n",
    "Find the product abc.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A*B*C = 31875000\n",
      "A =  200 \n",
      "B =  375 \n",
      "C = 425\n"
     ]
    }
   ],
   "source": [
    "def pythagorean_triplet(n):\n",
    "    for a in range(1, n):\n",
    "        for b in range(a+1, n):\n",
    "            c = n - a - b\n",
    "            if a**2 + b**2 == c**2:\n",
    "                print('A*B*C =',a*b*c)\n",
    "                print('A = ',a,'\\nB = ',b,'\\nC =',c)\n",
    "                return True\n",
    "    return False\n",
    "    \n",
    "# Modify this line for different result\n",
    "n = 1000\n",
    "if not pythagorean_triplet(n):\n",
    "    print('Try a larger number')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.\n",
    "\n",
    "Find the sum of all the primes below two million.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The summ of all prime numbers lower than 2000000 is: 142913828922\n",
      "Last prime number lower than  2000000 is: 1999993\n",
      "The number of prime numbers lower than  2000000 is: 148933\n"
     ]
    }
   ],
   "source": [
    "# Using the Sieve of Eratosthenes algorithm\n",
    "def prime_algorithm(n):\n",
    "\n",
    "    # Create a list of boolean populated with True values and set first 2 values as False\n",
    "    sieve = [True] * (n+1)\n",
    "    sieve[0] = False\n",
    "    sieve[1] = False\n",
    "\n",
    "    # Set as False all elements in the list with index not a prime number.\n",
    "    for i in range(2, int(n**0.5)+1):\n",
    "        if sieve[i]:\n",
    "            for j in range(i**2, n+1, i):\n",
    "                sieve[j] = False\n",
    "\n",
    "    # Create a prime list with the indexes from sieve list that have the value True\n",
    "    primes = [i for i in range(2, n + 1) if sieve[i]]\n",
    "    return primes\n",
    "\n",
    "\n",
    "# Modify n to set another limit\n",
    "n=2000000\n",
    "prime= prime_algorithm(n)\n",
    "print(f'The summ of all prime numbers lower than {n} is:',sum(prime))\n",
    "print(f'Last prime number lower than  {n} is:',  prime[-1])\n",
    "print(f'The number of prime numbers lower than  {n} is:',len(prime))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10. The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:\n",
    "\n",
    "1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\n",
    "\n",
    "Let us list the factors of the first seven triangle numbers:\n",
    "\n",
    "     1: 1\n",
    "     3: 1,3\n",
    "     6: 1,2,3,6\n",
    "    10: 1,2,5,10\n",
    "    15: 1,3,5,15\n",
    "    21: 1,3,7,21\n",
    "    28: 1,2,4,7,14,28\n",
    "\n",
    "We can see that 28 is the first triangle number to have over five divisors.\n",
    "\n",
    "What is the value of the first triangle number to have over five hundred divisors?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The triangle number with more than 500 is 76576500 and it has 576 divisors.\n"
     ]
    }
   ],
   "source": [
    "# Create a list of tuples of prime numbers and their exponent\n",
    "def factorization(n):\n",
    "    factors = []\n",
    "    d = 2\n",
    "    while d ** 2 <= n:\n",
    "        count = 0\n",
    "        while not n % d:\n",
    "            count += 1\n",
    "            n //= d\n",
    "        if count > 0:\n",
    "            factors.append((d, count))\n",
    "        d += 1\n",
    "    if n > 1:\n",
    "        factors.append((n, 1))\n",
    "    return factors\n",
    "\n",
    "# count divisors of n\n",
    "def d_count(n):\n",
    "    factors = factorization(n)\n",
    "    count = 1\n",
    "    for my_tuple in factors:\n",
    "        count *= (my_tuple[1] + 1)\n",
    "    return count\n",
    "\n",
    "def triangle_div(x):\n",
    "    n = 1\n",
    "    while True:\n",
    "        # Calculate sum of all integer les than n\n",
    "        triangle = n * (n + 1) // 2\n",
    "        divisors = d_count(triangle)\n",
    "        if divisors > x :\n",
    "            print(f'The triangle number with more than {x} is {triangle} and it has {divisors} divisors.')\n",
    "            break\n",
    "        else:\n",
    "            n += 1\n",
    "\n",
    "# Modify here for different result\n",
    "triangle_div(500)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "6150d5a5fa7a7dc65b87c699d9748e7bf7c3470dd4beea6a689a9719fc5fec7b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}