prob_070_done.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n",
      "False\n",
      "True\n",
      "[1]\n",
      "[2]\n",
      "[3]\n",
      "[2, 2]\n",
      "[5]\n",
      "[2, 3]\n",
      "[7]\n",
      "[2, 2, 2]\n",
      "[3, 3]\n",
      "[2, 5]\n",
      "[11]\n",
      "[2, 2, 3]\n",
      "[13]\n",
      "[2, 7]\n",
      "[3, 5]\n",
      "[2, 2, 2, 2]\n",
      "[17]\n",
      "[2, 3, 3]\n",
      "[19]\n",
      "[2, 2, 5]\n",
      "[3, 7]\n",
      "[2, 11]\n",
      "[23]\n",
      "[2, 2, 2, 3]\n",
      "[5, 5]\n",
      "[2, 13]\n",
      "[3, 3, 3]\n",
      "[2, 2, 7]\n",
      "[29]\n",
      "[2, 3, 5]\n",
      "[31]\n",
      "[2, 2, 2, 2, 2]\n",
      "[3, 11]\n",
      "[2, 17]\n",
      "[5, 7]\n",
      "[2, 2, 3, 3]\n",
      "[37]\n",
      "[2, 19]\n",
      "[3, 13]\n",
      "[2, 2, 2, 5]\n",
      "[41]\n",
      "[2, 3, 7]\n",
      "[43]\n",
      "[2, 2, 11]\n",
      "[3, 3, 5]\n",
      "[2, 23]\n",
      "[47]\n",
      "[2, 2, 2, 2, 3]\n",
      "[7, 7]\n",
      "[2, 5, 5]\n",
      "[3, 17]\n",
      "[2, 2, 13]\n",
      "[53]\n",
      "[2, 3, 3, 3]\n",
      "[5, 11]\n",
      "[2, 2, 2, 7]\n",
      "[3, 19]\n",
      "[2, 29]\n",
      "[59]\n",
      "[2, 2, 3, 5]\n",
      "[61]\n",
      "[2, 31]\n",
      "[3, 3, 7]\n",
      "[2, 2, 2, 2, 2, 2]\n",
      "[5, 13]\n",
      "[2, 3, 11]\n",
      "[67]\n",
      "[2, 2, 17]\n",
      "[3, 23]\n",
      "[2, 5, 7]\n",
      "[71]\n",
      "[2, 2, 2, 3, 3]\n",
      "[73]\n",
      "[2, 37]\n",
      "[3, 5, 5]\n",
      "[2, 2, 19]\n",
      "[7, 11]\n",
      "[2, 3, 13]\n",
      "[79]\n",
      "[2, 2, 2, 2, 5]\n",
      "[3, 3, 3, 3]\n",
      "[2, 41]\n",
      "[83]\n",
      "[2, 2, 3, 7]\n",
      "[5, 17]\n",
      "[2, 43]\n",
      "[3, 29]\n",
      "[2, 2, 2, 11]\n",
      "[89]\n",
      "[2, 3, 3, 5]\n",
      "[7, 13]\n",
      "[2, 2, 23]\n",
      "[3, 31]\n",
      "[2, 47]\n",
      "[5, 19]\n",
      "[2, 2, 2, 2, 2, 3]\n",
      "[97]\n",
      "[2, 7, 7]\n",
      "[3, 3, 11]\n",
      "[2, 2, 5, 5]\n",
      "[101]\n",
      "[2, 3, 17]\n",
      "[103]\n",
      "[2, 2, 2, 13]\n",
      "[3, 5, 7]\n",
      "[2, 53]\n",
      "[107]\n",
      "[2, 2, 3, 3, 3]\n",
      "[109]\n",
      "[2, 5, 11]\n",
      "[3, 37]\n",
      "[2, 2, 2, 2, 7]\n",
      "[113]\n",
      "[2, 3, 19]\n",
      "[5, 23]\n",
      "[2, 2, 29]\n",
      "[3, 3, 13]\n",
      "[2, 59]\n",
      "[7, 17]\n",
      "[2, 2, 2, 3, 5]\n",
      "[11, 11]\n",
      "[2, 61]\n",
      "[3, 41]\n",
      "[2, 2, 31]\n",
      "[5, 5, 5]\n",
      "[2, 3, 3, 7]\n",
      "[127]\n",
      "[2, 2, 2, 2, 2, 2, 2]\n",
      "[3, 43]\n",
      "[2, 5, 13]\n",
      "[131]\n",
      "[2, 2, 3, 11]\n",
      "[7, 19]\n",
      "[2, 67]\n",
      "[3, 3, 3, 5]\n",
      "[2, 2, 2, 17]\n",
      "[137]\n",
      "[2, 3, 23]\n",
      "[139]\n",
      "[2, 2, 5, 7]\n",
      "[3, 47]\n",
      "[2, 71]\n",
      "[11, 13]\n",
      "[2, 2, 2, 2, 3, 3]\n",
      "[5, 29]\n",
      "[2, 73]\n",
      "[3, 7, 7]\n",
      "[2, 2, 37]\n",
      "[149]\n",
      "[2, 3, 5, 5]\n",
      "[151]\n",
      "[2, 2, 2, 19]\n",
      "[3, 3, 17]\n",
      "[2, 7, 11]\n",
      "[5, 31]\n",
      "[2, 2, 3, 13]\n",
      "[157]\n",
      "[2, 79]\n",
      "[3, 53]\n",
      "[2, 2, 2, 2, 2, 5]\n",
      "[7, 23]\n",
      "[2, 3, 3, 3, 3]\n",
      "[163]\n",
      "[2, 2, 41]\n",
      "[3, 5, 11]\n",
      "[2, 83]\n",
      "[167]\n",
      "[2, 2, 2, 3, 7]\n",
      "[13, 13]\n",
      "[2, 5, 17]\n",
      "[3, 3, 19]\n",
      "[2, 2, 43]\n",
      "[173]\n",
      "[2, 3, 29]\n",
      "[5, 5, 7]\n",
      "[2, 2, 2, 2, 11]\n",
      "[3, 59]\n",
      "[2, 89]\n",
      "[179]\n",
      "[2, 2, 3, 3, 5]\n",
      "[181]\n",
      "[2, 7, 13]\n",
      "[3, 61]\n",
      "[2, 2, 2, 23]\n",
      "[5, 37]\n",
      "[2, 3, 31]\n",
      "[11, 17]\n",
      "[2, 2, 47]\n",
      "[3, 3, 3, 7]\n",
      "[2, 5, 19]\n",
      "[191]\n",
      "[2, 2, 2, 2, 2, 2, 3]\n",
      "[193]\n",
      "[2, 97]\n",
      "[3, 5, 13]\n",
      "[2, 2, 7, 7]\n",
      "[197]\n",
      "[2, 3, 3, 11]\n",
      "[199]\n",
      "[2, 2, 2, 5, 5]\n",
      "[3, 67]\n",
      "[2, 101]\n",
      "[7, 29]\n",
      "[2, 2, 3, 17]\n",
      "[5, 41]\n",
      "[2, 103]\n",
      "[3, 3, 23]\n",
      "[2, 2, 2, 2, 13]\n",
      "[11, 19]\n",
      "[2, 3, 5, 7]\n",
      "[211]\n",
      "[2, 2, 53]\n",
      "[3, 71]\n",
      "[2, 107]\n",
      "[5, 43]\n",
      "[2, 2, 2, 3, 3, 3]\n",
      "[7, 31]\n",
      "[2, 109]\n",
      "[3, 73]\n",
      "[2, 2, 5, 11]\n",
      "[13, 17]\n",
      "[2, 3, 37]\n",
      "[223]\n",
      "[2, 2, 2, 2, 2, 7]\n",
      "[3, 3, 5, 5]\n",
      "[2, 113]\n",
      "[227]\n",
      "[2, 2, 3, 19]\n",
      "[229]\n",
      "[2, 5, 23]\n",
      "[3, 7, 11]\n",
      "[2, 2, 2, 29]\n",
      "[233]\n",
      "[2, 3, 3, 13]\n",
      "[5, 47]\n",
      "[2, 2, 59]\n",
      "[3, 79]\n",
      "[2, 7, 17]\n",
      "[239]\n",
      "[2, 2, 2, 2, 3, 5]\n",
      "[241]\n",
      "[2, 11, 11]\n",
      "[3, 3, 3, 3, 3]\n",
      "[2, 2, 61]\n",
      "[5, 7, 7]\n",
      "[2, 3, 41]\n",
      "[13, 19]\n",
      "[2, 2, 2, 31]\n",
      "[3, 83]\n",
      "[2, 5, 5, 5]\n",
      "[251]\n",
      "[2, 2, 3, 3, 7]\n",
      "[11, 23]\n",
      "[2, 127]\n",
      "[3, 5, 17]\n",
      "[2, 2, 2, 2, 2, 2, 2, 2]\n",
      "[257]\n",
      "[2, 3, 43]\n",
      "[7, 37]\n",
      "[2, 2, 5, 13]\n",
      "[3, 3, 29]\n",
      "[2, 131]\n",
      "[263]\n",
      "[2, 2, 2, 3, 11]\n",
      "[5, 53]\n",
      "[2, 7, 19]\n",
      "[3, 89]\n",
      "[2, 2, 67]\n",
      "[269]\n",
      "[2, 3, 3, 3, 5]\n",
      "[271]\n",
      "[2, 2, 2, 2, 17]\n",
      "[3, 7, 13]\n",
      "[2, 137]\n",
      "[5, 5, 11]\n",
      "[2, 2, 3, 23]\n",
      "[277]\n",
      "[2, 139]\n",
      "[3, 3, 31]\n",
      "[2, 2, 2, 5, 7]\n",
      "[281]\n",
      "[2, 3, 47]\n",
      "[283]\n",
      "[2, 2, 71]\n",
      "[3, 5, 19]\n",
      "[2, 11, 13]\n",
      "[7, 41]\n",
      "[2, 2, 2, 2, 2, 3, 3]\n",
      "[17, 17]\n",
      "[2, 5, 29]\n",
      "[3, 97]\n",
      "[2, 2, 73]\n",
      "[293]\n",
      "[2, 3, 7, 7]\n",
      "[5, 59]\n",
      "[2, 2, 2, 37]\n",
      "[3, 3, 3, 11]\n",
      "[2, 149]\n",
      "[13, 23]\n",
      "[2, 2, 3, 5, 5]\n",
      "[7, 43]\n",
      "[2, 151]\n",
      "[3, 101]\n",
      "[2, 2, 2, 2, 19]\n",
      "[5, 61]\n",
      "[2, 3, 3, 17]\n",
      "[307]\n",
      "[2, 2, 7, 11]\n",
      "[3, 103]\n",
      "[2, 5, 31]\n",
      "[311]\n",
      "[2, 2, 2, 3, 13]\n",
      "[313]\n",
      "[2, 157]\n",
      "[3, 3, 5, 7]\n",
      "[2, 2, 79]\n",
      "[317]\n",
      "[2, 3, 53]\n",
      "[11, 29]\n",
      "[2, 2, 2, 2, 2, 2, 5]\n",
      "[3, 107]\n",
      "[2, 7, 23]\n",
      "[17, 19]\n",
      "[2, 2, 3, 3, 3, 3]\n",
      "[5, 5, 13]\n",
      "[2, 163]\n",
      "[3, 109]\n",
      "[2, 2, 2, 41]\n",
      "[7, 47]\n",
      "[2, 3, 5, 11]\n",
      "[331]\n",
      "[2, 2, 83]\n",
      "[3, 3, 37]\n",
      "[2, 167]\n",
      "[5, 67]\n",
      "[2, 2, 2, 2, 3, 7]\n",
      "[337]\n",
      "[2, 13, 13]\n",
      "[3, 113]\n",
      "[2, 2, 5, 17]\n",
      "[11, 31]\n",
      "[2, 3, 3, 19]\n",
      "[7, 7, 7]\n",
      "[2, 2, 2, 43]\n",
      "[3, 5, 23]\n",
      "[2, 173]\n",
      "[347]\n",
      "[2, 2, 3, 29]\n",
      "[349]\n",
      "[2, 5, 5, 7]\n",
      "[3, 3, 3, 13]\n",
      "[2, 2, 2, 2, 2, 11]\n",
      "[353]\n",
      "[2, 3, 59]\n",
      "[5, 71]\n",
      "[2, 2, 89]\n",
      "[3, 7, 17]\n",
      "[2, 179]\n",
      "[359]\n",
      "[2, 2, 2, 3, 3, 5]\n",
      "[19, 19]\n",
      "[2, 181]\n",
      "[3, 11, 11]\n",
      "[2, 2, 7, 13]\n",
      "[5, 73]\n",
      "[2, 3, 61]\n",
      "[367]\n",
      "[2, 2, 2, 2, 23]\n",
      "[3, 3, 41]\n",
      "[2, 5, 37]\n",
      "[7, 53]\n",
      "[2, 2, 3, 31]\n",
      "[373]\n",
      "[2, 11, 17]\n",
      "[3, 5, 5, 5]\n",
      "[2, 2, 2, 47]\n",
      "[13, 29]\n",
      "[2, 3, 3, 3, 7]\n",
      "[379]\n",
      "[2, 2, 5, 19]\n",
      "[3, 127]\n",
      "[2, 191]\n",
      "[383]\n",
      "[2, 2, 2, 2, 2, 2, 2, 3]\n",
      "[5, 7, 11]\n",
      "[2, 193]\n",
      "[3, 3, 43]\n",
      "[2, 2, 97]\n",
      "[389]\n",
      "[2, 3, 5, 13]\n",
      "[17, 23]\n",
      "[2, 2, 2, 7, 7]\n",
      "[3, 131]\n",
      "[2, 197]\n",
      "[5, 79]\n",
      "[2, 2, 3, 3, 11]\n",
      "[397]\n",
      "[2, 199]\n",
      "[3, 7, 19]\n",
      "[2, 2, 2, 2, 5, 5]\n",
      "[401]\n",
      "[2, 3, 67]\n",
      "[13, 31]\n",
      "[2, 2, 101]\n",
      "[3, 3, 3, 3, 5]\n",
      "[2, 7, 29]\n",
      "[11, 37]\n",
      "[2, 2, 2, 3, 17]\n",
      "[409]\n",
      "[2, 5, 41]\n",
      "[3, 137]\n",
      "[2, 2, 103]\n",
      "[7, 59]\n",
      "[2, 3, 3, 23]\n",
      "[5, 83]\n",
      "[2, 2, 2, 2, 2, 13]\n",
      "[3, 139]\n",
      "[2, 11, 19]\n",
      "[419]\n",
      "[2, 2, 3, 5, 7]\n",
      "[421]\n",
      "[2, 211]\n",
      "[3, 3, 47]\n",
      "[2, 2, 2, 53]\n",
      "[5, 5, 17]\n",
      "[2, 3, 71]\n",
      "[7, 61]\n",
      "[2, 2, 107]\n",
      "[3, 11, 13]\n",
      "[2, 5, 43]\n",
      "[431]\n",
      "[2, 2, 2, 2, 3, 3, 3]\n",
      "[433]\n",
      "[2, 7, 31]\n",
      "[3, 5, 29]\n",
      "[2, 2, 109]\n",
      "[19, 23]\n",
      "[2, 3, 73]\n",
      "[439]\n",
      "[2, 2, 2, 5, 11]\n",
      "[3, 3, 7, 7]\n",
      "[2, 13, 17]\n",
      "[443]\n",
      "[2, 2, 3, 37]\n",
      "[5, 89]\n",
      "[2, 223]\n",
      "[3, 149]\n",
      "[2, 2, 2, 2, 2, 2, 7]\n",
      "[449]\n",
      "[2, 3, 3, 5, 5]\n",
      "[11, 41]\n",
      "[2, 2, 113]\n",
      "[3, 151]\n",
      "[2, 227]\n",
      "[5, 7, 13]\n",
      "[2, 2, 2, 3, 19]\n",
      "[457]\n",
      "[2, 229]\n",
      "[3, 3, 3, 17]\n",
      "[2, 2, 5, 23]\n",
      "[461]\n",
      "[2, 3, 7, 11]\n",
      "[463]\n",
      "[2, 2, 2, 2, 29]\n",
      "[3, 5, 31]\n",
      "[2, 233]\n",
      "[467]\n",
      "[2, 2, 3, 3, 13]\n",
      "[7, 67]\n",
      "[2, 5, 47]\n",
      "[3, 157]\n",
      "[2, 2, 2, 59]\n",
      "[11, 43]\n",
      "[2, 3, 79]\n",
      "[5, 5, 19]\n",
      "[2, 2, 7, 17]\n",
      "[3, 3, 53]\n",
      "[2, 239]\n",
      "[479]\n",
      "[2, 2, 2, 2, 2, 3, 5]\n",
      "[13, 37]\n",
      "[2, 241]\n",
      "[3, 7, 23]\n",
      "[2, 2, 11, 11]\n",
      "[5, 97]\n",
      "[2, 3, 3, 3, 3, 3]\n",
      "[487]\n",
      "[2, 2, 2, 61]\n",
      "[3, 163]\n",
      "[2, 5, 7, 7]\n",
      "[491]\n",
      "[2, 2, 3, 41]\n",
      "[17, 29]\n",
      "[2, 13, 19]\n",
      "[3, 3, 5, 11]\n",
      "[2, 2, 2, 2, 31]\n",
      "[7, 71]\n",
      "[2, 3, 83]\n",
      "[499]\n",
      "[2, 2, 5, 5, 5]\n",
      "[3, 167]\n",
      "[2, 251]\n",
      "[503]\n",
      "[2, 2, 2, 3, 3, 7]\n",
      "[5, 101]\n",
      "[2, 11, 23]\n",
      "[3, 13, 13]\n",
      "[2, 2, 127]\n",
      "[509]\n",
      "[2, 3, 5, 17]\n",
      "[7, 73]\n",
      "[2, 2, 2, 2, 2, 2, 2, 2, 2]\n",
      "[3, 3, 3, 19]\n",
      "[2, 257]\n",
      "[5, 103]\n",
      "[2, 2, 3, 43]\n",
      "[11, 47]\n",
      "[2, 7, 37]\n",
      "[3, 173]\n",
      "[2, 2, 2, 5, 13]\n",
      "[521]\n",
      "[2, 3, 3, 29]\n",
      "[523]\n",
      "[2, 2, 131]\n",
      "[3, 5, 5, 7]\n",
      "[2, 263]\n",
      "[17, 31]\n",
      "[2, 2, 2, 2, 3, 11]\n",
      "[23, 23]\n",
      "[2, 5, 53]\n",
      "[3, 3, 59]\n",
      "[2, 2, 7, 19]\n",
      "[13, 41]\n",
      "[2, 3, 89]\n",
      "[5, 107]\n",
      "[2, 2, 2, 67]\n",
      "[3, 179]\n",
      "[2, 269]\n",
      "[7, 7, 11]\n",
      "[2, 2, 3, 3, 3, 5]\n",
      "[541]\n",
      "[2, 271]\n",
      "[3, 181]\n",
      "[2, 2, 2, 2, 2, 17]\n",
      "[5, 109]\n",
      "[2, 3, 7, 13]\n",
      "[547]\n",
      "[2, 2, 137]\n",
      "[3, 3, 61]\n",
      "[2, 5, 5, 11]\n",
      "[19, 29]\n",
      "[2, 2, 2, 3, 23]\n",
      "[7, 79]\n",
      "[2, 277]\n",
      "[3, 5, 37]\n",
      "[2, 2, 139]\n",
      "[557]\n",
      "[2, 3, 3, 31]\n",
      "[13, 43]\n",
      "[2, 2, 2, 2, 5, 7]\n",
      "[3, 11, 17]\n",
      "[2, 281]\n",
      "[563]\n",
      "[2, 2, 3, 47]\n",
      "[5, 113]\n",
      "[2, 283]\n",
      "[3, 3, 3, 3, 7]\n",
      "[2, 2, 2, 71]\n",
      "[569]\n",
      "[2, 3, 5, 19]\n",
      "[571]\n",
      "[2, 2, 11, 13]\n",
      "[3, 191]\n",
      "[2, 7, 41]\n",
      "[5, 5, 23]\n",
      "[2, 2, 2, 2, 2, 2, 3, 3]\n",
      "[577]\n",
      "[2, 17, 17]\n",
      "[3, 193]\n",
      "[2, 2, 5, 29]\n",
      "[7, 83]\n",
      "[2, 3, 97]\n",
      "[11, 53]\n",
      "[2, 2, 2, 73]\n",
      "[3, 3, 5, 13]\n",
      "[2, 293]\n",
      "[587]\n",
      "[2, 2, 3, 7, 7]\n",
      "[19, 31]\n",
      "[2, 5, 59]\n",
      "[3, 197]\n",
      "[2, 2, 2, 2, 37]\n",
      "[593]\n",
      "[2, 3, 3, 3, 11]\n",
      "[5, 7, 17]\n",
      "[2, 2, 149]\n",
      "[3, 199]\n",
      "[2, 13, 23]\n",
      "[599]\n",
      "[2, 2, 2, 3, 5, 5]\n",
      "[601]\n",
      "[2, 7, 43]\n",
      "[3, 3, 67]\n",
      "[2, 2, 151]\n",
      "[5, 11, 11]\n",
      "[2, 3, 101]\n",
      "[607]\n",
      "[2, 2, 2, 2, 2, 19]\n",
      "[3, 7, 29]\n",
      "[2, 5, 61]\n",
      "[13, 47]\n",
      "[2, 2, 3, 3, 17]\n",
      "[613]\n",
      "[2, 307]\n",
      "[3, 5, 41]\n",
      "[2, 2, 2, 7, 11]\n",
      "[617]\n",
      "[2, 3, 103]\n",
      "[619]\n",
      "[2, 2, 5, 31]\n",
      "[3, 3, 3, 23]\n",
      "[2, 311]\n",
      "[7, 89]\n",
      "[2, 2, 2, 2, 3, 13]\n",
      "[5, 5, 5, 5]\n",
      "[2, 313]\n",
      "[3, 11, 19]\n",
      "[2, 2, 157]\n",
      "[17, 37]\n",
      "[2, 3, 3, 5, 7]\n",
      "[631]\n",
      "[2, 2, 2, 79]\n",
      "[3, 211]\n",
      "[2, 317]\n",
      "[5, 127]\n",
      "[2, 2, 3, 53]\n",
      "[7, 7, 13]\n",
      "[2, 11, 29]\n",
      "[3, 3, 71]\n",
      "[2, 2, 2, 2, 2, 2, 2, 5]\n",
      "[641]\n",
      "[2, 3, 107]\n",
      "[643]\n",
      "[2, 2, 7, 23]\n",
      "[3, 5, 43]\n",
      "[2, 17, 19]\n",
      "[647]\n",
      "[2, 2, 2, 3, 3, 3, 3]\n",
      "[11, 59]\n",
      "[2, 5, 5, 13]\n",
      "[3, 7, 31]\n",
      "[2, 2, 163]\n",
      "[653]\n",
      "[2, 3, 109]\n",
      "[5, 131]\n",
      "[2, 2, 2, 2, 41]\n",
      "[3, 3, 73]\n",
      "[2, 7, 47]\n",
      "[659]\n",
      "[2, 2, 3, 5, 11]\n",
      "[661]\n",
      "[2, 331]\n",
      "[3, 13, 17]\n",
      "[2, 2, 2, 83]\n",
      "[5, 7, 19]\n",
      "[2, 3, 3, 37]\n",
      "[23, 29]\n",
      "[2, 2, 167]\n",
      "[3, 223]\n",
      "[2, 5, 67]\n",
      "[11, 61]\n",
      "[2, 2, 2, 2, 2, 3, 7]\n",
      "[673]\n",
      "[2, 337]\n",
      "[3, 3, 3, 5, 5]\n",
      "[2, 2, 13, 13]\n",
      "[677]\n",
      "[2, 3, 113]\n",
      "[7, 97]\n",
      "[2, 2, 2, 5, 17]\n",
      "[3, 227]\n",
      "[2, 11, 31]\n",
      "[683]\n",
      "[2, 2, 3, 3, 19]\n",
      "[5, 137]\n",
      "[2, 7, 7, 7]\n",
      "[3, 229]\n",
      "[2, 2, 2, 2, 43]\n",
      "[13, 53]\n",
      "[2, 3, 5, 23]\n",
      "[691]\n",
      "[2, 2, 173]\n",
      "[3, 3, 7, 11]\n",
      "[2, 347]\n",
      "[5, 139]\n",
      "[2, 2, 2, 3, 29]\n",
      "[17, 41]\n",
      "[2, 349]\n",
      "[3, 233]\n",
      "[2, 2, 5, 5, 7]\n",
      "[701]\n",
      "[2, 3, 3, 3, 13]\n",
      "[19, 37]\n",
      "[2, 2, 2, 2, 2, 2, 11]\n",
      "[3, 5, 47]\n",
      "[2, 353]\n",
      "[7, 101]\n",
      "[2, 2, 3, 59]\n",
      "[709]\n",
      "[2, 5, 71]\n",
      "[3, 3, 79]\n",
      "[2, 2, 2, 89]\n",
      "[23, 31]\n",
      "[2, 3, 7, 17]\n",
      "[5, 11, 13]\n",
      "[2, 2, 179]\n",
      "[3, 239]\n",
      "[2, 359]\n",
      "[719]\n",
      "[2, 2, 2, 2, 3, 3, 5]\n",
      "[7, 103]\n",
      "[2, 19, 19]\n",
      "[3, 241]\n",
      "[2, 2, 181]\n",
      "[5, 5, 29]\n",
      "[2, 3, 11, 11]\n",
      "[727]\n",
      "[2, 2, 2, 7, 13]\n",
      "[3, 3, 3, 3, 3, 3]\n",
      "[2, 5, 73]\n",
      "[17, 43]\n",
      "[2, 2, 3, 61]\n",
      "[733]\n",
      "[2, 367]\n",
      "[3, 5, 7, 7]\n",
      "[2, 2, 2, 2, 2, 23]\n",
      "[11, 67]\n",
      "[2, 3, 3, 41]\n",
      "[739]\n",
      "[2, 2, 5, 37]\n",
      "[3, 13, 19]\n",
      "[2, 7, 53]\n",
      "[743]\n",
      "[2, 2, 2, 3, 31]\n",
      "[5, 149]\n",
      "[2, 373]\n",
      "[3, 3, 83]\n",
      "[2, 2, 11, 17]\n",
      "[7, 107]\n",
      "[2, 3, 5, 5, 5]\n",
      "[751]\n",
      "[2, 2, 2, 2, 47]\n",
      "[3, 251]\n",
      "[2, 13, 29]\n",
      "[5, 151]\n",
      "[2, 2, 3, 3, 3, 7]\n",
      "[757]\n",
      "[2, 379]\n",
      "[3, 11, 23]\n",
      "[2, 2, 2, 5, 19]\n",
      "[761]\n",
      "[2, 3, 127]\n",
      "[7, 109]\n",
      "[2, 2, 191]\n",
      "[3, 3, 5, 17]\n",
      "[2, 383]\n",
      "[13, 59]\n",
      "[2, 2, 2, 2, 2, 2, 2, 2, 3]\n",
      "[769]\n",
      "[2, 5, 7, 11]\n",
      "[3, 257]\n",
      "[2, 2, 193]\n",
      "[773]\n",
      "[2, 3, 3, 43]\n",
      "[5, 5, 31]\n",
      "[2, 2, 2, 97]\n",
      "[3, 7, 37]\n",
      "[2, 389]\n",
      "[19, 41]\n",
      "[2, 2, 3, 5, 13]\n",
      "[11, 71]\n",
      "[2, 17, 23]\n",
      "[3, 3, 3, 29]\n",
      "[2, 2, 2, 2, 7, 7]\n",
      "[5, 157]\n",
      "[2, 3, 131]\n",
      "[787]\n",
      "[2, 2, 197]\n",
      "[3, 263]\n",
      "[2, 5, 79]\n",
      "[7, 113]\n",
      "[2, 2, 2, 3, 3, 11]\n",
      "[13, 61]\n",
      "[2, 397]\n",
      "[3, 5, 53]\n",
      "[2, 2, 199]\n",
      "[797]\n",
      "[2, 3, 7, 19]\n",
      "[17, 47]\n",
      "[2, 2, 2, 2, 2, 5, 5]\n",
      "[3, 3, 89]\n",
      "[2, 401]\n",
      "[11, 73]\n",
      "[2, 2, 3, 67]\n",
      "[5, 7, 23]\n",
      "[2, 13, 31]\n",
      "[3, 269]\n",
      "[2, 2, 2, 101]\n",
      "[809]\n",
      "[2, 3, 3, 3, 3, 5]\n",
      "[811]\n",
      "[2, 2, 7, 29]\n",
      "[3, 271]\n",
      "[2, 11, 37]\n",
      "[5, 163]\n",
      "[2, 2, 2, 2, 3, 17]\n",
      "[19, 43]\n",
      "[2, 409]\n",
      "[3, 3, 7, 13]\n",
      "[2, 2, 5, 41]\n",
      "[821]\n",
      "[2, 3, 137]\n",
      "[823]\n",
      "[2, 2, 2, 103]\n",
      "[3, 5, 5, 11]\n",
      "[2, 7, 59]\n",
      "[827]\n",
      "[2, 2, 3, 3, 23]\n",
      "[829]\n",
      "[2, 5, 83]\n",
      "[3, 277]\n",
      "[2, 2, 2, 2, 2, 2, 13]\n",
      "[7, 7, 17]\n",
      "[2, 3, 139]\n",
      "[5, 167]\n",
      "[2, 2, 11, 19]\n",
      "[3, 3, 3, 31]\n",
      "[2, 419]\n",
      "[839]\n",
      "[2, 2, 2, 3, 5, 7]\n",
      "[29, 29]\n",
      "[2, 421]\n",
      "[3, 281]\n",
      "[2, 2, 211]\n",
      "[5, 13, 13]\n",
      "[2, 3, 3, 47]\n",
      "[7, 11, 11]\n",
      "[2, 2, 2, 2, 53]\n",
      "[3, 283]\n",
      "[2, 5, 5, 17]\n",
      "[23, 37]\n",
      "[2, 2, 3, 71]\n",
      "[853]\n",
      "[2, 7, 61]\n",
      "[3, 3, 5, 19]\n",
      "[2, 2, 2, 107]\n",
      "[857]\n",
      "[2, 3, 11, 13]\n",
      "[859]\n",
      "[2, 2, 5, 43]\n",
      "[3, 7, 41]\n",
      "[2, 431]\n",
      "[863]\n",
      "[2, 2, 2, 2, 2, 3, 3, 3]\n",
      "[5, 173]\n",
      "[2, 433]\n",
      "[3, 17, 17]\n",
      "[2, 2, 7, 31]\n",
      "[11, 79]\n",
      "[2, 3, 5, 29]\n",
      "[13, 67]\n",
      "[2, 2, 2, 109]\n",
      "[3, 3, 97]\n",
      "[2, 19, 23]\n",
      "[5, 5, 5, 7]\n",
      "[2, 2, 3, 73]\n",
      "[877]\n",
      "[2, 439]\n",
      "[3, 293]\n",
      "[2, 2, 2, 2, 5, 11]\n",
      "[881]\n",
      "[2, 3, 3, 7, 7]\n",
      "[883]\n",
      "[2, 2, 13, 17]\n",
      "[3, 5, 59]\n",
      "[2, 443]\n",
      "[887]\n",
      "[2, 2, 2, 3, 37]\n",
      "[7, 127]\n",
      "[2, 5, 89]\n",
      "[3, 3, 3, 3, 11]\n",
      "[2, 2, 223]\n",
      "[19, 47]\n",
      "[2, 3, 149]\n",
      "[5, 179]\n",
      "[2, 2, 2, 2, 2, 2, 2, 7]\n",
      "[3, 13, 23]\n",
      "[2, 449]\n",
      "[29, 31]\n",
      "[2, 2, 3, 3, 5, 5]\n",
      "[17, 53]\n",
      "[2, 11, 41]\n",
      "[3, 7, 43]\n",
      "[2, 2, 2, 113]\n",
      "[5, 181]\n",
      "[2, 3, 151]\n",
      "[907]\n",
      "[2, 2, 227]\n",
      "[3, 3, 101]\n",
      "[2, 5, 7, 13]\n",
      "[911]\n",
      "[2, 2, 2, 2, 3, 19]\n",
      "[11, 83]\n",
      "[2, 457]\n",
      "[3, 5, 61]\n",
      "[2, 2, 229]\n",
      "[7, 131]\n",
      "[2, 3, 3, 3, 17]\n",
      "[919]\n",
      "[2, 2, 2, 5, 23]\n",
      "[3, 307]\n",
      "[2, 461]\n",
      "[13, 71]\n",
      "[2, 2, 3, 7, 11]\n",
      "[5, 5, 37]\n",
      "[2, 463]\n",
      "[3, 3, 103]\n",
      "[2, 2, 2, 2, 2, 29]\n",
      "[929]\n",
      "[2, 3, 5, 31]\n",
      "[7, 7, 19]\n",
      "[2, 2, 233]\n",
      "[3, 311]\n",
      "[2, 467]\n",
      "[5, 11, 17]\n",
      "[2, 2, 2, 3, 3, 13]\n",
      "[937]\n",
      "[2, 7, 67]\n",
      "[3, 313]\n",
      "[2, 2, 5, 47]\n",
      "[941]\n",
      "[2, 3, 157]\n",
      "[23, 41]\n",
      "[2, 2, 2, 2, 59]\n",
      "[3, 3, 3, 5, 7]\n",
      "[2, 11, 43]\n",
      "[947]\n",
      "[2, 2, 3, 79]\n",
      "[13, 73]\n",
      "[2, 5, 5, 19]\n",
      "[3, 317]\n",
      "[2, 2, 2, 7, 17]\n",
      "[953]\n",
      "[2, 3, 3, 53]\n",
      "[5, 191]\n",
      "[2, 2, 239]\n",
      "[3, 11, 29]\n",
      "[2, 479]\n",
      "[7, 137]\n",
      "[2, 2, 2, 2, 2, 2, 3, 5]\n",
      "[31, 31]\n",
      "[2, 13, 37]\n",
      "[3, 3, 107]\n",
      "[2, 2, 241]\n",
      "[5, 193]\n",
      "[2, 3, 7, 23]\n",
      "[967]\n",
      "[2, 2, 2, 11, 11]\n",
      "[3, 17, 19]\n",
      "[2, 5, 97]\n",
      "[971]\n",
      "[2, 2, 3, 3, 3, 3, 3]\n",
      "[7, 139]\n",
      "[2, 487]\n",
      "[3, 5, 5, 13]\n",
      "[2, 2, 2, 2, 61]\n",
      "[977]\n",
      "[2, 3, 163]\n",
      "[11, 89]\n",
      "[2, 2, 5, 7, 7]\n",
      "[3, 3, 109]\n",
      "[2, 491]\n",
      "[983]\n",
      "[2, 2, 2, 3, 41]\n",
      "[5, 197]\n",
      "[2, 17, 29]\n",
      "[3, 7, 47]\n",
      "[2, 2, 13, 19]\n",
      "[23, 43]\n",
      "[2, 3, 3, 5, 11]\n",
      "[991]\n",
      "[2, 2, 2, 2, 2, 31]\n",
      "[3, 331]\n",
      "[2, 7, 71]\n",
      "[5, 199]\n",
      "[2, 2, 3, 83]\n",
      "[997]\n",
      "[2, 499]\n",
      "[3, 3, 3, 37]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/opt/conda/lib/python3.5/site-packages/numpy/core/numeric.py:190: VisibleDeprecationWarning: using a non-integer number instead of an integer will result in an error in the future\n",
      "  a = empty(shape, dtype, order)\n"
     ]
    }
   ],
   "source": [
    "# %load peutils/peutils.py\n",
    "def getPrimes(n):\n",
    "\timport numpy as np\n",
    "\tsieve = np.ones(n/3 + (n%6==2), dtype=np.bool)\n",
    "\tsieve[0] = False\n",
    "\tfor i in range(int((n**0.5)/3)+1):\n",
    "\t\tif sieve[i]:\n",
    "\t\t\tk=3*i+1|1\n",
    "\t\t\tsieve[int((k*k)/3) :: 2*k] = False\n",
    "\t\t\tsieve[int((k*k+4*k-2*k*(i&1))/3) :: 2*k] = False\n",
    "\treturn list(np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)])\n",
    "\n",
    "def isPrimes(x):\n",
    "\tfrom math import sqrt\n",
    "\ttestprimes = getPrimes(int(sqrt(x)))\n",
    "\treturn all([x % p !=0 for p in testprimes])\n",
    "\n",
    "# http://stackoverflow.com/questions/34056609/how-to-check-if-an-integer-is-a-perfect-square\n",
    "def isSquare(x):\n",
    "\tif x == 1:\n",
    "\t\treturn True\n",
    "\tlow = 0\n",
    "\thigh = x // 2\n",
    "\troot = high\n",
    "\twhile root * root != x:\n",
    "\t\troot = (low + high) // 2\n",
    "\t\tif low +1 >= high:\n",
    "\t\t\treturn False\n",
    "\t\tif root * root > x:\n",
    "\t\t\thigh = root\n",
    "\t\telse:\n",
    "\t\t\tlow = root\n",
    "\treturn True\n",
    "\n",
    "# http://stackoverflow.com/questions/14550794/python-integer-factorization-into-primes\n",
    "def pFactors(n): \n",
    "\t\"\"\"Finds the prime factors of 'n'\"\"\" \n",
    "\tfrom math import sqrt \n",
    "\tpFact, limit, check, num = [], int(sqrt(n)) + 1, 2, n \n",
    "\tif n == 1: return [1] \n",
    "\tfor check in range(2, limit): \n",
    "\t\twhile num % check == 0: \n",
    "\t\t\tpFact.append(check) \n",
    "\t\t\tnum /= check \n",
    "\tif num > 1:\n",
    "\t\tpFact.append(int(num)) \n",
    "\treturn pFact \n",
    "\n",
    "# Euler's Totient function, [sometimes called the phi function]\n",
    "def euler_phi(n):\n",
    "\tfrom math import gcd\n",
    "\treturn(sum([gcd(i,n)==1 for i in range(1,n)]))\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\tprint(getPrimes(100))\n",
    "\tprint(isSquare(301))\n",
    "\tprint(isSquare(121))\n",
    "\tfor i in range(1,1000):\n",
    "\t\tprint (pFactors(i))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/opt/conda/lib/python3.5/site-packages/numpy/core/numeric.py:190: VisibleDeprecationWarning: using a non-integer number instead of an integer will result in an error in the future\n",
      "  a = empty(shape, dtype, order)\n"
     ]
    }
   ],
   "source": [
    "N = 10 ** 7\n",
    "midN = math.floor( math.sqrt(N))+1\n",
    "smallprimelist = getPrimes(midN)[::-1]\n",
    "primelist = getPrimes(N)\n",
    "minratio = -1\n",
    "minn = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3137\n",
      "3121\n",
      "3119\n",
      "3109\n",
      "3089\n",
      "3083\n",
      "3079\n",
      "3067\n",
      "3061\n",
      "3049\n",
      "3041\n",
      "3037\n",
      "3023\n",
      "3019\n",
      "3011\n",
      "3001\n",
      "2999\n",
      "2971\n",
      "2969\n",
      "2963\n",
      "2957\n",
      "2953\n",
      "2939\n",
      "2927\n",
      "2917\n",
      "2909\n",
      "2903\n",
      "2897\n",
      "2887\n",
      "2879\n",
      "2861\n",
      "2857\n",
      "2851\n",
      "2843\n",
      "2837\n",
      "2833\n",
      "2819\n",
      "2803\n",
      "2801\n",
      "2797\n",
      "2791\n",
      "2789\n",
      "2777\n",
      "2767\n",
      "2753\n",
      "2749\n",
      "2741\n",
      "2731\n",
      "2729\n",
      "2719\n",
      "2713\n",
      "2711\n",
      "2707\n",
      "2699\n",
      "2693\n",
      "2689\n",
      "2687\n",
      "2683\n",
      "2677\n",
      "2671\n",
      "2663\n",
      "2659\n",
      "2657\n",
      "2647\n",
      "2633\n",
      "2621\n",
      "2617\n",
      "2609\n",
      "2609 2693 7026037 7020736 1.00075504904\n",
      "2593\n",
      "2591\n",
      "2579\n",
      "2557\n",
      "2551\n",
      "2549\n",
      "2543\n",
      "2539\n",
      "2531\n",
      "2521\n",
      "2503\n",
      "2477\n",
      "2473\n",
      "2467\n",
      "2459\n",
      "2447\n",
      "2441\n",
      "2437\n",
      "2423\n",
      "2417\n",
      "2411\n",
      "2399\n",
      "2393\n",
      "2389\n",
      "2383\n",
      "2381\n",
      "2377\n",
      "2371\n",
      "2357\n",
      "2351\n",
      "2347\n",
      "2341\n",
      "2339\n",
      "2339 3557 8319823 8313928 1.00070905112\n",
      "2333\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-00a0690cddd7>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      8\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mestratio\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mminratio\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mminratio\u001b[0m \u001b[0;34m==\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 10\u001b[0;31m                 \u001b[0mphin\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0meuler_phi\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     11\u001b[0m                 \u001b[0mperms\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m''\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mp\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpermutations\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mphin\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mperms\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-1-fd65a2667e02>\u001b[0m in \u001b[0;36meuler_phi\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     50\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0meuler_phi\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     51\u001b[0m         \u001b[0;32mfrom\u001b[0m \u001b[0mmath\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mgcd\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 52\u001b[0;31m         \u001b[0;32mreturn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mgcd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;36m1\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     53\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     54\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0m__name__\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"__main__\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-1-fd65a2667e02>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m     50\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0meuler_phi\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     51\u001b[0m         \u001b[0;32mfrom\u001b[0m \u001b[0mmath\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mgcd\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 52\u001b[0;31m         \u001b[0;32mreturn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mgcd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;36m1\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     53\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     54\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0m__name__\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"__main__\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "for x in smallprimelist:\n",
    "    print(x)\n",
    "    for y in primelist:\n",
    "        if x*y< N and y>x:\n",
    "            n = x*y\n",
    "            estratio = n/(n-(x+y-1))\n",
    "#             print(x,y,n,estratio)\n",
    "            if estratio < minratio or minratio ==-1:\n",
    "                \n",
    "                phin = euler_phi(n)\n",
    "                perms = [''.join(p) for p in permutations(str(phin))]\n",
    "                if str(n) in perms:\n",
    "                    if minratio == -1:\n",
    "                        minn = n\n",
    "                        minratio = n/phin\n",
    "                        print(x,y,n,phin,n/phin)\n",
    "                    if n/phin < minratio:\n",
    "                        minn = n\n",
    "                        minratio = n/phin\n",
    "                        print(x,y,n,phin,n/phin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# found 2609 2693 7026037 7020736 1.00075504904 \n",
    "# found 2339 3557 8319823 8313928 1.00070905112 which is the correct solution        "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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
}