euler_hack_012.ipynb

euler_hack_012.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Euler Hack #12 (2017-08-28)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%reload_ext Cython\n",
    "# %%cython\n",
    "\n",
    "import io\n",
    "import re\n",
    "import csv\n",
    "import json\n",
    "import time\n",
    "import math\n",
    "import random\n",
    "import numbers\n",
    "import decimal\n",
    "import fractions\n",
    "import statistics\n",
    "import collections\n",
    "import operator as op\n",
    "import itertools as it\n",
    "import functools as ft"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Problem 6 - Sum square difference\n",
    " \n",
    "The sum of the squares of the first ten natural numbers is,\n",
    "\n",
    "1^2 + 2^2 + ... + 10^2 = 385\n",
    "The square of the sum of the first ten natural numbers is,\n",
    "\n",
    "(1 + 2 + ... + 10)^2 = 55^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": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "385"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(n ** 2 for n in range(1, 11))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3025"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "55 ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3025"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(n for n in range(1, 11)) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25164150"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(sum(n for n in range(1, 101)) ** 2) - sum(n ** 2 for n in range(1, 101))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with io.open(\"./share/p089_roman.txt\") as fh:\n",
    "    lines = fh.read().splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['MMMMDCLXXII',\n",
       " 'MMDCCCLXXXIII',\n",
       " 'MMMDLXVIIII',\n",
       " 'MMMMDXCV',\n",
       " 'DCCCLXXII',\n",
       " 'MMCCCVI',\n",
       " 'MMMCDLXXXVII',\n",
       " 'MMMMCCXXI',\n",
       " 'MMMCCXX',\n",
       " 'MMMMDCCCLXXIII']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lines[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "roman_conver=[  (1,'I'),\n",
    "                (5,'V'),\n",
    "                (10,'X'),\n",
    "                (50,'L'),\n",
    "                (100,'C'),\n",
    "                (500,'D'),\n",
    "                (1000,'M'),\n",
    "                    ]\n",
    "def roman_to_int(roman):\n",
    "    tot = 0\n",
    "    for i in range(0,len(roman)):\n",
    "        for each in roman_conver:\n",
    "            if roman[i]==each[1]:\n",
    "                if each[0]>tot:\n",
    "                    tot = each[0] - tot\n",
    "                else:\n",
    "                    tot = tot + each[0]\n",
    "    return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def int_to_roman(input):\n",
    "    result = \"\"\n",
    "    nums = ('M', 'D', 'C', 'L', 'X', 'V', 'I')\n",
    "    ints = (1000, 500, 100, 50,  10,  5,   1)\n",
    "    places = [0,] * len(nums)\n",
    "    # count how many times each int we have\n",
    "    for i in range(len(ints)):\n",
    "        value = ints[i]\n",
    "        count = input // value\n",
    "        places[i] = count\n",
    "        if count: input -= count * value\n",
    "    # Format the output string\n",
    "    for i in range(len(places)):\n",
    "       if places[i] < 4:\n",
    "           result += nums[i] * places[i]\n",
    "       else:\n",
    "         # 4 repetitions means we're trying to represent 4 or 9\n",
    "         # of something.\n",
    "         if places[i -1] == 0:\n",
    "            # it's a 4.\n",
    "            result += nums[i] + nums[i -1]\n",
    "         else:\n",
    "            # it's a 9.\n",
    "            # 'the next' character is 2 away from here, not 1;\n",
    "            # otherwise we'd get 'IV' when we want 'IX'.\n",
    "            # We'll also need to delete the previous character,\n",
    "            # or we'll get stuff like 'VIX' when we want 'IX'.\n",
    "            result = result[:-1] + nums[i] + nums[i -2]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "numeral_map = tuple(zip(\n",
    "    (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1),\n",
    "    ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')\n",
    "))\n",
    "\n",
    "def int_to_roman(i):\n",
    "    result = []\n",
    "    for integer, numeral in numeral_map:\n",
    "        count = i // integer\n",
    "        result.append(numeral * count)\n",
    "        i -= integer * count\n",
    "    return ''.join(result)\n",
    "\n",
    "def roman_to_int(n):\n",
    "    i = result = 0\n",
    "    for integer, numeral in numeral_map:\n",
    "        while n[i:i + len(numeral)] == numeral:\n",
    "            result += integer\n",
    "            i += len(numeral)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "743"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "savings = 0\n",
    "\n",
    "for line in lines:\n",
    "    num = roman_to_int(line)\n",
    "    assert num == roman_to_int(int_to_roman(num)), line\n",
    "    savings += len(line) - len(int_to_roman(num))\n",
    "\n",
    "savings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 288 - An enormous factorial\n",
    "\n",
    "For any prime p the number N(p,q) is defined by N(p,q) = ∑n=0 to q Tn*p^n\n",
    "with Tn generated by the following random number generator:\n",
    "\n",
    "    S0 = 290797\n",
    "    Sn+1 = Sn^2 mod 50515093\n",
    "    Tn = Sn mod p\n",
    "\n",
    "Let Nfac(p,q) be the factorial of N(p,q).\n",
    "\n",
    "Let NF(p,q) be the number of factors p in Nfac(p,q).\n",
    "\n",
    "You are given that NF(3,10000) mod 3^20=624955285.\n",
    "\n",
    "Find NF(61,10^7) mod 61^10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import math\n",
    "\n",
    "cdef N(long long p, long long q):\n",
    "    cdef long long Tn\n",
    "    cdef long long Sn = 290797\n",
    "    res = 0\n",
    "    pn = 1\n",
    "    \n",
    "    for n in range(0, q + 1):\n",
    "        Tn = Sn % p\n",
    "        Sn = (Sn * Sn) % 50515093\n",
    "        res += (Tn * pn)\n",
    "        pn = (pn * p)\n",
    "        \n",
    "    return res\n",
    "\n",
    "\n",
    "def NF(p, q, maxres):\n",
    "    n = N(p, q)\n",
    "    n_base_p = math.log(n) / math.log(p)\n",
    "    print(n_base_p)\n",
    "    cdef long long res = 0\n",
    "    while n >= p:\n",
    "        n = n // p\n",
    "        res = (res + n) % maxres\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N(3, 10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 244 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit NF(3, 10000, maxres=3 ** 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9999.26875717439\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "624955285"
      ]
     },
     "execution_count": 184,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NF(3, 10000, maxres=3 ** 20)\n",
    "# 624955285"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "177851684271204367"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NF(61, 10**4, maxres=61 ** 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "95.37971091270447\n"
     ]
    }
   ],
   "source": [
    "t0 = time.time()\n",
    "NF(61, 10**5, maxres=61**10)\n",
    "print(time.time() - t0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 9.56 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit N(61, 10**5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}