prime_network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b2a72754-151b-41f5-95d5-d6b0a5a1dc12",
   "metadata": {},
   "source": [
    "# The prime network\n",
    "\n",
    "#### Riddler Classic for Friday May 6, 2022. Solution by [Laurent Lessard](https://laurentlessard.com)\n",
    "\n",
    "This week's [Riddler Classic](https://fivethirtyeight.com/features/can-you-build-the-longest-ladder/) is about a network of prime numbers. Here is the problem:\n",
    "\n",
    "> As you may know, a word ladder is a sequence of words in which exactly one letter changes from one word to the next. And an optimal word ladder is a word ladder that gets you from the initial word to the final word using as few other words as possible. For example, to go from DOG to CAT, an optimal word ladder has just four total words (including DOG and CAT): DOG, DOT, COT and CAT.\n",
    ">\n",
    "> For this puzzle, Michael similarly defines optimal prime ladders. Every number in the ladder must be prime, with exactly one digit changing from one number to the next. For example, here is an optimal prime ladder that goes from 97 to 53 with just four total numbers: 97, 17, 13 and 53.\n",
    ">\n",
    "> This is tied for the longest optimal prime ladder consisting of two-digit primes. What is the longest optimal prime ladder for three-digit primes? Four-digit primes? Five-digit primes?\n",
    ">\n",
    "> Extra credit: What is the longest optimal prime ladder for six-digit primes?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1da370a2-2e73-46b2-9782-8dffe3dffd86",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "Imagine a graph, where each node is a different $N$-digit prime. We draw an edge connecting any two nodes if the corresponding primes differ by exactly one digit. Then, in graph theory terms,\n",
    "- A \"ladder\" from $p_1$ to $p_2$ is a [path](https://en.wikipedia.org/wiki/Path_(graph_theory)) from node $p_1$ to node $p_2$.\n",
    "- An \"optimal ladder\" from $p_1$ to $p_2$ is the path of minimum [distance](https://en.wikipedia.org/wiki/Distance_(graph_theory)) between $p_1$ and $p_2$.\n",
    "- The \"longest optimal ladder\" is the [diameter](https://en.wikipedia.org/wiki/Distance_(graph_theory)#:~:text=To%20find%20the%20diameter%20of,the%20diameter%20of%20the%20graph.) of the graph.\n",
    "\n",
    "There exist [polynomial-time algorithms](https://stackoverflow.com/questions/15646307/algorithm-for-diameter-of-graph) for finding the diameter of a graph, which is what we implemented here.\n",
    "\n",
    "Here are the solutions I obtained. For each, I will give the length of the longest optimal ladder, which is the same as the diameter of the graph plus one (since the diameter counts the number of edges, not the number of nodes). I also provide one possible example of a longest optimal ladder.\n",
    "- $N=2$. Length 4. Example: `[23, 73, 71, 31]`\n",
    "- $N=3$. Length 7. Example: `[389, 379, 179, 109, 101, 701, 761]`\n",
    "- $N=4$. Length 9. Example: `[2441, 5441, 5449, 5849, 5869, 6869, 6899, 6199, 9199]`\n",
    "- $N=5$. Length 11. Example: `[88259, 78259, 76259, 96259, 96269, 96469, 96461, 96661, 99661, 99761, 99721]`\n",
    "- $N=6$. Length 13. Example: `[440497, 410497, 410491, 710491, 710441, 710443, 717443, 917443, 917843, 907843, 905843, 905833, 995833]`\n",
    "\n",
    "For $N\\leq 5$, the graph is [connected](https://en.wikipedia.org/wiki/Connectivity_(graph_theory)). But when $N=6$, interestingly, the graph is disconnected! The graph for $N=6$ has 68,906 nodes, but 7 connected components! They are: `[294001]`, `[505447]`, `[584141]`, `[604171]`, `[929573]`, `[971767]`, and then everything else. This means that if you start with any of these six primes, there is no way to change a single digit and obtain another prime. My code is below."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fefead80-6910-4d26-adef-1f5961923861",
   "metadata": {},
   "source": [
    "# My Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 384,
   "id": "c740751e-76a8-4b84-a9aa-43d9497b0877",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvis.network import Network\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5539c304-f84d-45a6-93ba-dd38b54492f8",
   "metadata": {},
   "source": [
    "## Make visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 386,
   "id": "a4e15f79-0d01-494c-ad18-7e0b165927d3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"900px\"\n",
       "            height=\"600px\"\n",
       "            src=\"netplot.html\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x21e805f2df0>"
      ]
     },
     "execution_count": 386,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DIGITS = 3\n",
    "plist = [n for n in primes(10**(DIGITS)-1) if n >= 10**(DIGITS-1)]\n",
    "net = Network('600px','900px')\n",
    "net.add_nodes(plist, size=[8]*len(plist))\n",
    "\n",
    "for (p1,p2) in combinations(plist,2):\n",
    "    if isnear(p1,p2):\n",
    "        net.add_edge(p1,p2)\n",
    "\n",
    "# get adjacency matrix\n",
    "graph = net.get_adj_list()\n",
    "        \n",
    "# MAKE VISUALIZATION\n",
    "net.toggle_physics(status=True)\n",
    "net.prep_notebook()\n",
    "net.show('netplot.html')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7957d9fb-5eac-4095-a429-d4d048bcb989",
   "metadata": {},
   "source": [
    "---\n",
    "## Use csr representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 387,
   "id": "1395f1f7-8b0d-4737-b661-829fd0c8e70e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.sparse import csr_matrix\n",
    "from scipy.sparse.csgraph import shortest_path, connected_components\n",
    "from itertools import combinations\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 388,
   "id": "b1de87b9-ae6a-462d-b770-ccaf756b01f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def primes(n):\n",
    "    \"\"\" Returns  a list of primes < n \"\"\"\n",
    "    sieve = [True] * n\n",
    "    for i in range(3,int(n**0.5)+1,2):\n",
    "        if sieve[i]:\n",
    "            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)\n",
    "    return [2] + [i for i in range(3,n,2) if sieve[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 389,
   "id": "1ff5c499-6396-449e-9f5b-68ff1a7f8c25",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isnear(p1,p2):\n",
    "    \"\"\" Returns TRUE if p1 and p2 differ by one digit \"\"\"\n",
    "    string1 = str(p1)\n",
    "    string2 = str(p2)\n",
    "    count_diffs = 0\n",
    "    for a, b in zip(string1, string2):\n",
    "        if a!=b:\n",
    "            if count_diffs: return False\n",
    "            count_diffs += 1\n",
    "    return count_diffs == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 390,
   "id": "c6b2bb6a-bb3e-412b-82a8-b401357f4dd7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isnear_str(string1,string2):\n",
    "    \"\"\" Returns TRUE if p1 and p2 differ by one digit \"\"\"\n",
    "    count_diffs = 0\n",
    "    for a, b in zip(string1, string2):\n",
    "        if a!=b:\n",
    "            if count_diffs: return False\n",
    "            count_diffs += 1\n",
    "    return count_diffs == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 391,
   "id": "5ca915d4-de16-4a03-9a14-4d2223ded5cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_path(plist,Pr, i, j):\n",
    "    path = [int(plist[j])]\n",
    "    k = j\n",
    "    while Pr[i, k] != -9999:\n",
    "        path.append(int(plist[Pr[i, k]]))\n",
    "        k = Pr[i, k]\n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 392,
   "id": "6a0cec5b-b4dd-4719-919e-5f002807d100",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 19.2 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "DIGITS = 3\n",
    "\n",
    "plist = [str(n) for n in primes(10**(DIGITS)-1) if n >= 10**(DIGITS-1)]\n",
    "\n",
    "data = []\n",
    "row_ind = []\n",
    "col_ind = []\n",
    "\n",
    "for (i,j) in combinations(range(len(plist)),2):\n",
    "    if isnear_str(plist[i],plist[j]):\n",
    "        data.append(1)\n",
    "        row_ind.append(i)\n",
    "        col_ind.append(j)\n",
    "\n",
    "# build matrix sparse adjacency matrix\n",
    "mat = csr_matrix((data,(row_ind,col_ind)),(len(plist),len(plist)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 393,
   "id": "48ef01f4-de55-4acb-8176-9a632169e65a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "[389, 379, 179, 109, 101, 701, 761]\n",
      "Wall time: 4.99 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "dist_matrix, pred = shortest_path(csgraph=mat, directed=False, return_predecessors=True)\n",
    "\n",
    "# deal with the possibility that the graph has multiple connected components\n",
    "if connected_components(mat, directed=False, return_labels=False) > 1:\n",
    "    print('There are multiple connected components!')\n",
    "    dist_matrix = np.where(dist_matrix == np.inf, -9999, dist_matrix)\n",
    "\n",
    "# find longest path (graph diameter)\n",
    "(i1,i2) = np.unravel_index(dist_matrix.argmax(), dist_matrix.shape)\n",
    "pp = get_path(plist,pred,i1,i2)\n",
    "print(len(pp)-1)\n",
    "print(pp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21de7feb-ad02-4a7b-9bb4-e2b010195c11",
   "metadata": {},
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}