{ "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", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
Unsorted
 
Sorted

n

rad(n)


n

rad(n)

k
1
1
 
1
1
1
2
2
 
2
2
2
3
3
 
4
2
3
4
2
 
8
2
4
5
5
 
3
3
5
6
6
 
9
3
6
7
7
 
5
5
7
8
2
 
6
6
8
9
3
 
7
7
9
10
10
 
10
10
10
\n", "\n", "Let $E(k)$ be the $k^{th}$ element in the sorted $n$ column; for example, $E(4) = 8$ and $E(6) = 9$.\n", "\n", "If $rad(n)$ is sorted for $1 \u2264 n \u2264 100000$, find $E(10000)$." ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p124() =\n", " let rad (n:int) = Math.FactorInteger(n) |> Seq.map fst |> Seq.fold ( * ) 1 \n", " seq { for i in 1..100000 -> i, rad i }\n", " |> Seq.sortBy snd\n", " |> Seq.nth (10000-1)\n", " |> fst\n", " \n", "Euler.Timer(p124)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 1, "text": [ "val it : int * float = (21417, 3.0745379)" ] } ], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Palindromic sums\n", "####Problem 125\n", "\n", "The palindromic number $595$ is interesting because it can be written as the sum of consecutive squares: $6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2$.\n", "\n", "There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is $4164$. Note that $1 = 0^2 + 1^2$ has not been included as this problem is concerned with the squares of positive integers.\n", "\n", "Find the sum of all the numbers less than $10^8$ that are both palindromic and can be written as the sum of consecutive squares.\n" ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p125() =\n", " let maxN = pown 10L 8\n", " let isPalindrome (n:int64) = Math.Reverse(n) = n \n", " let sqrSum i j =\n", " let acc = ref (0L)\n", " for k = i to i + j - 1 do\n", " acc := !acc + pown (int64 k) 2\n", " !acc \n", " set [ for i in 1 .. int(Math.ISqrt(maxN)) do\n", " let j = ref 2\n", " let next = ref (sqrSum i !j)\n", " while !next < maxN do\n", " if isPalindrome !next then yield !next\n", " incr j\n", " next := sqrSum i !j ]\n", " |> Seq.sum\n", " \n", "Euler.Timer(p125)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 2, "text": [ "val it : int64 * float = (2906969179L, 0.7995607)" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }