Honors_algo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Honors Assignment: Project Euler problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "******\n",
    "**Euler46** *Goldbach's other conjecture*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5777\n"
     ]
    }
   ],
   "source": [
    "n = 9\n",
    "memo_primes = [2,3,5,7]\n",
    "\n",
    "def prime(i):\n",
    "    for p in memo_primes:\n",
    "        if(i % p == 0):\n",
    "            return False\n",
    "    return True\n",
    "def check(i):\n",
    "    for k in range(1,i):#sqrt\n",
    "        if (i-2*k*k) in memo_primes:\n",
    "            return False\n",
    "    return True\n",
    "while True:\n",
    "    if prime(n):\n",
    "        memo_primes.append(n)\n",
    "    else:\n",
    "        if check(n):\n",
    "            break\n",
    "    n += 2 #could be optimized to +2 +4 +2 +4...\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simple search problem. An odd number(>=3) could be prime number. We add it to list of prime numbers if it is one, otherwise we check if there is any k for which i-2kk is a prime number, if there is one we move on, if not, we've found our very first number that breaks Goldbach's other conjecture."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler47** *Distinct primes factors*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "134043\n"
     ]
    }
   ],
   "source": [
    "def prime_factors_count(n):\n",
    "    i = 2\n",
    "    factors = []\n",
    "    while(i * i <= n):\n",
    "        if(n % i != 0):\n",
    "            i += 1\n",
    "        else:\n",
    "            n /= i\n",
    "            factors.append(i)\n",
    "    if(n > 1):\n",
    "        factors.append(n)\n",
    "    return len(set(factors))\n",
    "i = 16 #2*2*2*2\n",
    "while True:\n",
    "    if(prime_factors_count(i)==4):\n",
    "        if(prime_factors_count(i+1)==4):\n",
    "            if(prime_factors_count(i+2)==4):\n",
    "                if(prime_factors_count(i+3)==4):\n",
    "                    print(i)\n",
    "                    break\n",
    "                else:\n",
    "                    i+=4\n",
    "            else:\n",
    "                i+=3\n",
    "        else:\n",
    "            i+=2\n",
    "    else:\n",
    "        i+=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another search problem. Could be optimized by memoizing prime factors but would take more space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler53** *Combinatoric selections*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4075\n"
     ]
    }
   ],
   "source": [
    "from math import factorial as fac\n",
    "def binomial(c, r):\n",
    "    outp = fac(c) // fac(r) // fac(c - r)\n",
    "    return outp\n",
    "flag = 0\n",
    "for i in range(1,101):\n",
    "    for j in range(1,i):\n",
    "        if (binomial(i,j)>1000000):\n",
    "            flag +=1\n",
    "print(flag)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I first tried using my C++ code from the problem nCr table from contest 2 which uses memoization. It didn't give accurate output as some values were too big to be stored in *unsigned long long int*. The code above doesn't use memoization. It computes binomial(n,r) through the use of factorials which is costly but leads to an easily readble code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler114** *Counting block combinations I*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16475640049\n"
     ]
    }
   ],
   "source": [
    "m = 3\n",
    "n = 50\n",
    "ways = [0]*(n+1)\n",
    "sum_so_far = [0]*(n+1)\n",
    "ways[0] = ways[1] = ways[2] = 1\n",
    "sum_so_far[0] = 1\n",
    "sum_so_far[1] = 2\n",
    "sum_so_far[2] = 3\n",
    "for i in range(m, n+1):\n",
    "    ways[i] = ways[i-1] + sum_so_far[i-m-1] + 1\n",
    "    sum_so_far[i] = sum_so_far[i-1] + ways[i]\n",
    "print(ways[n])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This line of code **ways[i] = ways[i-1] + sum_so_far[i-m-1] + 1** is where the magic happens. In order to compute the number of ways we can fill a row of length i, we add the number of ways of filling the i-1th row(fill the rest with black blocks) to the total number of making all rows with a length that is smaller or equal to i-m(fill the rest with red blocks) to 1(an all red row)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler115** *Counting block combinations II*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "168\n"
     ]
    }
   ],
   "source": [
    "m = 50\n",
    "ways = []\n",
    "sum_so_far = []\n",
    "\n",
    "for i in range(m):\n",
    "    ways.append(1)\n",
    "\n",
    "for i in range(m):\n",
    "    sum_so_far.append(i+1)\n",
    "i = 50\n",
    "while(True):\n",
    "    t = 0\n",
    "    if i-m-1<0:\n",
    "        t = 0\n",
    "    else:\n",
    "        t = sum_so_far[i-m-1]\n",
    "    if ((ways[i-1] + t + 1)>1000000):\n",
    "        break;\n",
    "    ways.append(ways[i-1] + t + 1)\n",
    "    sum_so_far.append(sum_so_far[i-1] + ways[i])\n",
    "    i += 1\n",
    "print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem is just a variation of the previous problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler116** *Red, green or blue tiles*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20492570929\n"
     ]
    }
   ],
   "source": [
    "def Ways(n,i):\n",
    "    ways = [0]*(n+1) #allocate the array\n",
    "    for j in range(i):\n",
    "        ways[j] = 1 #set the first i elements to 1\n",
    "    for j in range(i, n+1):\n",
    "        ways[j] = ways[j-1] + ways[j-i]\n",
    "    return ways[n] - 1 #delete the all empty case\n",
    "\n",
    "n = 50\n",
    "c = [2,3,4]\n",
    "ways = 0\n",
    "for i in c:\n",
    "    ways += Ways(n,i)\n",
    "print(ways)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem is similar to problem114 except that we have to compute the number of ways for different colored lengths as well as exclude the all black rows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "**Euler117** *Red, green and blue tiles*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100808458960497\n"
     ]
    }
   ],
   "source": [
    "n = 50\n",
    "ways = [0]*(n+1)\n",
    "ways[0] = 1\n",
    "for i in range(1, n+1):\n",
    "    temp = i - 4\n",
    "    if(temp < 0):\n",
    "        temp = 0\n",
    "    Sum = 0\n",
    "    for j in range(temp,i):\n",
    "        Sum += ways[j]\n",
    "    ways[i] = Sum\n",
    "print(ways[n])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we can have multiple length(colors) mixed up in one row. This is similar to the coin change problem we've seen except that (e.g) {3,1,1} would count as 3 ways since it can be represented as{3,1,1}, {1,3,1},{1,1,3}."
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}