{ "metadata": { "language": "fsharp", "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "###Squarefree Binomial Coefficients\n", "####Problem 203\n", "\n", "The binomial coefficients $^nC_k$ can be arranged in triangular form, Pascal's triangle, like this:\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
1
11
121
1331
14641
15101051
1615201561
172135352171
\n", "\n", "It can be seen that the first eight rows of Pascal's triangle contain twelve distinct numbers: $1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21$ and $35$.\n", "\n", "A positive integer $n$ is called squarefree if no square of a prime divides $n$. Of the twelve distinct numbers in the first eight rows of Pascal's triangle, all except $4$ and $20$ are squarefree. The sum of the distinct squarefree numbers in the first eight rows is $105$.\n", "\n", "Find the sum of the distinct squarefree numbers in the first $51$ rows of Pascal's triangle." ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p203() =\n", " let n = 50L\n", " let sqrFree (n:int64) = Math.FactorInteger n |> Seq.forall (fun (n,p) -> p=1)\n", " \n", " set [ for row in 0L..n do\n", " for i in 0L..row ->\n", " (Math.Binomial(row, i)) ]\n", " |> Set.filter sqrFree\n", " |> Seq.sum\n", " \n", "Euler.Timer(p203)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 1, "text": [ "val it : int64 * float = (34029210557338L, 0.0468358)" ] } ], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Generalised Hamming Numbers\n", "####Problem 204\n", "\n", "A Hamming number is a positive number which has no prime factor larger than $5$.\n", "So the first few Hamming numbers are $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15$.\n", "There are $1105$ Hamming numbers not exceeding $10^8$.\n", "\n", "We will call a positive number a generalised Hamming number of type $n$, if it has no prime factor larger than $n$.\n", "Hence the Hamming numbers are the generalised Hamming numbers of type $5$.\n", "\n", "How many generalised Hamming numbers of type $100$ are there which don't exceed $10^9$?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p204() =\n", " let m = 9.0\n", " let primes = Math.Primes32 |> Seq.takeWhile (fun n -> n < 100)\n", " let pl = [for p in primes -> log10 (float p)]\n", " let rec loop pos limit =\n", " if pos = 0 then int(limit/pl.[0])+1\n", " else\n", " let v = pl.[pos]\n", " let s = ref 0\n", " let nextLimit = ref limit\n", " while !nextLimit > 0.0 do\n", " s := !s + loop (pos - 1) !nextLimit\n", " nextLimit := !nextLimit - v\n", " !s\n", " loop (pl.Length-1) m\n", "\n", "Euler.Timer(p204)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 1, "text": [ "val it : int * float = (2944730, 0.0561035)" ] } ], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }