rogers-ramanujan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ロジャース・ラマヌジャン恒等式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "from copy import copy\n",
    "from math import fmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[6, 3, 1], [6, 4], [7, 3], [8, 2], [9, 1], [10]]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#d-差的な分割\n",
    "def partitions_diff_at_least(d, n):\n",
    "    partitions = []\n",
    "    stack = deque([])\n",
    "    m = n\n",
    "    while m >= 1:\n",
    "        stack.append([m])\n",
    "        m -= 1\n",
    "    while len(stack):\n",
    "        partial_partition = stack.pop()\n",
    "        partial_sum = sum(partial_partition)\n",
    "        if partial_sum == n:\n",
    "            partitions.append(partial_partition)\n",
    "        else:\n",
    "            m = min(partial_partition[-1]-d, n-partial_sum)\n",
    "            while m >= 1:\n",
    "                r = copy(partial_partition)\n",
    "                r.append(m)\n",
    "                stack.append(r)\n",
    "                m -= 1\n",
    "    return partitions\n",
    "\n",
    "partitions_diff_at_least(2, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       " [4, 1, 1, 1, 1, 1, 1],\n",
       " [4, 4, 1, 1],\n",
       " [6, 1, 1, 1, 1],\n",
       " [6, 4],\n",
       " [9, 1]]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def partitons_with_mod_restriction(cond, n):\n",
    "    partitions = []\n",
    "    stack = deque([])\n",
    "    m = n\n",
    "    while m >= 1:\n",
    "        if(cond(m)):\n",
    "            stack.append([m])\n",
    "        m -= 1\n",
    "    while len(stack):\n",
    "        partial_partition = stack.pop()\n",
    "        partial_sum = sum(partial_partition)\n",
    "        if partial_sum == n:\n",
    "            partitions.append(partial_partition)\n",
    "        else:\n",
    "            m = min(partial_partition[-1], n-partial_sum)\n",
    "            while m >= 1:\n",
    "                if(cond(m)):\n",
    "                    r = copy(partial_partition)\n",
    "                    r.append(m)\n",
    "                    stack.append(r)\n",
    "                m -= 1\n",
    "    return partitions\n",
    "\n",
    "partitons_with_mod_restriction(lambda m: fmod(m,5) == 1 or fmod(m,5) == 4, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "1: 1\n",
      "\n",
      "[2]\n",
      "2: 1\n",
      "\n",
      "[3]\n",
      "3: 1\n",
      "\n",
      "[3, 1]\n",
      "[4]\n",
      "4: 2\n",
      "\n",
      "[4, 1]\n",
      "[5]\n",
      "5: 2\n",
      "\n",
      "[4, 2]\n",
      "[5, 1]\n",
      "[6]\n",
      "6: 3\n",
      "\n",
      "[5, 2]\n",
      "[6, 1]\n",
      "[7]\n",
      "7: 3\n",
      "\n",
      "[5, 3]\n",
      "[6, 2]\n",
      "[7, 1]\n",
      "[8]\n",
      "8: 4\n",
      "\n",
      "[5, 3, 1]\n",
      "[6, 3]\n",
      "[7, 2]\n",
      "[8, 1]\n",
      "[9]\n",
      "9: 5\n",
      "\n",
      "[6, 3, 1]\n",
      "[6, 4]\n",
      "[7, 3]\n",
      "[8, 2]\n",
      "[9, 1]\n",
      "[10]\n",
      "10: 6\n",
      "\n",
      "[6, 4, 1]\n",
      "[7, 3, 1]\n",
      "[7, 4]\n",
      "[8, 3]\n",
      "[9, 2]\n",
      "[10, 1]\n",
      "[11]\n",
      "11: 7\n",
      "\n",
      "[6, 4, 2]\n",
      "[7, 4, 1]\n",
      "[7, 5]\n",
      "[8, 3, 1]\n",
      "[8, 4]\n",
      "[9, 3]\n",
      "[10, 2]\n",
      "[11, 1]\n",
      "[12]\n",
      "12: 9\n",
      "\n",
      "[7, 4, 2]\n",
      "[7, 5, 1]\n",
      "[8, 4, 1]\n",
      "[8, 5]\n",
      "[9, 3, 1]\n",
      "[9, 4]\n",
      "[10, 3]\n",
      "[11, 2]\n",
      "[12, 1]\n",
      "[13]\n",
      "13: 10\n",
      "\n",
      "[7, 5, 2]\n",
      "[8, 4, 2]\n",
      "[8, 5, 1]\n",
      "[8, 6]\n",
      "[9, 4, 1]\n",
      "[9, 5]\n",
      "[10, 3, 1]\n",
      "[10, 4]\n",
      "[11, 3]\n",
      "[12, 2]\n",
      "[13, 1]\n",
      "[14]\n",
      "14: 12\n",
      "\n",
      "[7, 5, 3]\n",
      "[8, 5, 2]\n",
      "[8, 6, 1]\n",
      "[9, 4, 2]\n",
      "[9, 5, 1]\n",
      "[9, 6]\n",
      "[10, 4, 1]\n",
      "[10, 5]\n",
      "[11, 3, 1]\n",
      "[11, 4]\n",
      "[12, 3]\n",
      "[13, 2]\n",
      "[14, 1]\n",
      "[15]\n",
      "15: 14\n",
      "\n",
      "[1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14]\n"
     ]
    }
   ],
   "source": [
    "for n in range(1,N+1):\n",
    "    stack = deque([])\n",
    "    m = n\n",
    "    while m >= 1:\n",
    "        stack.append([m])\n",
    "        m -= 1\n",
    "    comb = 0\n",
    "    while len(stack):\n",
    "        partial_partition = stack.pop()\n",
    "        partial_sum = sum(partial_partition)\n",
    "        if partial_sum == n:\n",
    "            comb += 1\n",
    "            print(partial_partition)\n",
    "        else:\n",
    "            m = min(partial_partition[-1]-d, n-partial_sum)\n",
    "            while m >= 1:\n",
    "                r = copy(partial_partition)\n",
    "                r.append(m)\n",
    "                stack.append(r)\n",
    "                m -= 1\n",
    "    print(f\"{n}: {comb}\\n\")\n",
    "    seq.append(comb)\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和因子が $\\pm 1\\mod 5$ となる分割"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "77d8cf8982bac036912c34eb7ad2ebfa0377b1462510884a8096c4b34eca4032"
  },
  "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}