{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Factorials\n",
    "\n",
    "Let's compute $n! = 1\\times 2\\times 3\\times 4....\\times n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fact(n):\n",
    "    res = 1\n",
    "    for i in range(1, n+1):\n",
    "        res *= i\n",
    "        \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Trailing zeros\n",
    "\n",
    "Suppose we'd like to count up the number of *trailing zeros* in $n!$ -- the zeros at the end of the number. Here is the strategy:\n",
    "\n",
    "* Compute fact_n = n!\n",
    "* Keep dividing fact_n by 10 while it's divisible by 10\n",
    "* The number of times that res could be divided by 10 is the number of trailing zeros in n!\n",
    "\n",
    "(Note that dividing a number by 10 is the same as removing one trailing zero.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def trailing_zeros(n):\n",
    "    \n",
    "    fact_n = fact(n)\n",
    "    \n",
    "    counter = 0\n",
    "    \n",
    "    while fact_n % 10 == 0:\n",
    "        fact_n //= 10\n",
    "        counter += 1\n",
    "        \n",
    "    return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "124"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trailing_zeros(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have set up a counter variable, which is incremented every time we divide `fact_n` by 10 (i.e., remove a trailing 0.\n",
    "\n",
    "What happens if n! has no trailing 0s? We simply never enter the `while`-loop, and return 0, which is the correct thing."
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}