{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Shared packages and functions" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "using Iterators, Primes, Combinatorics, Distributions, DataStructures, StatsBase, Digits\n", "\n", "# Combines an array of integers into one integer.\n", "function combine_list(l::Array{Int,1})\n", " s, p = 0, 0\n", " for (i, n) in enumerate(reverse(l))\n", " s += n * 10^p\n", " p += ndigits(n)\n", " end\n", " s\n", "end\n", "\n", "# Selects the first element from a list for which a condition is true\n", "function ifirst(cond, itr)\n", " for elem in itr\n", " cond(elem) && return elem\n", " end\n", "end\n", "\n", "# More functions for Digits\n", "isanagram(a, b) = sort(digits(a)) == sort(digits(b))\n", "ispandigital(l, n=9) = sort(digits(l)) == [1:n;]\n", "\n", "# Finds the most common elements in a counter object\n", "most_common(ct) = sort(collect(ct.map), by=p->p[2], rev=true)\n", "most_common(ct, n) = Base.select(collect(ct.map), 1:n, by=p->p[2], rev=true)\n", "\n", "# An iterator of prime numbers\n", "primeiter(n=2) = filter(isprime, countfrom(big(n)))\n", "\n", "# Returns the integer value of a hypotenuse\n", "ihypot(a,b) = isqrt(a^2 + b^2);\n", "\n", "# Returns square numbers up to hi (inclusive)\n", "function square_numbers(hi)\n", " l = []\n", " for n in countfrom()\n", " sq = n^2\n", " if sq <= hi\n", " push!(l, sq)\n", " else\n", " break\n", " end\n", " end\n", " l\n", "end\n", "\n", "# Returns all non-square numbers up to hi (inclusive)\n", "non_squares(hi) = setdiff(1:hi, square_numbers(hi))\n", "\n", "triangular(n) = div(n * (n + 1), 2)\n", "pentagonal(n) = div(3*n^2 - n, 2)\n", "hexagonal(n) = div(2*n*(2*n -1), 2)\n", "\n", "function divisors(n)\n", " n == 0 && return []\n", " l = [1]\n", " for (p,e) in factor(n)\n", " l = reduce(vcat, l, [l * p^j for j in 1:e])\n", " end\n", " l\n", "end\n", "\n", "proper_divisors(n) = divisors(n)[1:end-1];" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 1](https://projecteuler.net/problem=1)\n", "\n", "Add all the natural numbers below one thousand that are multiples of 3 or 5." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.087482 seconds (36.03 k allocations: 1.515 MB)\n" ] }, { "data": { "text/html": [ "233168" ], "text/plain": [ "233168" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 999\n", "@time sum(union(0:3:L, 0:5:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 2](https://projecteuler.net/problem=2)\n", "\n", "Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.108539 seconds (30.94 k allocations: 1.356 MB)\n" ] }, { "data": { "text/html": [ "4613732" ], "text/plain": [ "4613732" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 4*10^6\n", "function p2()\n", " l = []\n", " for n in countfrom()\n", " push!(l, fibonaccinum(n))[end] > L && break\n", " end\n", " sum(filter(iseven, l))\n", "end\n", "\n", "@time p2()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 3](https://projecteuler.net/problem=3)\n", "\n", "What is the largest prime factor of the number 600851475143?" ] }, { "cell_type": "code", "execution_count": 89, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000030 seconds (20 allocations: 1.219 KB)\n" ] }, { "data": { "text/html": [ "6857" ], "text/plain": [ "6857" ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time maximum(keys(factor(600851475143)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 4](https://projecteuler.net/problem=4)\n", "\n", "Find the largest palindrome made from the product of two 3-digit numbers." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.415372 seconds (2.95 M allocations: 180.946 MB, 6.26% gc time)\n" ] }, { "data": { "text/html": [ "906609" ], "text/plain": [ "906609" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time maximum(filter(ispalindrome, map(prod, combinations(100:999, 2))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 5](https://projecteuler.net/problem=5)\n", "\n", "What is the smallest number divisible by each of the numbers 1 to 20?" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.053492 seconds (17.82 k allocations: 820.314 KB)\n" ] }, { "data": { "text/html": [ "232792560" ], "text/plain": [ "232792560" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time lcm(1:20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 6](https://projecteuler.net/problem=6)\n", "\n", "Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.019625 seconds (4.37 k allocations: 202.390 KB)\n" ] } ], "source": [ "@time sum(1:100)^2 - sum(square_numbers(100))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 7](https://projecteuler.net/problem=7)\n", "\n", "Find the 10001st prime." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.129407 seconds (358.19 k allocations: 8.060 MB, 5.68% gc time)\n" ] }, { "data": { "text/html": [ "104743" ], "text/plain": [ "104743" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time nth(primeiter(), 10001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 8](https://projecteuler.net/problem=8)\n", "\n", "Discover the largest product of 13 consecutive digits in the 1000-digit number." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.067704 seconds (25.30 k allocations: 1.179 MB)\n" ] }, { "data": { "text/html": [ "23514624000" ], "text/plain": [ "23514624000" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = [parse(Int, c) for c in readstring(\"p/p008_number.txt\")]\n", "\n", "@time maximum(i -> prod(n[i:i+12]), 1:length(n)-12)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 9](https://projecteuler.net/problem=9)\n", "\n", "Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.128624 seconds (658.47 k allocations: 35.793 MB, 3.37% gc time)\n" ] }, { "data": { "text/html": [ "31875000" ], "text/plain": [ "31875000" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time first(a*b*ihypot(a,b) for (a,b) in combinations(1:500, 2) if a + b + hypot(a,b) == 1000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 10](https://projecteuler.net/problem=10)\n", "\n", "Calculate the sum of all the primes below two million." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.093572 seconds (3.46 k allocations: 2.692 MB)\n" ] }, { "data": { "text/html": [ "142913828922" ], "text/plain": [ "142913828922" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 2*10^6\n", "@time sum(primes(L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 11](https://projecteuler.net/problem=11)\n", "\n", "What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.696232 seconds (341.82 k allocations: 14.091 MB, 1.41% gc time)\n" ] }, { "data": { "text/html": [ "70600674" ], "text/plain": [ "70600674" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = readdlm(\"p/p011_grid.txt\", Int)\n", "\n", "function p11()\n", " n = size(a, 1)\n", " line_value(start, direction) = prod(k -> a[start[1] + direction[1]*k, start[2] + direction[2]*k], 0:3)\n", " directions = filter(d -> d != (0,0), product(-1:1, -1:1))\n", " maximum(line_value(start, direction) for start in product(4:n-4, 4:n-4), direction in directions)\n", "end\n", "\n", "@time p11()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 12](https://projecteuler.net/problem=12)\n", "\n", "What is the value of the first triangle number to have over five hundred divisors?" ] }, { "cell_type": "code", "execution_count": 88, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.494830 seconds (1.10 M allocations: 62.531 MB, 1.86% gc time)\n" ] }, { "data": { "text/html": [ "76576500" ], "text/plain": [ "76576500" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time ifirst(n -> length(divisors(n)) > 500, imap(triangular, countfrom()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 13](https://projecteuler.net/problem=13)\n", "\n", "Find the first ten digits of the sum of one-hundred 50-digit numbers." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.102453 seconds (36.08 k allocations: 1.535 MB)\n" ] }, { "data": { "text/html": [ "5537376230" ], "text/plain": [ "5537376230" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = readdlm(\"p/p013_numbers.txt\", BigInt)\n", "@time Digits.select(sum(a), 1:10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 14](https://projecteuler.net/problem=14)\n", "\n", "Which starting number, under one million, produces the longest collatz chain?" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.987422 seconds (31.25 k allocations: 8.982 MB, 0.61% gc time)\n" ] } ], "source": [ "L = 10^6\n", "function collatz(n)\n", " n == 1 && return 1\n", " return iseven(n) ? collatz(div(n,2)) + 1 : collatz(3*n + 1) + 1\n", "end\n", " \n", "@time indmax(map(collatz, 1:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 15](https://projecteuler.net/problem=15)\n", "\n", "Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?\n", "\n", "Analysis: To get to the corner, you need to go down exactly 20 times in a total of 40 moves, with each step being a choice between two options. This is given by the binomial distribution. " ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000015 seconds (5 allocations: 176 bytes)\n" ] }, { "data": { "text/html": [ "137846528820" ], "text/plain": [ "137846528820" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time binomial(40, 20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 16](https://projecteuler.net/problem=16)\n", "\n", "What is the sum of the digits of the number 2^1000?" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.015957 seconds (2.73 k allocations: 87.234 KB)\n" ] }, { "data": { "text/html": [ "1366" ], "text/plain": [ "1366" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time sum(digits(big(2)^1000))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 17](https://projecteuler.net/problem=17)\n", "\n", "How many letters would be needed to write all the numbers in words from 1 to 1000?" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.123722 seconds (58.32 k allocations: 31.420 MB, 4.22% gc time)\n" ] }, { "data": { "text/html": [ "21124" ], "text/plain": [ "21124" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function english(n)\n", " ones = [\"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\", \"ten\", \"eleven\", \n", " \"twelve\", \"thirteen\", \"fourteen\", \"fifteen\", \"sixteen\", \"seventeen\", \"eighteen\", \"nineteen\"]\n", " tens = [\"ten\", \"twenty\", \"thirty\", \"forty\", \"fifty\", \"sixty\", \"seventy\", \"eighty\", \"ninety\"]\n", " n == 1000 && return \"onethousand\"\n", " n >= 100 && return ones[fld(n, 100)] * \"hundred\" * (n % 100 > 0 ? \"and\" : \"\") * english(n % 100)\n", " n >= 20 && return tens[fld(n, 10)] * english(n % 10)\n", " n > 0 && return ones[n]\n", " return \"\"\n", "end\n", "\n", "@time length(prod(english, 1:1000))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 18](https://projecteuler.net/problem=18)\n", "\n", "Find the maximum sum traveling from the top of the triangle to the base.\n", "\n", "Analysis: Start at the bottom and go up. Assign each tile the value of itself plus the largest of the two tiles that can lead to it. This will be the maximum sum leading to that tile." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.028874 seconds (7.97 k allocations: 348.880 KB)\n" ] }, { "data": { "text/html": [ "1074" ], "text/plain": [ "1074" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = readdlm(\"p/p018_triangle.txt\")\n", "\n", "function triangle_sum(a)\n", " for row in reverse(1:size(a, 2)-1), col in 1:row\n", " a[row, col] += max(a[row+1, col], a[row+1, col+1])\n", " end\n", " a[1, 1]\n", "end\n", "\n", "@time triangle_sum(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 19](https://projecteuler.net/problem=19)\n", "\n", "How many Sundays fell on the first of the month during the twentieth century?" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.094457 seconds (50.17 k allocations: 2.133 MB)\n" ] }, { "data": { "text/html": [ "171" ], "text/plain": [ "171" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time count(date -> Dates.day(date) == 1 && Dates.dayofweek(date) == 7, Date(1901, 1, 1):Date(2000, 12, 31))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 20](https://projecteuler.net/problem=20)\n", "\n", "Find the sum of digits in 100!" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.061847 seconds (22.51 k allocations: 943.126 KB)\n" ] }, { "data": { "text/html": [ "648" ], "text/plain": [ "648" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time sum(digits(factorial(big(100))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 21](https://projecteuler.net/problem=21)\n", "\n", "Evaluate the sum of all the amicable numbers under 10000." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.877834 seconds (1.87 M allocations: 95.861 MB, 3.95% gc time)\n" ] }, { "data": { "text/html": [ "31626" ], "text/plain": [ "31626" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^4\n", "function amicable(a)\n", " b = sum(proper_divisors(a))\n", " return a != b && sum(proper_divisors(b)) == a\n", "end\n", " \n", "@time sum(filter(amicable, 2:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 22](https://projecteuler.net/problem=22)\n", "\n", "What is the total of all the name scores in the file of first names?" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.104837 seconds (47.44 k allocations: 1.996 MB)\n" ] }, { "data": { "text/html": [ "871198282" ], "text/plain": [ "871198282" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = readdlm(\"p/p022_names.txt\", ',', String)\n", "@time sum(sum(char -> findfirst('A':'Z', char), name) * i for (i, name) in enumerate(sort(vec(a))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 23](https://projecteuler.net/problem=23)\n", "\n", "Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.825126 seconds (13.80 M allocations: 268.302 MB, 4.67% gc time)\n" ] }, { "data": { "text/html": [ "4179871" ], "text/plain": [ "4179871" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 28123\n", "function p23()\n", " s, abundants = 0, Set() \n", " for n in 1:L\n", " sum(proper_divisors(n)) > n && push!(abundants, n)\n", " if !any(a -> n - a in abundants, abundants); s += n; end\n", " end\n", " s\n", "end\n", "\n", "@time p23()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 24](https://projecteuler.net/problem=24)\n", "\n", "What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.088130 seconds (11.15 k allocations: 497.436 KB)\n" ] }, { "data": { "text/html": [ "2783915460" ], "text/plain": [ "2783915460" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time combine_list(nthperm(collect(0:9), 10^6))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 25](https://projecteuler.net/problem=25)\n", "\n", "What is the first term in the Fibonacci sequence to contain 1000 digits?" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.302039 seconds (117.02 k allocations: 5.519 MB)\n" ] }, { "data": { "text/html": [ "4782" ], "text/plain": [ "4782" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 1000\n", "@time ifirst(n -> log10(fibonaccinum(n)) + 1 >= L, countfrom(1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 26](https://projecteuler.net/problem=26)\n", "\n", "Find the value of d < 1000 for which 1/d contains the longest recurring cycle.\n", "\n", "Analysis: https://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators.\n", "The length of the repetend (period of the repeating decimal) of 1/p is equal to the order of 10 modulo p." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.419154 seconds (10.14 M allocations: 303.302 MB, 14.50% gc time)\n" ] }, { "data": { "text/html": [ "983" ], "text/plain": [ "983" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 999\n", "function cycle_length(d)\n", " for k in 1:big(d)\n", " 10^k % d == 1 && return k\n", " end\n", " 0\n", "end\n", " \n", "@time indmax(map(cycle_length, 1:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 27](https://projecteuler.net/problem=27)\n", "\n", "Find a quadratic formula with terms below 1000 that produces the maximum number of primes for consecutive values of n." ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.271666 seconds (789.91 k allocations: 18.744 MB, 3.81% gc time)\n" ] }, { "data": { "text/html": [ "-59231" ], "text/plain": [ "-59231" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 999\n", "consecutive_primes_of_quadratic(a, b) = ifirst(n -> !isprime(n^2 + a*n + b), countfrom())\n", "\n", "@time maximum((consecutive_primes_of_quadratic(a, b), a*b) for a in -L:L, b in primes(L))[2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 28](https://projecteuler.net/problem=28)\n", "\n", "What is the sum of both diagonals in a 1001 by 1001 spiral?" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.016608 seconds (7.07 k allocations: 249.779 KB)\n" ] }, { "data": { "text/html": [ "669171001" ], "text/plain": [ "669171001" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 1001\n", "function p28()\n", " l, diagonal = [1], 1\n", " for sidelength in 3:2:L, corner in 1:4\n", " diagonal += sidelength - 1\n", " push!(l, diagonal)\n", " end\n", " sum(l)\n", "end\n", "\n", "@time p28()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 29](https://projecteuler.net/problem=29)\n", "\n", "How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and \n", "2 ≤ b ≤ 100?" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.256971 seconds (448.86 k allocations: 13.967 MB, 3.47% gc time)\n" ] }, { "data": { "text/html": [ "9183" ], "text/plain": [ "9183" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 100\n", "@time length(unique(a^b for a in 2:big(L), b in 2:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 30](https://projecteuler.net/problem=30)\n", "\n", "Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.\n", "\n", "Analysis: The highest sum of fifth powers of digits for a number with 7 digits is 9^5 * 7 = 413343, which has only 6 digits. So the number must have at most 6 digits." ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.350097 seconds (1.03 M allocations: 124.079 MB, 3.05% gc time)\n" ] }, { "data": { "text/html": [ "443839" ], "text/plain": [ "443839" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi = 10^6\n", "@time sum(filter(n -> n == sum(d -> d^5, digits(n)), 2:hi))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 31](https://projecteuler.net/problem=31)\n", "\n", "How many different ways can 2 pounds be made using any number of coins?\n", "\n", "Analysis: Dynamic programming. Approach described here: https://en.wikipedia.org/wiki/Change-making_problem" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.021557 seconds (4.75 k allocations: 213.026 KB)\n" ] }, { "data": { "text/html": [ "73682" ], "text/plain": [ "73682" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function find_ways(l)\n", " ways = vcat([1], zeros(Int, l[end]))\n", " for i in 1:length(l) -1, j in 1:length(ways) - l[i]\n", " ways[l[i] + j] += ways[j]\n", " end\n", " ways[end]\n", "end\n", "\n", "@time find_ways([1,2,5,10,20,50,100, 200]) + 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 32](https://projecteuler.net/problem=32)\n", "\n", "Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.\n", "\n", "Analysis: For *a* x *b* to be a 9-digit number, either *a* is 1-digit and *b* is 4-digit, or *a* is 2-digit and *b* is 3-digit. So *a* can be at most 2 digit and *b* at most 4 digit. (This could easily be optimized further.)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.697287 seconds (10.06 M allocations: 913.936 MB, 11.14% gc time)\n" ] }, { "data": { "text/html": [ "45228" ], "text/plain": [ "45228" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi_a, hi_b = 100, 10000\n", "@time sum(Set(a*b for a in 1:hi_a, b in 1:hi_b if ispandigital(combine_list([a,b, a*b]))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 33](https://projecteuler.net/problem=33)\n", "\n", "Discover all the fractions with an curious cancelling method." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.154890 seconds (58.61 k allocations: 3.355 MB)\n" ] }, { "data": { "text/html": [ "100" ], "text/plain": [ "100" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "curious_cancelling(num, den) = digits(num)[1] == digits(den)[2] && digits(num)[2] / digits(den)[1] == num / den && num != den\n", "\n", "@time Int(prod(den / num for num in 10:99, den in 10:99 if curious_cancelling(num, den)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 34](https://projecteuler.net/problem=34)\n", "\n", "Find the sum of all numbers which are equal to the sum of the factorial of their digits.\n", "\n", "Analysis: 9! x 8 has only 7 digits, so an upper bound is 9! * 7." ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.170661 seconds (10.19 M allocations: 748.111 MB, 15.88% gc time)\n" ] }, { "data": { "text/html": [ "40730" ], "text/plain": [ "40730" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi = factorial(9)*7\n", "@time sum(filter(n -> sum(map(factorial, digits(n))) == n, 3:hi))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 35](https://projecteuler.net/problem=35)\n", "\n", "How many circular primes are there below one million?" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.174397 seconds (465.75 k allocations: 46.426 MB, 4.10% gc time)\n" ] }, { "data": { "text/html": [ "55" ], "text/plain": [ "55" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^6\n", "is_circular(n) = all(isprime, combine(crop(n, i), crop(n, i - ndigits(n))) for i in 1:ndigits(n))\n", "@time count(is_circular, primes(L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 36](https://projecteuler.net/problem=36)\n", "\n", "Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2." ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.302072 seconds (1.03 M allocations: 124.354 MB, 4.38% gc time)\n" ] }, { "data": { "text/html": [ "872187" ], "text/plain": [ "872187" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^6\n", "@time sum(filter(n -> ispalindrome(n) && bin(n) == reverse(bin(n)), 1:L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 37](https://projecteuler.net/problem=37)\n", "\n", "Find the sum of the only eleven primes that are both truncatable from left to right and right to left." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.235966 seconds (8.69 M allocations: 238.342 MB, 11.81% gc time)\n" ] } ], "source": [ "function p37()\n", " l = []\n", " for n in primeiter(10)\n", " all(isprime, crop(n, i) for i in -ndigits(n)+1:ndigits(n)-1) && push!(l, n)\n", " length(l) == 11 && return(sum(l))\n", " end\n", "end\n", "\n", "@time p37()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 38](https://projecteuler.net/problem=38)\n", "\n", "What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n)?\n", "\n", "Analysis: Each increment of *n* adds at least as many digits as the number has. So *n* must be less than 10, and the number of digits in the base number multiplied by n must be at most 9. (This could easily be optimized further.)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.223927 seconds (181.81 k allocations: 12.655 MB, 5.99% gc time)\n" ] }, { "data": { "text/html": [ "932718654" ], "text/plain": [ "932718654" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time maximum(filter(ispandigital, combine_list([a*j for j in 1:n]) for n in 2:10 for a in 1:10^(div(9, n))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 39](https://projecteuler.net/problem=39)\n", "\n", "Find the perimeter <= 1000 for which there is the highest number of right-angled triangles with integer side lengths." ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.341787 seconds (807.61 k allocations: 44.938 MB, 2.94% gc time)\n" ] }, { "data": { "text/html": [ "840" ], "text/plain": [ "840" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 1000\n", "@time Int(mode(filter(p -> p == round(p) && p <= L, [a + b + hypot(a, b) for (a,b) in combinations(1:L/2, 2)])))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 40](https://projecteuler.net/problem=40)\n", "\n", "An irrational decimal fraction is created by concatenating the positive integers: If dn represents the nth digit, find the value of the following expression: d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.475002 seconds (18.04 M allocations: 762.385 MB, 6.04% gc time)\n" ] }, { "data": { "text/html": [ "210" ], "text/plain": [ "210" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time prod(d -> parse(Int, join(1:10^6)[10^d]), 1:6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 41](https://projecteuler.net/problem=41)\n", "\n", "What is the largest n-digit pandigital prime that exists?\n", "\n", "Analysis: 9 and 8 digit pandigital numbers are divisible by 3 and thus cannot be prime. We find the largest prime by starting from the highest pandigital number and going down until we find a prime." ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.181940 seconds (881.82 k allocations: 102.983 MB, 9.96% gc time)\n" ] }, { "data": { "text/html": [ "7652413" ], "text/plain": [ "7652413" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi = 10^7\n", "@time ifirst(n -> ispandigital(n, ndigits(n)), reverse(primes(hi)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 42](https://projecteuler.net/problem=42)\n", "\n", "Find the number of triangle words in a list." ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.064393 seconds (78.98 k allocations: 7.379 MB)\n" ] }, { "data": { "text/html": [ "162" ], "text/plain": [ "162" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = [strip(w) for w in readdlm(\"p/p042_words.txt\", ',')]\n", "\n", "@time count(word -> sum(char -> Int(char) - Int('A') + 1, word) in Set(map(triangular, 1:28)), a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 43](https://projecteuler.net/problem=43)\n", "\n", "Find the sum of all pandigital numbers with a sub-string divisibility property.\n", "\n", "Analysis: Build the pandigital number recursively, adding one new digit at a time, so that the property is true with each addition." ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.081455 seconds (60.74 k allocations: 3.676 MB)\n" ] }, { "data": { "text/html": [ "1695334890" ], "text/plain": [ "1695334890" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function get_sum(l)\n", " any(i -> (length(l) >= i && combine_list(l[end+1-i:end+3-i]) % primes(17)[10-i] != 0), 3:9) && return 0\n", " length(l) == 9 && return sum(combine_list(l))\n", " s = 0\n", " for elem in collect(setdiff(Set(0:9), Set(l)))\n", " s += get_sum(insert!(copy(l), 1, elem))\n", " end\n", " s\n", "end\n", "\n", "@time get_sum(Int[]) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 44](https://projecteuler.net/problem=44)\n", "\n", "Find the pair of pentagonal numbers for which their sum and difference are pentagonal and the difference is minimized.\n", "\n", "Analysis: Go through the pentagonals in increasing order. For each pentagonal, look for a smaller pentagonal that satisfies the criteria, and save the one with minimized difference. Once the difference between successive pentagonals is larger than the minimum difference found, stop the search." ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 3.716701 seconds (23.05 k allocations: 221.304 MB, 3.30% gc time)\n" ] }, { "data": { "text/html": [ "5482660" ], "text/plain": [ "5482660" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p44()\n", " hi = 10^7\n", " pentas = map(pentagonal, 1:hi)\n", " pentaset = Set(pentas)\n", " mindiff = maximum(pentas)\n", " for i in countfrom(1)\n", " for j in reverse(1:i-1)\n", " diff = pentas[i] - pentas[j]\n", " diff > mindiff && break\n", " if diff in pentaset && pentas[i] + pentas[j] in pentaset\n", " mindiff = diff\n", " end\n", " end\n", " pentas[i+1] - pentas[i] > mindiff && break\n", " end\n", " mindiff\n", "end\n", "\n", "@time p44()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 45](https://projecteuler.net/problem=45)\n", "\n", "Find the next triangle number that is also pentagonal and hexagonal." ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.131044 seconds (20.44 k allocations: 13.296 MB)\n" ] }, { "data": { "text/html": [ "1533776805" ], "text/plain": [ "1533776805" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi = 10^5\n", "@time first(intersect(\n", " Set(map(triangular, 286:hi)), \n", " Set(map(pentagonal, 166:hi)),\n", " Set(map(hexagonal, 144:hi))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 46](https://projecteuler.net/problem=46)\n", "\n", "What is the smallest odd composite that is not a goldbach number (can be written as the sum of a prime and twice a square)?" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.868557 seconds (1.46 M allocations: 46.790 MB, 8.33% gc time)\n" ] }, { "data": { "text/html": [ "5777" ], "text/plain": [ "5777" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p46()\n", " hi = 10^4\n", " goldbachs = Set(prime + 2 * square for prime in primes(hi), square in square_numbers(hi))\n", " ifirst(n -> !(isprime(n) || n in goldbachs), 3:2:hi)\n", "end\n", "\n", "@time p46()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 47](https://projecteuler.net/problem=47)\n", "\n", "Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.630264 seconds (1.81 M allocations: 152.956 MB, 5.05% gc time)\n" ] }, { "data": { "text/html": [ "134043" ], "text/plain": [ "134043" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time ifirst(n -> all(i -> length(factor(n+i)) == 4, 0:3), countfrom())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 48](https://projecteuler.net/problem=48)\n", "\n", "Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.161696 seconds (144.25 k allocations: 6.613 MB, 2.69% gc time)\n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "WARNING: could not attach metadata for @simd loop.\n" ] }, { "data": { "text/html": [ "9110846700" ], "text/plain": [ "9110846700" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time sum(n -> n^n, 1:big(1000)) % 10^10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 49](https://projecteuler.net/problem=49)\n", "\n", "Find the members of a 4-digits sequence." ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.105660 seconds (91.61 k allocations: 6.129 MB)\n" ] }, { "data": { "text/html": [ "296962999629" ], "text/plain": [ "296962999629" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_unusual_series(seq) = all(isanagram(seq[1], elem) for elem in seq) && seq[1] != 1487 && all(isprime, seq)\n", " \n", "@time combine_list(ifirst(is_unusual_series, [[a, a + 3330, a + 6660] for a in 1000:3340]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 50](https://projecteuler.net/problem=50)\n", "\n", "Which prime, below one-million, can be written as the sum of the most consecutive primes?" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.267989 seconds (281.31 k allocations: 8.348 MB)\n" ] }, { "data": { "text/html": [ "997651" ], "text/plain": [ "997651" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p50()\n", " L = 10^6\n", " prs, l = primes(L), []\n", " for i in 1:length(prs)-1\n", " prsum = prs[i]\n", " for j in i+1:length(prs)\n", " prsum += prs[j]\n", " prsum > L && break\n", " isprime(prsum) && push!(l, (j-i, prsum))\n", " end\n", " end\n", " maximum(l)[2]\n", "end\n", "\n", "@time p50()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 51](https://projecteuler.net/problem=51)\n", "\n", "Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.\n", "\n", "Analysis: Start with 5-digit numbers, in increasing order, looking at all subsets. If none are found fulfilling the criteria, look at 6-digits numbers, etc." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.876182 seconds (5.33 M allocations: 615.901 MB, 4.84% gc time)\n" ] }, { "data": { "text/html": [ "121313" ], "text/plain": [ "121313" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p51()\n", " function replacements(prime, subset)\n", " digits = 1 in subset ? collect(1:9) : collect(0:9)\n", " [Digits.replace(prime, subset, fill(d, length(subset))) for d in digits]\n", " end\n", "\n", " family_size(prime, subset) = sum(isprime, replacements(prime, subset))\n", " \n", " for n in countfrom(5), prime in primes(10^n, 10^(n+1)), subset in subsets(1:n)\n", " if family_size(prime, subset) == 8 && prime in replacements(prime, subset)\n", " return prime\n", " end\n", " end\n", "end\n", "\n", "@time p51()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 52](https://projecteuler.net/problem=52)\n", "\n", "Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits." ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.151504 seconds (1.15 M allocations: 113.272 MB, 9.68% gc time)\n" ] }, { "data": { "text/html": [ "142857" ], "text/plain": [ "142857" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time ifirst(n -> all(m -> sort(digits(n*m)) == sort(digits(n)), 2:6), countfrom(2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 53](https://projecteuler.net/problem=53)\n", "\n", "How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.091601 seconds (134.87 k allocations: 4.946 MB, 5.35% gc time)\n" ] }, { "data": { "text/html": [ "4075" ], "text/plain": [ "4075" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 100\n", "@time count(t -> binomial(reverse(big(t))...) > 10^6, combinations(1:L, 2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 54](https://projecteuler.net/problem=54)\n", "\n", "How many poker hands does Player 1 win?" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.796863 seconds (1.52 M allocations: 68.323 MB, 1.73% gc time)\n" ] }, { "data": { "text/html": [ "376" ], "text/plain": [ "376" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function rank_hand(hand)\n", " vals = map(card -> searchindex(\"x23456789TJQKA\", card[1]), hand)\n", " suits = map(card -> card[2], hand)\n", " flush = length(unique(suits)) == 1\n", " straight = maximum(vals) - minimum(vals) == 4 && allunique(vals)\n", " of_a_kind = map(t -> last(t), most_common(counter(vals)))\n", " if straight && flush\n", " order = \"8_\"\n", " elseif 4 in of_a_kind\n", " order = \"7_\"\n", " elseif 3 in of_a_kind && 2 in of_a_kind\n", " order = \"6_\" \n", " elseif flush\n", " order = \"5_\"\n", " elseif straight\n", " order = \"4_\"\n", " elseif 3 in of_a_kind\n", " order = \"3_\"\n", " elseif count(n -> n==2, of_a_kind) == 2\n", " order = \"2_\"\n", " elseif 2 in of_a_kind\n", " order = \"1_\"\n", " else\n", " order = \"0_\"\n", " end\n", " sorted_values = map(t -> first(t), sort(collect(counter(vals)), by=t->reverse(t), rev=true))\n", " sorted_values_str = map(value -> lpad(string(value), 2, \"0\"), sorted_values)\n", " return order * join(sorted_values_str, \"_\")\n", "end\n", "\n", "a = readdlm(\"p/p054_poker.txt\", String)\n", "@time sum(mapslices(l -> rank_hand(l[1:5]) > rank_hand(l[6:end]), a, 2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 55](https://projecteuler.net/problem=55)\n", "\n", "How many Lychrel numbers are there below ten-thousand?" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.648186 seconds (6.67 M allocations: 187.056 MB, 22.30% gc time)\n" ] }, { "data": { "text/html": [ "249" ], "text/plain": [ "249" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 9999\n", "function is_lychrel(n)\n", " n = big(n)\n", " for _ in 1:50\n", " n += reversedigits(n)\n", " ispalindrome(n) && return false\n", " end\n", " true\n", "end\n", "\n", "@time count(is_lychrel, 1:L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 56](https://projecteuler.net/problem=56)\n", "\n", "Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.648536 seconds (7.02 M allocations: 193.326 MB, 19.34% gc time)\n" ] }, { "data": { "text/html": [ "972" ], "text/plain": [ "972" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 99\n", "@time maximum(sum(digits(a^big(b))) for a in 1:L, b in 1:L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 57](https://projecteuler.net/problem=57)\n", "\n", "In the first one-thousand expansions of the square root of 2, how many fractions contain a numerator with more digits than denominator?" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.159370 seconds (207.33 k allocations: 7.543 MB, 9.99% gc time)\n" ] }, { "data": { "text/html": [ "153" ], "text/plain": [ "153" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p57()\n", " n = 0\n", " expander = big(2)\n", " for _ in 1:1000\n", " expander = 2 + 1 // expander\n", " fraction = 1 + 1 // expander\n", " if ndigits(num(fraction)) > ndigits(den(fraction))\n", " n += 1\n", " end\n", " end\n", " n\n", "end\n", "\n", "@time p57()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 58](https://projecteuler.net/problem=58)\n", "\n", "What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.055767 seconds (45.11 k allocations: 932.160 KB)\n" ] }, { "data": { "text/html": [ "26241" ], "text/plain": [ "26241" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p58()\n", " nprimes, diagonal = 0, 1\n", " for sidelength in countfrom(3,2), corner in 1:4\n", " diagonal += sidelength - 1\n", " nprimes += isprime(diagonal)\n", " if nprimes / (2 * sidelength - 1) < 0.1\n", " return sidelength\n", " end\n", " end\n", "end\n", "\n", "@time p58()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 59](https://projecteuler.net/problem=59)\n", "\n", "Find the key that decrypts a file.\n", "\n", "Analysis: We check all possible keys, and identify the key that finds at least 7 common words." ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.872329 seconds (654.20 k allocations: 73.307 MB, 2.00% gc time)\n" ] }, { "data": { "text/html": [ "107359" ], "text/plain": [ "107359" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "text = readdlm(\"p/p059_cipher.txt\", ',', Int)\n", "\n", "function p59()\n", " common_words = [\"the\", \"and\", \"be\", \"of\", \"that\", \"have\", \"for\", \"it\", \"not\", \"on\", \"with\", \"you\"]\n", " many_common_words(text) = count(word -> Base.contains(text, word), common_words) > 6\n", " convert(text, key) = [letter $ key[1 + (i - 1) % 3] for (i, letter) in enumerate(text)]\n", " decrypt(text, key) = join(map(Char, convert(text, key)))\n", " key = ifirst(key -> many_common_words(decrypt(text, key)), product(97:123, 97:123, 97:123))\n", " sum(convert(text, key))\n", "end\n", "\n", "@time p59()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 60](https://projecteuler.net/problem=60)\n", "\n", "Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.\n", "\n", "Analysis: We add the primes recursively one at a time, so that all primes in the set concatenate with each other." ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.971747 seconds (4.14 M allocations: 85.908 MB, 1.91% gc time)\n" ] } ], "source": [ "function p60()\n", " hi = 10^4\n", " pr = primes(hi)\n", "\n", " @noinline all_concatenate(p_indices, i) = \n", " all(j -> isprime(combine(pr[j], pr[i])) && isprime(combine(pr[i], pr[j])), p_indices)\n", "\n", " function find_primeset(p_indices)\n", " length(p_indices) == 5 && return p_indices\n", " start = isempty(p_indices) ? 1 : p_indices[end] + 1\n", "\n", " for i in start:length(pr)\n", " if all_concatenate(p_indices, i)\n", " result = find_primeset(push!(copy(p_indices), i))\n", " result != nothing && return result\n", " end\n", " end\n", " end\n", " sum(pr[find_primeset([])])\n", "end\n", "\n", "@time p60()" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "2" ], "text/plain": [ "2" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ndigits(38)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 61](https://projecteuler.net/problem=61)\n", "\n", "Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.\n", "\n", "Analysis: Build the sets recursively. Each new addition to the set must be cyclic with the previous number, and be of a new polygonal type." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.232055 seconds (529.59 k allocations: 36.667 MB, 3.46% gc time)\n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "WARNING: Method definition p61() in module Main at In[14]:2 overwritten at In[15]:2.\n" ] }, { "data": { "text/html": [ "28684" ], "text/plain": [ "28684" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p61()\n", " len, ndigit, hi_poly = 6, 4, 200\n", " square(n) = n^2\n", " heptagonal(n) = div(n * (5*n - 3), 2)\t\n", " octogonal(n) = n * (3*n - 2)\n", " vals = Dict()\n", " for (nsides, polygon) in zip(3:8, [triangular, square, pentagonal, hexagonal, heptagonal, octogonal])\n", " vals[nsides] = filter(n -> ndigit == ndigits(n), map(n -> polygon(n), 1:hi_poly))\n", " end\n", " arelinked(n1, n2) = digits(crop(n1, 2)) == digits(crop(n2, -2))\n", "\n", " function fits(chain, value)\n", " isempty(chain) && return true\n", " ! arelinked(chain[end], value) && return false\n", " if length(chain) == len -1\n", " return arelinked(value, chain[1])\n", " else\n", " return true\n", " end\n", " end\n", "\n", " function get_chain(chain, polygons) \n", " length(chain) == len && return chain\n", " for polygon in setdiff(Set(3:8), polygons), val in vals[polygon]\n", " if fits(chain, val)\n", " new_chain = get_chain(push!(copy(chain), val), push!(copy(polygons), polygon))\n", " new_chain != nothing && return new_chain\n", " end\n", " end\n", " end\n", "\n", " sum(get_chain([], Set()))\n", "end\n", " \n", "@time p61()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 62](https://projecteuler.net/problem=62)\n", "\n", "Find the smallest cube for which exactly five permutations of its digits are cube.\n", "\n", "Analysis: Look at all cubes with a specific number of digits, make a dictionary with keys as the digits, and values as all the cubes that contain exactly those digits. Find all the keys that contain exactly 5 cubes. If there are any, return the smallest of these cubes. If there aren't any, clear the dictionary, and look at all cubes with one more digit." ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.548282 seconds (520.43 k allocations: 24.302 MB, 1.05% gc time)\n" ] }, { "data": { "text/html": [ "127035954683" ], "text/plain": [ "127035954683" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p62()\n", " cubes, nd = DefaultDict(Array{Int,1}), 1\n", " for n in countfrom(1)\n", " cube = n^3\n", " if ndigits(cube) > nd\n", " l = [v[1] for v in values(cubes) if length(v) == 5]\n", " if !isempty(l) \n", " return minimum(l)\n", " else\n", " cubes, nd = DefaultDict(Array{Int,1}), ndigits(cube)\n", " end\n", " end\n", " push!(cubes[sort(digits(cube))], cube)\n", " end\n", "end\n", "\n", "@time p62()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 63](https://projecteuler.net/problem=63)\n", "\n", "How many n-digit positive integers exist which are also an nth power?\n", "\n", "Analysis: *a* cannot excede 10 since 10^n is n+1 digits long." ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.092655 seconds (58.58 k allocations: 1.986 MB)\n" ] }, { "data": { "text/html": [ "49" ], "text/plain": [ "49" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hi_a, hi_n = 10, 100\n", "@time sum(ndigits(a^n) == n for a in 1:big(hi_a), n in 1:hi_n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 64](https://projecteuler.net/problem=64)\n", "\n", "How many continued fractions for N ≤ 10000 have an odd period?\n", "\n", "Analysis: Algorithm from https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Algorithm" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.143329 seconds (2.35 M allocations: 44.425 MB, 9.25% gc time)\n" ] }, { "data": { "text/html": [ "1322" ], "text/plain": [ "1322" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^4\n", "function continued_fraction_period(n)\n", " m, d = 0, 1\n", " a0 = floor(sqrt(n))\n", " a = [a0]\n", " while 2 * a0 != a[end]\n", " m = d * a[end] - m\n", " d = (n - m^2) / d\n", " push!(a, floor((a0 + m) / d))\n", " end\n", " return a\n", "end\n", " \n", "@time count(n -> iseven(length(continued_fraction_period(n))), non_squares(L))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 65](https://projecteuler.net/problem=65)\n", "\n", "Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e." ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.037850 seconds (6.32 k allocations: 271.143 KB)\n" ] }, { "data": { "text/html": [ "272" ], "text/plain": [ "272" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p65()\n", " cont_fraction(n) = n % 3 == 2 ? 2*n : 1\n", " num, den = 2, big(1)\n", " for n in 1:100\n", " num, den = cont_fraction(n) * den + num, num\n", " end\n", " sum(digits(den))\n", "end\n", "\n", "@time p65()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 66](https://projecteuler.net/problem=66)\n", "\n", "Solve diophantine equations.\n", "\n", "Analysis: Method from https://en.wikipedia.org/wiki/Chakravala_method" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.150747 seconds (676.78 k allocations: 16.425 MB, 3.89% gc time)\n" ] }, { "data": { "text/html": [ "661" ], "text/plain": [ "661" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function chakravala(N)\n", " sq = BigInt(floor(sqrt(N)))\n", " a, b, k, m = sq, 1, sq^2 - N, sq\n", " while k != 1\n", " m = div((m + sq), k) * k - m \n", " a, b, k = div((a*m + N*b), abs(k)), div((a + b*m), abs(k)), div((m^2 - N), k)\n", " end\n", " a\n", "end\n", " \n", "@time maximum(map(i -> (chakravala(i), i), non_squares(1000)))[2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 67](https://projecteuler.net/problem=67)\n", "\n", "Find the maximum sum traveling from the top of the triangle to the base.\n", "\n", "Analysis: Reuse of code from problem 18." ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000529 seconds (8.65 k allocations: 135.188 KB)\n" ] }, { "data": { "text/html": [ "7273" ], "text/plain": [ "7273" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = readdlm(\"p/p067_triangle.txt\")\n", "@time triangle_sum(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 68](https://projecteuler.net/problem=68)\n", "\n", "What is the maximum 16-digit string for a \"magic\" 5-gon ring?\n", "\n", "Analysis: 10 has to be in the outer ring for the ring to have 16 digits. We first select the 5 numbers 1:9 that make up the inner ring. The outer numbers is determined from these." ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.455496 seconds (298.26 k allocations: 13.965 MB, 3.16% gc time)\n" ] }, { "data": { "text/html": [ "6531031914842725" ], "text/plain": [ "6531031914842725" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p98()\n", " strings = []\n", " for innerset in subsets(collect(1:9), 5)\n", " outerset = setdiff(Set(1:10), Set(innerset))\n", " groupsum = (2 * sum(innerset) + sum(outerset)) / 5\n", " groupsum != round(groupsum) && continue\n", " for inner in permutations(innerset)\n", " outer = [Int(groupsum) - inner[i] - inner[i%5+1] for i in 1:5]\n", " (Set(outer) != outerset || outer[1] != minimum(outer)) && continue\n", " ring = [[outer[i], inner[i], inner[i%5+1]] for i in 1:5]\n", " push!(strings, combine_list(vcat(ring...)))\n", " end\n", " end\n", " maximum(strings)\n", "end\n", "\n", "@time p98()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 69](https://projecteuler.net/problem=69)\n", "\n", "Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.\n", "\n", "Analysis: n/φ(n) is lowest when n has the most prime factors compared to its size. This is the case when n is a primorial" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "2310" ], "text/plain": [ "2310" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "primorial(ifirst(n -> primorial(n+1) > L, countfrom()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 70](https://projecteuler.net/problem=70)\n", "\n", "Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum\n", "\n", "Analysis: φ is lowest when its the product of exactly two primes. The algorithm searches through pairs of primes and saves the best pair product." ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.251114 seconds (1.72 M allocations: 107.609 MB, 9.51% gc time)\n" ] }, { "data": { "text/html": [ "8319823" ], "text/plain": [ "8319823" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^7\n", "function p70()\n", " pr = primes(floor(Int, 1.2 * sqrt(L)))\n", " min, min_n = 10, 0\n", " for (p1, p2) in combinations(pr, 2)\n", " n = p1 * p2\n", " φ_n = (1 - p1) * (1 - p2)\n", " if n / φ_n < min && n <= L && isanagram(n, φ_n)\n", " min, min_n = n / φ_n, n\n", " end\n", " end\n", " min_n\n", "end\n", "\n", "@time p70()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 71](https://projecteuler.net/problem=71)\n", "\n", "By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7." ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.654339 seconds (49.91 k allocations: 34.610 MB, 0.65% gc time)\n" ] }, { "data": { "text/html": [ "428570" ], "text/plain": [ "428570" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^6\n", "@time num(maximum(filter(fr -> fr != 3//7, map(n -> fld(3*n, 7) // n, 1:L))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 72](https://projecteuler.net/problem=72)\n", "\n", "How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?\n", "\n", "Analysis: Go through the primes in order. For each prime, update all the values of d and discount the denominators for which the fraction could be reduced by that prime." ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.408494 seconds (23.94 M allocations: 432.392 MB, 5.63% gc time)\n" ] }, { "data": { "text/html": [ "303963552391" ], "text/plain": [ "303963552391" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 10^6\n", "function p72()\n", " d = [i-1 for i in 1:L]\n", " for n in 2:L\n", " if d[n] == n - 1\n", " for i in 2*n:n:L\n", " d[i] -= div(d[i], n)\n", " end\n", " end\n", " end\n", " sum(d)\n", "end\n", "\n", "@time p72()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 73](https://projecteuler.net/problem=73)\n", "\n", "How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.013527 seconds (54.37 k allocations: 2.154 MB)\n" ] }, { "data": { "text/html": [ "7295372" ], "text/plain": [ "7295372" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 12000\n", "@time sum(gcd(num, den) == 1 for den in 4:L for num in div(den, 3)+1:div(den, 2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 74](https://projecteuler.net/problem=74)\n", "\n", "How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?\n", "\n", "Analysis: For each starting number we find the chain, and add all the numbers in that chain to 'lengths' dictionary. This dictionary is used to find the lengths of future chains." ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.054663 seconds (7.02 M allocations: 477.947 MB, 14.84% gc time)\n" ] }, { "data": { "text/html": [ "402" ], "text/plain": [ "402" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p74()\n", " lengths = Dict(169 => 3, 363601 => 3, 1454 => 3, 871 => 2, 45361 => 2, 872 => 2, 45362 => 2)\n", " for start in 1:10^6\n", " chain = [start]\n", " while true\n", " if chain[end] in keys(lengths)\n", " for (i, elem) in enumerate(chain)\n", " lengths[elem] = length(chain) - i + lengths[chain[end]]\n", " end\n", " break\n", " end\n", " push!(chain, sum(map(factorial, digits(chain[end]))))\n", " if chain[end] == chain[end-1]\n", " lengths[chain[end]] = length(chain) - 1\n", " break\n", " end\n", " end\n", " end\n", " count(n -> n == 60, values(lengths))\n", "end\n", "\n", "@time p74()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 75](https://projecteuler.net/problem=75)\n", "\n", "Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?\n", "\n", "Analysis: Formula from https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1.687752 seconds (11.55 M allocations: 233.776 MB, 25.94% gc time)\n" ] }, { "data": { "text/html": [ "161667" ], "text/plain": [ "161667" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p75()\n", " L = 1.5 * 10^6\n", " hi = floor(Int, sqrt(L))\n", " perimeters = []\n", " for n in 1:hi, m in n+1:2:hi\n", " if gcd(m, n) == 1\n", " for k in countfrom()\n", " perimeter = k * (m^2 - n^2 + 2*m*n + m^2 + n^2)\n", " perimeter > L && break\n", " push!(perimeters, perimeter)\n", " end\n", " end\n", " end\n", " count(t -> t[2] == 1, counter(perimeters))\n", "end\n", "\n", "@time p75()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 76](https://projecteuler.net/problem=76)\n", "\n", "How many different ways can one hundred be written as a sum of at least two positive integers?\n", "\n", "Analysis: Reuse of code from problem 31." ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000019 seconds (11 allocations: 2.953 KB)\n" ] }, { "data": { "text/html": [ "190569291" ], "text/plain": [ "190569291" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time find_ways(collect(1:100))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 77](https://projecteuler.net/problem=77)\n", "\n", "What is the first value which can be written as the sum of primes in over five thousand different ways?\n", "\n", "Analysis: Reuse of code from problem 31." ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.008558 seconds (2.16 k allocations: 167.065 KB)\n" ] }, { "data": { "text/html": [ "71" ], "text/plain": [ "71" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = 5000\n", "@time ifirst(n -> find_ways(primes(n)) > L, countfrom(2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 78](https://projecteuler.net/problem=78)\n", "\n", "Let p(n) represent the number of different ways in which n coins can be separated into piles. Find the least value of n for which p(n) is divisible by one million.\n", "\n", "Analysis: Solution from \n", ": \n", "p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ..." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.503586 seconds (65.04 k allocations: 3.902 MB)\n" ] }, { "data": { "text/html": [ "55374" ], "text/plain": [ "55374" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function p78()\n", " pentagonals = filter(n -> n != 0, sort(map(pentagonal, -250:250)))\n", " signs, p = [1,1,-1,-1], [1]\n", " while p[end] != 0\n", " p_n = 0\n", " for i in countfrom()\n", " pentagonals[i] > length(p) && break\n", " p_n = (p_n + signs[(i-1)%4+1] * p[length(p) + 1 - pentagonals[i]]) % 10^6\n", " end\n", " push!(p, p_n)\n", " end\n", " length(p) - 1\n", "end\n", "\n", "@time p78()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 79](https://projecteuler.net/problem=79)\n", "\n", "Analyse the file so as to determine the shortest possible secret passcode of unknown length.\n", "\n", "Analysis: Sort the numbers in order of how many different numbers appear after it." ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.722035 seconds (425.11 k allocations: 17.957 MB, 4.04% gc time)\n" ] }, { "data": { "text/plain": [ "\"73162890\"" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "logins = readdlm(\"p/p079_keylog.txt\", String)\n", "\n", "function p79()\n", " numbers_pressed_after = DefaultDict(Set)\n", " for login in Set(logins)\n", " push!(numbers_pressed_after[login[1]], login[2:3]...)\n", " push!(numbers_pressed_after[login[2]], login[3])\n", " push!(numbers_pressed_after[login[3]], \"\")\n", " end\n", " join(map(t -> t[2], sort([(length(v), k) for (k,v) in numbers_pressed_after], rev=true)))\n", "end\n", "\n", "@time p79()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### [Problem 80](https://projecteuler.net/problem=80)\n", "\n", "For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.\n", "\n", "Analysis: This method is used to calculate square roots: http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf" ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 2.047113 seconds (23.22 M allocations: 624.470 MB, 20.91% gc time)\n" ] }, { "data": { "text/html": [ "40886" ], "text/plain": [ "40886" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function dsqrt(n, decs)\n", " a, b = 5*n, big(5)\n", " while length(digits(b)) < decs + 2\n", " if a >= b\n", " a -= b\n", " b += 10\n", " else\n", " a *= 100\n", " b = fld(b, 10) * 100 + 5\n", " end\n", " end\n", " b\n", "end\n", "\n", "@time sum(n -> sum(digits(dsqrt(n, 100))[end-100:end]), non_squares(100))" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 0.5.0", "language": "julia", "name": "julia-0.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "0.5.0" } }, "nbformat": 4, "nbformat_minor": 1 }