euler.ipynb

environment.yml

channels:
  - defaults
dependencies:
  - ipython
  - ipywidgets
  - matplotlib
  - numpy

euler.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "euler.ipynb",
      "provenance": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyOlLzb+XKSxP7lxJIPLdjru",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/franknoh/7382d29e42eb7b4445f4210023456b38/euler.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WG1J3TXTROq_"
      },
      "source": [
        "# [Problem 1](https://projecteuler.net/problem=1)\n",
        "\n",
        "**Multiples of 3 and 5**\n",
        "\n",
        "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",
        "\n",
        "* `Answer: 233168`"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sUCdDTgYRX5_",
        "outputId": "079759c0-ccf3-4036-9b77-41a05df4a5a7"
      },
      "source": [
        "from math import *\n",
        "def euler(n):\n",
        "    n -= 1\n",
        "    res = 0\n",
        "    res += 3*floor(n/3)*(floor(n/3)+1)/2\n",
        "    res += 5*floor(n/5)*(floor(n/5)+1)/2\n",
        "    res -= 15*floor(n/15)*(floor(n/15)+1)/2\n",
        "    print(res)\n",
        "\n",
        "euler(1000)"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "233168.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wSLg8xLBRgCr"
      },
      "source": [
        "#[Problem 2](https://projecteuler.net/problem=2)\n",
        "\n",
        "**Even Fibonacci numbers**\n",
        "\n",
        "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",
        "\n",
        "* `Answer: 4613732`"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5pFQK9EMRgbb",
        "outputId": "eb258036-7b78-4eb3-db10-aad9ddf806d4"
      },
      "source": [
        "from utlis import *\n",
        "\n",
        "def euler(n):\n",
        "    res=0\n",
        "    i=1\n",
        "    while fibo(i)<n:\n",
        "        if fibo(i)%2==0:\n",
        "            res += fibo(i)\n",
        "        i+=1\n",
        "    print(res)\n",
        "\n",
        "euler(4000000)"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4613732\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yUblsWiyTqmm"
      },
      "source": [
        "#[Problem 3](https://projecteuler.net/problem=3)\n",
        "\n",
        "**Largest prime factor**\n",
        "\n",
        "The prime factors of 13195 are 5, 7, 13 and 29.\n",
        "\n",
        "What is the largest prime factor of the number 600851475143 ?\n",
        "\n",
        "* `Answer:  6857`\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "U9JMI6uXUO69",
        "outputId": "a37b7d7f-b185-4309-df7e-9a4dfe543d52"
      },
      "source": [
        "from utlis import *\n",
        "\n",
        "def euler(n):\n",
        "    print(factors(n).pop())\n",
        "\n",
        "euler(600851475143)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6857\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_Mwemd2gUidn"
      },
      "source": [
        "#[Problem 4](https://projecteuler.net/problem=4)\n",
        "\n",
        "**Largest palindrome product**\n",
        "\n",
        "\n",
        "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",
        "\n",
        "\n",
        "* `Answer:  906609`"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pL_HzaU-WoUh",
        "outputId": "de30c7dc-f9a7-438c-d66c-63b40196696f"
      },
      "source": [
        "def euler():\n",
        "    max_res = 0\n",
        "    for x in range(100,1000):\n",
        "        for y in range(100,1000):\n",
        "            t = list(str(x * y))\n",
        "            re_t = list(reversed(t))\n",
        "            if t[:3] == re_t[:3] and int(''.join(t)) > max_res:\n",
        "                max_res = int(''.join(t))\n",
        "    print(max_res)\n",
        "\n",
        "euler()"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "906609\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xF7RKwZQWQ-S"
      },
      "source": [
        "# [Problem 5](https://projecteuler.net/problem=5)\n",
        "\n",
        "**Smallest multiple**\n",
        "\n",
        "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",
        "\n",
        "\n",
        "* `Answer:  232792560`"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zqZE1PPKWpdD",
        "outputId": "8e4f84e3-ca19-47b6-e312-b1325222152b"
      },
      "source": [
        "def euler():\n",
        "    print(2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19)\n",
        "euler()"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "232792560\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}

utlis.py

import math

def nPrime(n):
    start = 2
    count = 0
    while True:
        if all([start % i for i in range(2, int(math.sqrt(start)) + 1)]) != 0:
            count += 1
            if count == n:
                return start
        start += 1 

def pList(n):
    prime = []
    p = 2
    while True:
        flag = 1
        if p % 2 == 0 and p != 2:
            flag = 0
        if flag  == 1:
            for each in prime:
                if p % each == 0:
                    flag = 0
            if flag == 1:
                prime.append(p)
        if prime[len(prime)-1] >= n:
            break
        p+=1
    return prime

def factors(n):
    res=[]
    while n % 2 == 0:
        res.append(2),
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2):
        while n % i== 0:
            res.append(i),
            n = n / i
    if n > 2:
        res.append(n)
    return res

def nFactorial(n):
    return n * nFactorial(n-1) if n > 1 else 1

def fibo(n):
    if n <= 2: return 1
    else: return fibo(n-2) + fibo(n-1)