{
 "metadata": {
  "language": "fsharp",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Diophantine reciprocals II\n",
      "####Problem 110\n",
      "\n",
      "In the following equation $x$, $y$, and $n$ are positive integers.\n",
      "\n",
      "$$\\frac 1 x + \\frac 1 y = \\frac 1 n$$\n",
      "\n",
      "It can be verified that when $n = 1260$ there are $113$ distinct solutions and this is the least value of $n$ for which the total number of distinct solutions exceeds one hundred.\n",
      "\n",
      "What is the least value of $n$ for which the number of distinct solutions exceeds four million?\n",
      "\n",
      "NOTE: This problem is a much more difficult version of problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "open Euler\n",
      "\n",
      "let p110() =\n",
      "    let n = 1260\n",
      "    let k = 12 // started at 15 and went down until answer repeated\n",
      "    let step = Math.Primes |> Seq.take k |> Seq.fold ( * ) 1L\n",
      "    let solutions (n:int64) = (Math.DivisorSigma(2, n) + 1) / 2\n",
      "    let rec answer guess =\n",
      "        if solutions guess < 4000000 then \n",
      "            answer (guess + step)\n",
      "        else guess\n",
      "    answer step\n",
      "\n",
      "Euler.Timer(p110)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "val it : int64 * float = (9350130049860600L, 0.11362)"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}