Euler 172 - Investigating numbers with few repeated digits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler Problem 172\n",
    "=================\n",
    "\n",
    "How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "227485267000992000\n"
     ]
    }
   ],
   "source": [
    "# a(d,k) = number of d-digit numbers containing only the digits 1 through k such that \n",
    "#          no digit occurs more than three times.\n",
    "# \n",
    "# The following recurrence is satisfied:\n",
    "#    a(d, k) = sum (i=0 to 3) c(d+1, i) * a(d-i, k-1)\n",
    "# where c() is a binomial coefficient.\n",
    "# \n",
    "# The final answer (inserting the zeros last) is\n",
    "#    a(d, 10) = sum (i=0 to 3) c(d, i) * a(d-i, 9)\n",
    "# The replacement of c(d+1, i) with c(d, i) occurs because leading zeros are not permitted.\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def c(n,r):\n",
    "    if n < 0 or r < 0 or r > n:\n",
    "        return 0\n",
    "    c = 1\n",
    "    for k in range(r):\n",
    "        c = (c * (n-k)) // (k+1)\n",
    "    return c\n",
    "\n",
    "a = Counter()\n",
    "a[0] = 1\n",
    "for k in range(10):\n",
    "    e = (k == 9)\n",
    "    for d in range(18, 0, -1):\n",
    "        a[d] += sum(c(d-e, i) * a[d-i] for i in [1,2,3])\n",
    "print(a[18])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}