partitions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "30759aaa",
   "metadata": {},
   "source": [
    "# Partition function $p(n)$\n",
    "+ a partition of positive integer n is a sequence of positive integers >0 whose sum is n\n",
    "+ $p(n)$ gives the total number of partitions of n that is possible\n",
    "+ we use euler's pentagonal theorem \n",
    "$$ p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)+\\dots+(-1)^m[p(n-\\frac{1}{2}m(3m-1)+p(n-\\frac{1}{2}m(3m+1)]+\\dots = 0 $$\n",
    "+ current program/algoritm is slow as it is recursive "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4bfcabd3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def parti(n):\n",
    "    pt=[1,1,2,3,5,7,11] #first 6 partitions with P(0)=1\n",
    "    n=int(n)\n",
    "    if n<0  :\n",
    "        return 0 \n",
    "    elif n<7:\n",
    "        return pt[n]\n",
    "    else:\n",
    "        P=0\n",
    "        for i in range (1,n+1):\n",
    "            k1=int((i*(3*i+1))/2) #for p(n-pentagonal number)\n",
    "            k2=int((i*(3*i-1))/2)\n",
    "            P+=((-1)**(i+1))*(parti(n-k1)+parti(n-k2)) # eulers formula iteration\n",
    "            if n-k1<0 or n-k2 <0:\n",
    "                break\n",
    "        return P "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e585a360",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n=34\n",
      "The number of partitions for 34 is 12310\n",
      "\n",
      "runtime = 12.782519817352295\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "n=input('n=')\n",
    "n=int(n)\n",
    "s=time.time()\n",
    "pn=parti(n)\n",
    "e=time.time()\n",
    "print('The number of partitions for',n,'is',pn)\n",
    "print('\\nruntime =',e-s)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}