eulerbooks/notebooks/problem0061.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3b0c78de",
   "metadata": {},
   "source": [
    "# [Cyclical Figurate Numbers](https://projecteuler.net/problem=61)\n",
    "\n",
    "We can easily generate all the necessary four digit polygonal numbers - there's not that many of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "be5e1782",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "299"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polygonals = {s: {polygonal_number(s, n) for n in range(0, 141) if 1000 <= polygonal_number(s, n) < 10000} for s in range(3, 9)}\n",
    "len(set.union(*polygonals.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11711bef",
   "metadata": {},
   "source": [
    "Then we can construct a graph where we add an edge between any two nodes when they are part of different polygonal sets, and the last two digits of the first number match the first two of the second."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "aa608b47",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Digraph on 286 vertices (use the .plot() method to plot)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import permutations, product\n",
    "\n",
    "G = DiGraph()\n",
    "for (U, V) in permutations(polygonals.values(), int(2)):\n",
    "    for u, v in product(U, V):\n",
    "        if u == v:\n",
    "            continue\n",
    "            \n",
    "        if u % 100 == v // 100:\n",
    "            G.add_edge(u, v)\n",
    "            \n",
    "G"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1350c55f",
   "metadata": {},
   "source": [
    "We'll search for all cycles of length six:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6dac9995",
   "metadata": {},
   "outputs": [],
   "source": [
    "candidates = [c for c in G.all_simple_cycles(max_length=6) if len(c) == 7]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4a5ffd5",
   "metadata": {},
   "source": [
    "This leaves us with a decent number of cycles, but only one of them has one of each type of polygonal number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f3362ea0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(candidates)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8e5245e",
   "metadata": {},
   "source": [
    "So, we'll filter these candidates by checking if they have one of each type of polygonal number. We need to be careful, since [every hexagonal number is also a triangular number](https://en.wikipedia.org/wiki/Polygonal_number), so our answer will have *two* triangular numbers in it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a1c2106e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_all_polygonals(c):\n",
    "    f = {n: set() for n in range(3, 9)}\n",
    "    for v in c:\n",
    "        for (i, s) in polygonals.items():\n",
    "            if v in s:\n",
    "                f[i].add(v)\n",
    "    \n",
    "    return len(f[3]) == 2 and all(len(f[n]) == 1 for n in range(4, 9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7e2c6d83",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1281, 8128, 2882, 8256, 5625, 2512, 1281]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cycles = [c for c in candidates if has_all_polygonals(c)]\n",
    "cycles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a2c6bfb",
   "metadata": {},
   "source": [
    "Only one cycle left after filtering, as expected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e5677b2f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28684"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(cycles[0][:-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d93f90a",
   "metadata": {},
   "source": [
    "## Relevant sequences\n",
    "* Triangular numbers: [A000217](https://oeis.org/A000217)\n",
    "* Square numbers: [A000290](https://oeis.org/A000290)\n",
    "* Pentagonal numbers: [A000326](https://oeis.org/A000326)\n",
    "* Hexagonal numbers: [A000384](https://oeis.org/A000384)\n",
    "* Heptagonal numbers: [A000566](https://oeis.org/A000566)\n",
    "* Octagonal numbers: [A000567](https://oeis.org/A000567)\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
}