prob_075_done.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from time import time\n",
    "from math import sqrt, gcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "161667 0.7652683258056641\n"
     ]
    }
   ],
   "source": [
    "t0 = time()\n",
    "\n",
    "L_max = 1500000\n",
    "count = [0 for _ in range(L_max+1)]\n",
    "m_max = int(sqrt(L_max//2))+1\n",
    "for m in range(2, m_max):\n",
    "    for n in range(1, m):\n",
    "        if gcd(m,n)==1 and (m+n)%2==1:\n",
    "            LD = m*m+n*n\n",
    "            L1 = 2*m*n\n",
    "            L2 = m*m-n*n\n",
    "            L_tot = LD+L1+L2\n",
    "            scale = 1\n",
    "            while L_tot*scale <= L_max:\n",
    "                count[L_tot*scale]+=1\n",
    "                scale+=1\n",
    "\n",
    "print(sum([x==1 for x in count]),time()-t0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 161667 correct solution"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}