euler_171-Copy1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def run(num_digits):\n",
    "    \n",
    "    from itertools import combinations_with_replacement\n",
    "    from math import factorial\n",
    "    from collections import Counter\n",
    "\n",
    "\n",
    "    def f(digits):\n",
    "        \"\"\"@digits is a tuple\"\"\"\n",
    "        total = 0\n",
    "        for d in digits:\n",
    "            total += d**2\n",
    "        return total\n",
    "\n",
    "\n",
    "    def is_square(apositiveint):\n",
    "        if apositiveint==1:\n",
    "            return True\n",
    "        x = apositiveint / 2\n",
    "        seen = set([x])\n",
    "        while x * x != apositiveint:\n",
    "            x = (x + (apositiveint / x)) / 2\n",
    "            if x in seen: return False\n",
    "            seen.add(x)\n",
    "        return True\n",
    "    \n",
    "\n",
    "    sum_of_powers_of_10 = (10**num_digits - 1)/9\n",
    "    big_fact = factorial(num_digits-1)\n",
    "\n",
    "    count = 0\n",
    "    for n in xrange(1,num_digits+1):\n",
    "        what_to_product = []\n",
    "\n",
    "        small_fact = factorial(num_digits-n)\n",
    "        perms = combinations_with_replacement(range(1,10), r=n)\n",
    "        for p in perms:\n",
    "            #print p\n",
    "            if is_square(f(p)):\n",
    "                factorials = {}\n",
    "                counter = Counter(p)\n",
    "                all_facts = 1\n",
    "                for c in counter:\n",
    "                    factorials[c] = factorial(counter[c])\n",
    "                    all_facts *= factorials[c]\n",
    "                for d in set(p):\n",
    "                    temp = factorial(counter[d]-1)\n",
    "                    multiple = (big_fact * factorials[d]) / (all_facts * small_fact * temp)\n",
    "                    #print p, d, multiple\n",
    "                    count += multiple * d * sum_of_powers_of_10\n",
    "    return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N = 20\n",
      "Total sum: 104861799630145516743395826448142989277\n",
      "Last 9 digits: 142989277\n",
      "Time taken: 117 s\n",
      "\n"
     ]
    }
   ],
   "source": [
    "num_digits = 20\n",
    "start = time.time()\n",
    "answer = run(num_digits)\n",
    "time_taken = time.time()-start\n",
    "print \"N =\", num_digits\n",
    "print \"Total sum:\", answer\n",
    "print \"Last 9 digits:\", answer%(10**9)\n",
    "print \"Time taken: {} s\\n\".format(int(time_taken))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}