{ "metadata": { "language": "fsharp", "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "###Efficient exponentiation\n", "####Problem 122\n", "\n", "The most naive way of computing $n^{15}$ requires fourteen multiplications:\n", "\n", "$$n \u00d7 n \u00d7 ... \u00d7 n = n^{15}$$\n", "\n", "But using a \"binary\" method you can compute it in six multiplications:\n", "\n", "$$n \u00d7 n = n^2$$\n", "$$n^2 \u00d7 n^2 = n^4$$\n", "$$n^4 \u00d7 n^4 = n^8$$\n", "$$n^8 \u00d7 n^4 = n^{12}$$\n", "$$n^{12} \u00d7 n^2 = n^{14}$$\n", "$$n^{14} \u00d7 n = n^{15}$$\n", "\n", "However it is yet possible to compute it in only five multiplications:\n", "\n", "$$n \u00d7 n = n^2$$\n", "$$n^2 \u00d7 n = n^3$$\n", "$$n^3 \u00d7 n^3 = n^6$$\n", "$$n^6 \u00d7 n^6 = n^{12}$$\n", "$$n^{12} \u00d7 n^3 = n^{15}$$\n", "\n", "We shall define $m(k)$ to be the minimum number of multiplications to compute $n^k$; for example $m(15) = 5$.\n", "\n", "For $1 \u2264 k \u2264 200$, find $\u2211 m(k)$." ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p122() =\n", " let limit = 200\n", " let cost = Array.zeroCreate (limit + 1)\n", " let path = Array.zeroCreate (limit + 1)\n", " let rec Backtrack(power, depth) =\n", " if power > limit || depth > cost.[power] then ()\n", " else\n", " cost.[power] <- depth\n", " path.[depth] <- power\n", " for i in depth .. -1 .. 0 do\n", " Backtrack(power + path.[i], depth + 1)\n", " let result = ref 0\n", " for i = 0 to limit do\n", " cost.[i] <- System.Int32.MaxValue\n", " Backtrack(1, 0)\n", " for i = 1 to limit do\n", " result := !result + cost.[i] \n", " !result\n", " \n", "Euler.Timer(p122)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 1, "text": [ "val it : int * float = (1582, 0.0808332)" ] } ], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Ordered radicals\n", "####Problem 124\n", "\n", "The radical of $n$, $rad(n)$, is the product of the distinct prime factors of $n$. For example, $504 = 23 \u00d7 32 \u00d7 7$, so $rad(504) = 2 \u00d7 3 \u00d7 7 = 42$.\n", "\n", "If we calculate $rad(n)$ for $1 \u2264 n \u2264 10$, then sort them on $rad(n)$, and sorting on $n$ if the radical values are equal, we get:\n", "\n", "
Unsorted | \n",
" \n", " | Sorted | \n",
"|||
n | \n",
" rad(n) | \n",
" n | \n",
" rad(n) | \n",
" k | \n",
"|
1 | 1 | \n",
" \n", " | 1 | 1 | 1 | \n",
"
2 | 2 | \n",
" \n", " | 2 | 2 | 2 | \n",
"
3 | 3 | \n",
" \n", " | 4 | 2 | 3 | \n",
"
4 | 2 | \n",
"\n", " | 8 | 2 | 4 | \n",
"
5 | 5 | \n",
"\n", " | 3 | 3 | 5 | \n",
"
6 | 6 | \n",
"\n", " | 9 | 3 | 6 | \n",
"
7 | 7 | \n",
"\n", " | 5 | 5 | 7 | \n",
"
8 | 2 | \n",
"\n", " | 6 | 6 | 8 | \n",
"
9 | 3 | \n",
"\n", " | 7 | 7 | 9 | \n",
"
10 | 10 | \n",
"\n", " | 10 | 10 | 10 | \n",
"