{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f6ad1b47",
   "metadata": {},
   "source": [
    "# [Counting Rectangles](https://projecteuler.net/problem=85)\n",
    "\n",
    "Let $R(m, n)$ give the number of rectangles contained in an $m \\times n$ grid. We will derive a simple formula for $R$. First, observe that an $m \\times 1$ grid contains $\\frac{m(m+1)}{2}$ rectangles, i.e.\n",
    "$$R(m, 1) = \\frac{m(m+1)}{2}$$\n",
    "(You could prove this [inductively](https://en.wikipedia.org/wiki/Mathematical_induction) if you really wanted to).\n",
    "\n",
    "Then, we can derive the following recursive formula for $R$.\n",
    "$$R(m, n) = R(m, n - 1) + n R(m, 1)$$\n",
    "To make sense of this formula, consider that the number of rectangles in an $m \\times n$ grid must be the sum of the number of rectangles in an $m \\times (n-1)$ grid (i.e. $R(m, n-1)$) and the number of rectangles in an $m \\times n$ grid *that are at least partially in the bottom row* - these are [disjoint sets](https://en.wikipedia.org/wiki/Disjoint_sets), so there's no double counting with this approach. We already know the number of rectangles that lie *entirely* in the bottom row - it's just $R(m, 1)$. We can then make any of those rectangles any height we want between 1 and $n$, giving the formula $n R(m, 1)$.\n",
    "\n",
    "At this point, we could easily translate this into a recursive function to compute $R$, but we can also simplify this into a closed formula. Substituting the formula for $R(m,1)$ from above, we get\n",
    "$$R(m, n) = R(m, n - 1) + \\frac{mn(m+1)}{2}$$\n",
    "Then, by repeatedly substituting $R(m, n-1)$ with our recursive formula, we get\n",
    "$$R(m, n) = \\frac{mn(m+1)}{2} + \\frac{m(n-1)(m+1)}{2} + \\frac{m(n-2)(m+1)}{2} + \\cdots + \\frac{m(m+1)}{2} = \\sum_{k=1}^n \\frac{mk(m+1)}{2}$$\n",
    "Applying some [summation identities](https://en.wikipedia.org/wiki/Summation) (also see [problem 1](https://projecteuler.net/problem=1)), this simplifies to\n",
    "$$R(m, n) = \\frac{mn(m+1)(n+1)}{4}$$\n",
    "Interestingly, this formula is really just the product of $m$th and $n$th [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2c2038a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def R(m, n):\n",
    "    return m * n * (m + 1) * (n + 1) // 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f29eaf82",
   "metadata": {},
   "source": [
    "Figuring out the formula's the hard part - now we can just iterate over grid sizes to calculate how many rectangles they have."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3409e88c",
   "metadata": {},
   "outputs": [],
   "source": [
    "totals = dict()\n",
    "\n",
    "for x in range(1, 2001):\n",
    "    for y in range(1, 2001):\n",
    "        r = R(x, y)\n",
    "        totals[(x,y)] = r\n",
    "        if r > 2000000:\n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9ce5480",
   "metadata": {},
   "source": [
    "We'll figure out which grid is the closest to containing 2000000 rectangles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "dbc72aaa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(36, 77)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m, n = min(totals, key=lambda x: abs(totals[x] - 2000000))\n",
    "m, n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e69c5c48",
   "metadata": {},
   "source": [
    "The area of that grid is our answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f230a0d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2772"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m * n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d30d6d4f",
   "metadata": {},
   "source": [
    "## Relevant sequences\n",
    "* Number of rectangles in an $m \\times n$ grid: [A098358](https://oeis.org/A098358)\n",
    "\n",
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}