{
"metadata": {
"language": "Julia",
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#Project Euler"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Multiples of 3 and 5\n",
"
\n",
"Problem 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.\n",
"\n",
"Find the sum of all the multiples of 3 or 5 below 1000."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function Mult3or5_below(num)\n",
" sum_all = 0\n",
" for i = 1:num\n",
" if ((i%5 == 0) || (i%3 == 0))\n",
" sum_all += i\n",
" end\n",
" end\n",
" return sum_all\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 146,
"text": [
"Mult3or5_below (generic function with 1 method)"
]
}
],
"prompt_number": 146
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Mult3or5_below(999)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 148,
"text": [
"233168"
]
}
],
"prompt_number": 148
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Even Fibonacci numbers\n",
"
\n",
"Problem 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:\n",
"\n",
"1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
"\n",
"By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function SumFibEvens_below(num)\n",
" fib_num_prev = 1\n",
" fib_num = 1\n",
" fib_sum = 0\n",
" answer = 0\n",
" \n",
" while fib_sum < num\n",
" fib_sum = fib_num_prev + fib_num\n",
" fib_num_prev = fib_num\n",
" fib_num = fib_sum\n",
" if fib_sum%2 == 0\n",
" answer += fib_sum\n",
" end\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 65,
"text": [
"SumFibEvens_below (generic function with 1 method)"
]
}
],
"prompt_number": 65
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SumFibEvens_below(4000000)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 66,
"text": [
"4613732"
]
}
],
"prompt_number": 66
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Largest prime factor\n",
"
\n",
"Problem 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The prime factors of 13195 are 5, 7, 13 and 29.\n",
"\n",
"What is the largest prime factor of the number 600851475143 ?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function LargestPrimeFactor(num)\n",
" factor_dict = factor(num)\n",
" return maximum(factor_dict)[1]\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 84,
"text": [
"LargestPrimeFactor (generic function with 1 method)"
]
}
],
"prompt_number": 84
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"LargestPrimeFactor(600851475143)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 83,
"text": [
"6857"
]
}
],
"prompt_number": 83
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Largest palindrome product\n",
"
\n",
"Problem 4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 \u00d7 99.\n",
"\n",
"Find the largest palindrome made from the product of two 3-digit numbers."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function IsPalindrome(num1, num2)\n",
" product = string(num1 * num2) \n",
" return product == reverse(product)\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 39,
"text": [
"IsPalindrome (generic function with 1 method)"
]
}
],
"prompt_number": 39
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IsPalindrome(91,99)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 40,
"text": [
"true"
]
}
],
"prompt_number": 40
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function MaxPalindrome_digits(num)\n",
" min_num = 10^(num-1)\n",
" max_num = int(repeat(\"9\",num))\n",
" product = 0\n",
" answer = 0\n",
" \n",
" for x = min_num:max_num\n",
" for y = min_num:max_num\n",
" product = x * y\n",
" if IsPalindrome(x,y) && product > answer\n",
" answer = product\n",
" end\n",
" end\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 41,
"text": [
"MaxPalindrome_digits (generic function with 1 method)"
]
}
],
"prompt_number": 41
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MaxPalindrome_digits(3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 42,
"text": [
"906609"
]
}
],
"prompt_number": 42
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Smallest multiple\n",
"
\n",
"Problem 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.\n",
"\n",
"What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function SmallestMult(num)\n",
" range_list = Int64[]\n",
" for i = 1:num\n",
" push!(range_list,i)\n",
" end\n",
" answer = lcm(range_list...)\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 101,
"text": [
"SmallestMult (generic function with 1 method)"
]
}
],
"prompt_number": 101
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SmallestMult(20)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 102,
"text": [
"232792560"
]
}
],
"prompt_number": 102
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"lcm(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 176,
"text": [
"232792560"
]
}
],
"prompt_number": 176
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Sum square difference\n",
"
\n",
"Problem 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The sum of the squares of the first ten natural numbers is,\n",
"\n",
"12 + 22 + ... + 102 = 385\n",
"The square of the sum of the first ten natural numbers is,\n",
"\n",
"(1 + 2 + ... + 10)2 = 552 = 3025\n",
"Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 \u2212 385 = 2640.\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",
"collapsed": false,
"input": [
"function SumSqDif(num)\n",
" sumsquares = 0\n",
" runningsum = 0\n",
" for i = 1:num\n",
" sumsquares += i^2\n",
" runningsum += i\n",
" end\n",
" squaresum = runningsum^2\n",
" answer = squaresum - sumsquares\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 218,
"text": [
"SumSqDif (generic function with 1 method)"
]
}
],
"prompt_number": 218
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SumSqDif(100)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 219,
"text": [
"25164150"
]
}
],
"prompt_number": 219
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"10001st prime\n",
"
\n",
"Problem 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.\n",
"\n",
"What is the 10001st prime number?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function Prime(n)\n",
" x = 2\n",
" i = 0\n",
" answer = 0\n",
" while i < n\n",
" if isprime(x)\n",
" answer = x\n",
" i = i + 1\n",
" end\n",
" x = x + 1\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 22,
"text": [
"Prime (generic function with 1 method)"
]
}
],
"prompt_number": 22
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Prime(10001)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 23,
"text": [
"104743"
]
}
],
"prompt_number": 23
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Largest product in a series\n",
"
\n",
"Problem 8"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Find the greatest product of five consecutive digits in the 1000-digit number.\n",
"\n",
"73167176531330624919225119674426574742355349194934\n",
"96983520312774506326239578318016984801869478851843\n",
"85861560789112949495459501737958331952853208805511\n",
"12540698747158523863050715693290963295227443043557\n",
"66896648950445244523161731856403098711121722383113\n",
"62229893423380308135336276614282806444486645238749\n",
"30358907296290491560440772390713810515859307960866\n",
"70172427121883998797908792274921901699720888093776\n",
"65727333001053367881220235421809751254540594752243\n",
"52584907711670556013604839586446706324415722155397\n",
"53697817977846174064955149290862569321978468622482\n",
"83972241375657056057490261407972968652414535100474\n",
"82166370484403199890008895243450658541227588666881\n",
"16427171479924442928230863465674813919123162824586\n",
"17866458359124566529476545682848912883142607690042\n",
"24219022671055626321111109370544217506941658960408\n",
"07198403850962455444362981230987879927244284909188\n",
"84580156166097919133875499200524063689912560717606\n",
"05886116467109405077541002256983155200055935729725\n",
"71636269561882670428252483600823257530420752963450
"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"x = \"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450\""
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 249,
"text": [
"\"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450\""
]
}
],
"prompt_number": 249
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function GrtstProdofFive(input_string)\n",
" answer = 0\n",
" for i = 1:length(input_string)-4\n",
" product = input_string[i] - '0' # subtract '0' to convert char into int\n",
" for k = 1:4\n",
" product = product * (input_string[i+k] - '0')\n",
" end\n",
" if product > answer\n",
" answer = product\n",
" end\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 318,
"text": [
"GrtstProdofFive (generic function with 1 method)"
]
}
],
"prompt_number": 318
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"GrtstProdofFive(x)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 320,
"text": [
"40824"
]
}
],
"prompt_number": 320
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Special Pythagorean triplet\n",
"
\n",
"Problem 9"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,\n",
"\n",
"\n",
"For example, 32 + 42 = 9 + 16 = 25 = 52.\n",
"\n",
"There exists exactly one Pythagorean triplet for which a + b + c = 1000.\n",
"Find the product abc."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function PythagTriple()\n",
" answer = 0\n",
" for a = 1:1000\n",
" for b = a:1000\n",
" c = sqrt(a^2 + b^2)\n",
" if (a+b+c) == 1000\n",
" answer = a*b*c\n",
" return int(answer)\n",
" end\n",
" end\n",
" end\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 361,
"text": [
"PythagTriple (generic function with 1 method)"
]
}
],
"prompt_number": 361
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PythagTriple()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 362,
"text": [
"31875000"
]
}
],
"prompt_number": 362
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Summation of primes\n",
"
\n",
"Problem 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.\n",
"\n",
"Find the sum of all the primes below two million."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function Prime2(n)\n",
" x = 1\n",
" answer = 2\n",
" while x < n\n",
" if isprime(x)\n",
" answer += x\n",
" end\n",
" x = x + 2\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 381,
"text": [
"Prime2 (generic function with 1 method)"
]
}
],
"prompt_number": 381
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Prime2(2000000)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 384,
"text": [
"142913828922"
]
}
],
"prompt_number": 384
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Largest product in a grid\n",
"
\n",
"Problem 11"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the 20\u00d720 grid below, four numbers along a diagonal line have been marked in red.\n",
"\n",
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
"
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
"
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
"
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
"
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
"
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
"
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
"
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
"
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
"
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
"
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
"
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
"
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
"
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
"
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
"
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
"
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
"
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
"
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
"
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
\n",
"\n",
"The product of these numbers is 26 \u00d7 63 \u00d7 78 \u00d7 14 = 1788696.\n",
"\n",
"What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20\u00d720 grid?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"My2DArray = [[08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48]]\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 84,
"text": [
"20x20 Array{Int64,2}:\n",
" 8 2 22 97 38 15 0 40 0 \u2026 5 7 78 52 12 50 77 91 8\n",
" 49 49 99 40 17 81 18 57 60 40 98 43 69 48 4 56 62 0\n",
" 81 49 31 73 55 79 14 29 93 67 53 88 30 3 49 13 36 65\n",
" 52 70 95 23 4 60 11 42 69 56 1 32 56 71 37 2 36 91\n",
" 22 31 16 71 51 67 63 89 41 54 22 40 40 28 66 33 13 80\n",
" 24 47 32 60 99 3 45 2 44 \u2026 53 78 36 84 20 35 17 12 50\n",
" 32 98 81 28 64 23 67 10 26 67 59 54 70 66 18 38 64 70\n",
" 67 26 20 68 2 62 12 20 95 39 63 8 40 91 66 49 94 21\n",
" 24 55 58 5 66 73 99 26 97 78 96 83 14 88 34 89 63 72\n",
" 21 36 23 9 75 0 76 44 20 14 0 61 33 97 34 31 33 95\n",
" 78 17 53 28 22 75 31 67 15 \u2026 80 4 62 16 14 9 53 56 92\n",
" 16 39 5 42 96 35 31 47 55 24 0 17 54 24 36 29 85 57\n",
" 86 56 0 48 35 71 89 7 5 37 44 60 21 58 51 54 17 58\n",
" 19 80 81 68 5 94 47 69 28 13 86 52 17 77 4 89 55 40\n",
" 4 52 8 83 97 35 99 16 7 32 16 26 26 79 33 27 98 66\n",
" 88 36 68 87 57 62 20 72 3 \u2026 67 46 55 12 32 63 93 53 69\n",
" 4 42 16 73 38 25 39 11 24 18 8 46 29 32 40 62 76 36\n",
" 20 69 36 41 72 30 23 88 34 69 82 67 59 85 74 4 36 16\n",
" 20 73 35 29 78 31 90 1 74 71 48 86 81 16 23 57 5 54\n",
" 1 70 54 71 83 51 54 69 16 48 61 43 52 1 89 19 67 48"
]
}
],
"prompt_number": 84
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function FourProd(array_2d)\n",
" enum = size(array_2d)\n",
" transpose_array = array_2d'\n",
" rotate_array = rotl90(array_2d)\n",
" answer = 0\n",
" for x = 1:enum[1]-4\n",
" for y = 1:enum[2]-4\n",
" product1 = array_2d[x,y]\n",
" product2 = transpose_array[x,y]\n",
" product3 = array_2d[x,y]\n",
" product4 = rotate_array[x,y]\n",
" for z = 1:3\n",
" h = x + z\n",
" v = y + z\n",
" product1 *= array_2d[h,y] # search for up/down product\n",
" product2 *= transpose_array[h,y] # search for left/right product\n",
" product3 *= array_2d[h,v] # search for diagonal \\ product \n",
" product4 *= rotate_array[h,v] # search for diagonal / product\n",
" end\n",
" max_product = max(product1, product2, product3, product4)\n",
" if max_product > answer\n",
" answer = max_product\n",
" end\n",
" end\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 82,
"text": [
"FourProd (generic function with 1 method)"
]
}
],
"prompt_number": 82
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"FourProd(My2DArray)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 85,
"text": [
"70600674"
]
}
],
"prompt_number": 85
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Highly divisible triangular number\n",
"
\n",
"Problem 12"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:\n",
"\n",
"1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
\n",
"\n",
"Let us list the factors of the first seven triangle numbers:\n",
"1: 1\n",
"
3: 1,3\n",
"
6: 1,2,3,6\n",
"
10: 1,2,5,10\n",
"
15: 1,3,5,15\n",
"
21: 1,3,7,21\n",
"
28: 1,2,4,7,14,28\n",
"
\n",
"We can see that 28 is the first triangle number to have over five divisors.\n",
"\n",
"What is the value of the first triangle number to have over five hundred divisors?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function NumDivisors(n)\n",
" answer = 0\n",
" x = floor(sqrt(n))\n",
" for i=1:x\n",
" if n%i == 0\n",
" answer += 2\n",
" end\n",
" end\n",
" if n/x == x\n",
" answer -= 1\n",
" end\n",
" return answer\n",
"end\n",
"\n",
"function TriangleDivisors(n)\n",
" count_div = 0\n",
" counter = 1\n",
" answer = 0\n",
" while count_div < n\n",
" answer += counter\n",
" count_div = NumDivisors(answer)\n",
" counter += 1\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 179,
"text": [
"TriangleDivisors (generic function with 1 method)"
]
}
],
"prompt_number": 179
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"TriangleDivisors(500)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 182,
"text": [
"76576500"
]
}
],
"prompt_number": 182
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Large sum\n",
"
\n",
"Problem 13"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.\n",
"\n",
"37107287533902102798797998220837590246510135740250\n",
"46376937677490009712648124896970078050417018260538\n",
"74324986199524741059474233309513058123726617309629\n",
"91942213363574161572522430563301811072406154908250\n",
"23067588207539346171171980310421047513778063246676\n",
"89261670696623633820136378418383684178734361726757\n",
"28112879812849979408065481931592621691275889832738\n",
"44274228917432520321923589422876796487670272189318\n",
"47451445736001306439091167216856844588711603153276\n",
"70386486105843025439939619828917593665686757934951\n",
"62176457141856560629502157223196586755079324193331\n",
"64906352462741904929101432445813822663347944758178\n",
"92575867718337217661963751590579239728245598838407\n",
"58203565325359399008402633568948830189458628227828\n",
"80181199384826282014278194139940567587151170094390\n",
"35398664372827112653829987240784473053190104293586\n",
"86515506006295864861532075273371959191420517255829\n",
"71693888707715466499115593487603532921714970056938\n",
"54370070576826684624621495650076471787294438377604\n",
"53282654108756828443191190634694037855217779295145\n",
"36123272525000296071075082563815656710885258350721\n",
"45876576172410976447339110607218265236877223636045\n",
"17423706905851860660448207621209813287860733969412\n",
"81142660418086830619328460811191061556940512689692\n",
"51934325451728388641918047049293215058642563049483\n",
"62467221648435076201727918039944693004732956340691\n",
"15732444386908125794514089057706229429197107928209\n",
"55037687525678773091862540744969844508330393682126\n",
"18336384825330154686196124348767681297534375946515\n",
"80386287592878490201521685554828717201219257766954\n",
"78182833757993103614740356856449095527097864797581\n",
"16726320100436897842553539920931837441497806860984\n",
"48403098129077791799088218795327364475675590848030\n",
"87086987551392711854517078544161852424320693150332\n",
"59959406895756536782107074926966537676326235447210\n",
"69793950679652694742597709739166693763042633987085\n",
"41052684708299085211399427365734116182760315001271\n",
"65378607361501080857009149939512557028198746004375\n",
"35829035317434717326932123578154982629742552737307\n",
"94953759765105305946966067683156574377167401875275\n",
"88902802571733229619176668713819931811048770190271\n",
"25267680276078003013678680992525463401061632866526\n",
"36270218540497705585629946580636237993140746255962\n",
"24074486908231174977792365466257246923322810917141\n",
"91430288197103288597806669760892938638285025333403\n",
"34413065578016127815921815005561868836468420090470\n",
"23053081172816430487623791969842487255036638784583\n",
"11487696932154902810424020138335124462181441773470\n",
"63783299490636259666498587618221225225512486764533\n",
"67720186971698544312419572409913959008952310058822\n",
"95548255300263520781532296796249481641953868218774\n",
"76085327132285723110424803456124867697064507995236\n",
"37774242535411291684276865538926205024910326572967\n",
"23701913275725675285653248258265463092207058596522\n",
"29798860272258331913126375147341994889534765745501\n",
"18495701454879288984856827726077713721403798879715\n",
"38298203783031473527721580348144513491373226651381\n",
"34829543829199918180278916522431027392251122869539\n",
"40957953066405232632538044100059654939159879593635\n",
"29746152185502371307642255121183693803580388584903\n",
"41698116222072977186158236678424689157993532961922\n",
"62467957194401269043877107275048102390895523597457\n",
"23189706772547915061505504953922979530901129967519\n",
"86188088225875314529584099251203829009407770775672\n",
"11306739708304724483816533873502340845647058077308\n",
"82959174767140363198008187129011875491310547126581\n",
"97623331044818386269515456334926366572897563400500\n",
"42846280183517070527831839425882145521227251250327\n",
"55121603546981200581762165212827652751691296897789\n",
"32238195734329339946437501907836945765883352399886\n",
"75506164965184775180738168837861091527357929701337\n",
"62177842752192623401942399639168044983993173312731\n",
"32924185707147349566916674687634660915035914677504\n",
"99518671430235219628894890102423325116913619626622\n",
"73267460800591547471830798392868535206946944540724\n",
"76841822524674417161514036427982273348055556214818\n",
"97142617910342598647204516893989422179826088076852\n",
"87783646182799346313767754307809363333018982642090\n",
"10848802521674670883215120185883543223812876952786\n",
"71329612474782464538636993009049310363619763878039\n",
"62184073572399794223406235393808339651327408011116\n",
"66627891981488087797941876876144230030984490851411\n",
"60661826293682836764744779239180335110989069790714\n",
"85786944089552990653640447425576083659976645795096\n",
"66024396409905389607120198219976047599490197230297\n",
"64913982680032973156037120041377903785566085089252\n",
"16730939319872750275468906903707539413042652315011\n",
"94809377245048795150954100921645863754710598436791\n",
"78639167021187492431995700641917969777599028300699\n",
"15368713711936614952811305876380278410754449733078\n",
"40789923115535562561142322423255033685442488917353\n",
"44889911501440648020369068063960672322193204149535\n",
"41503128880339536053299340368006977710650566631954\n",
"81234880673210146739058568557934581403627822703280\n",
"82616570773948327592232845941706525094512325230608\n",
"22918802058777319719839450180888072429661980811197\n",
"77158542502016545090413245809786882778948721859617\n",
"72107838435069186155435662884062257473692284509516\n",
"20849603980134001723930671666823555245252804609722\n",
"53503534226472524250874054075591789781264330331690\n",
""
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"LargeNumString = \"37107287533902102798797998220837590246510135740250\n",
"46376937677490009712648124896970078050417018260538\n",
"74324986199524741059474233309513058123726617309629\n",
"91942213363574161572522430563301811072406154908250\n",
"23067588207539346171171980310421047513778063246676\n",
"89261670696623633820136378418383684178734361726757\n",
"28112879812849979408065481931592621691275889832738\n",
"44274228917432520321923589422876796487670272189318\n",
"47451445736001306439091167216856844588711603153276\n",
"70386486105843025439939619828917593665686757934951\n",
"62176457141856560629502157223196586755079324193331\n",
"64906352462741904929101432445813822663347944758178\n",
"92575867718337217661963751590579239728245598838407\n",
"58203565325359399008402633568948830189458628227828\n",
"80181199384826282014278194139940567587151170094390\n",
"35398664372827112653829987240784473053190104293586\n",
"86515506006295864861532075273371959191420517255829\n",
"71693888707715466499115593487603532921714970056938\n",
"54370070576826684624621495650076471787294438377604\n",
"53282654108756828443191190634694037855217779295145\n",
"36123272525000296071075082563815656710885258350721\n",
"45876576172410976447339110607218265236877223636045\n",
"17423706905851860660448207621209813287860733969412\n",
"81142660418086830619328460811191061556940512689692\n",
"51934325451728388641918047049293215058642563049483\n",
"62467221648435076201727918039944693004732956340691\n",
"15732444386908125794514089057706229429197107928209\n",
"55037687525678773091862540744969844508330393682126\n",
"18336384825330154686196124348767681297534375946515\n",
"80386287592878490201521685554828717201219257766954\n",
"78182833757993103614740356856449095527097864797581\n",
"16726320100436897842553539920931837441497806860984\n",
"48403098129077791799088218795327364475675590848030\n",
"87086987551392711854517078544161852424320693150332\n",
"59959406895756536782107074926966537676326235447210\n",
"69793950679652694742597709739166693763042633987085\n",
"41052684708299085211399427365734116182760315001271\n",
"65378607361501080857009149939512557028198746004375\n",
"35829035317434717326932123578154982629742552737307\n",
"94953759765105305946966067683156574377167401875275\n",
"88902802571733229619176668713819931811048770190271\n",
"25267680276078003013678680992525463401061632866526\n",
"36270218540497705585629946580636237993140746255962\n",
"24074486908231174977792365466257246923322810917141\n",
"91430288197103288597806669760892938638285025333403\n",
"34413065578016127815921815005561868836468420090470\n",
"23053081172816430487623791969842487255036638784583\n",
"11487696932154902810424020138335124462181441773470\n",
"63783299490636259666498587618221225225512486764533\n",
"67720186971698544312419572409913959008952310058822\n",
"95548255300263520781532296796249481641953868218774\n",
"76085327132285723110424803456124867697064507995236\n",
"37774242535411291684276865538926205024910326572967\n",
"23701913275725675285653248258265463092207058596522\n",
"29798860272258331913126375147341994889534765745501\n",
"18495701454879288984856827726077713721403798879715\n",
"38298203783031473527721580348144513491373226651381\n",
"34829543829199918180278916522431027392251122869539\n",
"40957953066405232632538044100059654939159879593635\n",
"29746152185502371307642255121183693803580388584903\n",
"41698116222072977186158236678424689157993532961922\n",
"62467957194401269043877107275048102390895523597457\n",
"23189706772547915061505504953922979530901129967519\n",
"86188088225875314529584099251203829009407770775672\n",
"11306739708304724483816533873502340845647058077308\n",
"82959174767140363198008187129011875491310547126581\n",
"97623331044818386269515456334926366572897563400500\n",
"42846280183517070527831839425882145521227251250327\n",
"55121603546981200581762165212827652751691296897789\n",
"32238195734329339946437501907836945765883352399886\n",
"75506164965184775180738168837861091527357929701337\n",
"62177842752192623401942399639168044983993173312731\n",
"32924185707147349566916674687634660915035914677504\n",
"99518671430235219628894890102423325116913619626622\n",
"73267460800591547471830798392868535206946944540724\n",
"76841822524674417161514036427982273348055556214818\n",
"97142617910342598647204516893989422179826088076852\n",
"87783646182799346313767754307809363333018982642090\n",
"10848802521674670883215120185883543223812876952786\n",
"71329612474782464538636993009049310363619763878039\n",
"62184073572399794223406235393808339651327408011116\n",
"66627891981488087797941876876144230030984490851411\n",
"60661826293682836764744779239180335110989069790714\n",
"85786944089552990653640447425576083659976645795096\n",
"66024396409905389607120198219976047599490197230297\n",
"64913982680032973156037120041377903785566085089252\n",
"16730939319872750275468906903707539413042652315011\n",
"94809377245048795150954100921645863754710598436791\n",
"78639167021187492431995700641917969777599028300699\n",
"15368713711936614952811305876380278410754449733078\n",
"40789923115535562561142322423255033685442488917353\n",
"44889911501440648020369068063960672322193204149535\n",
"41503128880339536053299340368006977710650566631954\n",
"81234880673210146739058568557934581403627822703280\n",
"82616570773948327592232845941706525094512325230608\n",
"22918802058777319719839450180888072429661980811197\n",
"77158542502016545090413245809786882778948721859617\n",
"72107838435069186155435662884062257473692284509516\n",
"20849603980134001723930671666823555245252804609722\n",
"53503534226472524250874054075591789781264330331690\""
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 243,
"text": [
"\"37107287533902102798797998220837590246510135740250\\n46376937677490009712648124896970078050417018260538\\n74324986199524741059474233309513058123726617309629\\n91942213363574161572522430563301811072406154908250\\n23067588207539346171171980310421047513778063246676\\n89261670696623633820136378418383684178734361726757\\n28112879812849979408065481931592621691275889832738\\n44274228917432520321923589422876796487670272189318\\n47451445736001306439091167216856844588711603153276\\n70386486105843025439939619828917593665686757934951\\n62176457141856560629502157223196586755079324193331\\n64906352462741904929101432445813822663347944758178\\n92575867718337217661963751590579239728245598838407\\n58203565325359399008402633568948830189458628227828\\n80181199384826282014278194139940567587151170094390\\n35398664372827112653829987240784473053190104293586\\n86515506006295864861532075273371959191420517255829\\n71693888707715466499115593487603532921714970056938\\n54370070576826684624621495650076471787294438377604\\n53282654108756828443191190634694037855217779295145\\n36123272525000296071075082563815656710885258350721\\n45876576172410976447339110607218265236877223636045\\n17423706905851860660448207621209813287860733969412\\n81142660418086830619328460811191061556940512689692\\n51934325451728388641918047049293215058642563049483\\n62467221648435076201727918039944693004732956340691\\n15732444386908125794514089057706229429197107928209\\n55037687525678773091862540744969844508330393682126\\n18336384825330154686196124348767681297534375946515\\n80386287592878490201521685554828717201219257766954\\n78182833757993103614740356856449095527097864797581\\n16726320100436897842553539920931837441497806860984\\n48403098129077791799088218795327364475675590848030\\n87086987551392711854517078544161852424320693150332\\n59959406895756536782107074926966537676326235447210\\n69793950679652694742597709739166693763042633987085\\n41052684708299085211399427365734116182760315001271\\n65378607361501080857009149939512557028198746004375\\n35829035317434717326932123578154982629742552737307\\n94953759765105305946966067683156574377167401875275\\n88902802571733229619176668713819931811048770190271\\n25267680276078003013678680992525463401061632866526\\n36270218540497705585629946580636237993140746255962\\n24074486908231174977792365466257246923322810917141\\n91430288197103288597806669760892938638285025333403\\n34413065578016127815921815005561868836468420090470\\n23053081172816430487623791969842487255036638784583\\n11487696932154902810424020138335124462181441773470\\n63783299490636259666498587618221225225512486764533\\n67720186971698544312419572409913959008952310058822\\n95548255300263520781532296796249481641953868218774\\n76085327132285723110424803456124867697064507995236\\n37774242535411291684276865538926205024910326572967\\n23701913275725675285653248258265463092207058596522\\n29798860272258331913126375147341994889534765745501\\n18495701454879288984856827726077713721403798879715\\n38298203783031473527721580348144513491373226651381\\n34829543829199918180278916522431027392251122869539\\n40957953066405232632538044100059654939159879593635\\n29746152185502371307642255121183693803580388584903\\n41698116222072977186158236678424689157993532961922\\n62467957194401269043877107275048102390895523597457\\n23189706772547915061505504953922979530901129967519\\n86188088225875314529584099251203829009407770775672\\n11306739708304724483816533873502340845647058077308\\n82959174767140363198008187129011875491310547126581\\n97623331044818386269515456334926366572897563400500\\n42846280183517070527831839425882145521227251250327\\n55121603546981200581762165212827652751691296897789\\n32238195734329339946437501907836945765883352399886\\n75506164965184775180738168837861091527357929701337\\n62177842752192623401942399639168044983993173312731\\n32924185707147349566916674687634660915035914677504\\n99518671430235219628894890102423325116913619626622\\n73267460800591547471830798392868535206946944540724\\n76841822524674417161514036427982273348055556214818\\n97142617910342598647204516893989422179826088076852\\n87783646182799346313767754307809363333018982642090\\n10848802521674670883215120185883543223812876952786\\n71329612474782464538636993009049310363619763878039\\n62184073572399794223406235393808339651327408011116\\n66627891981488087797941876876144230030984490851411\\n60661826293682836764744779239180335110989069790714\\n85786944089552990653640447425576083659976645795096\\n66024396409905389607120198219976047599490197230297\\n64913982680032973156037120041377903785566085089252\\n16730939319872750275468906903707539413042652315011\\n94809377245048795150954100921645863754710598436791\\n78639167021187492431995700641917969777599028300699\\n15368713711936614952811305876380278410754449733078\\n40789923115535562561142322423255033685442488917353\\n44889911501440648020369068063960672322193204149535\\n41503128880339536053299340368006977710650566631954\\n81234880673210146739058568557934581403627822703280\\n82616570773948327592232845941706525094512325230608\\n22918802058777319719839450180888072429661980811197\\n77158542502016545090413245809786882778948721859617\\n72107838435069186155435662884062257473692284509516\\n20849603980134001723930671666823555245252804609722\\n53503534226472524250874054075591789781264330331690\""
]
}
],
"prompt_number": 243
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"num_array = split(LargeNumString, \"\\n\")\n",
"A = [ float(num_array[i]) for i=1:length(num_array) ]\n",
"answer = sum(A)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 245,
"text": [
"5.537376230390877e51"
]
}
],
"prompt_number": 245
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Longest Collatz sequence\n",
"
\n",
"Problem 14"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following iterative sequence is defined for the set of positive integers:\n",
"\n",
"n \u2192 n/2 (n is even)
\n",
"n \u2192 3n + 1 (n is odd)\n",
"\n",
"Using the rule above and starting with 13, we generate the following sequence:\n",
"\n",
"13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1
\n",
"It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.\n",
"\n",
"Which starting number, under one million, produces the longest chain?\n",
"\n",
"NOTE: Once the chain starts the terms are allowed to go above one million."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function CollatzSeq(n)\n",
" A = [n]\n",
" while n > 1\n",
" n = iseven(n)? int(n/2) : 3*n + 1\n",
" push!(A, n)\n",
" end\n",
" return A\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 28,
"text": [
"CollatzSeq (generic function with 1 method)"
]
}
],
"prompt_number": 28
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"\n",
"answer = []\n",
"seq = []\n",
"\n",
"for i = 700000:1000000\n",
" seq = CollatzSeq(i)\n",
" length(seq) >= length(answer)? answer = seq : pass\n",
"end\n",
"\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer[1]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 6"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
".568037033081055"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 29,
"text": [
"837799"
]
}
],
"prompt_number": 29
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"\n",
"seqs = map((x) -> length(CollatzSeq(x)), 700000:1000000)\n",
"\n",
"print(\"runtime: \",time() - begin_time)\n",
"return 700000+indmax(seqs)-1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 3"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
".7657041549682617"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 30,
"text": [
"837799"
]
}
],
"prompt_number": 30
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Lattice paths\n",
"
\n",
"Problem 15"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Starting in the top left corner of a 2\u00d72 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.\n",
"\n",
"How many such routes are there through a 20\u00d720 grid?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function LatticeRecursive(x, y)\n",
" if x == 1.0 && y == 1.0\n",
" return 2.0\n",
" elseif x == 1.0\n",
" return 1.0 + LatticeRecursive(x, y-1.0)\n",
" elseif y == 1.0\n",
" return 1.0 + LatticeRecursive(x-1.0, y)\n",
" else\n",
" return LatticeRecursive(x-1.0, y) + LatticeRecursive(x, y-1.0)\n",
" end\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 231,
"text": [
"LatticeRecursive (generic function with 1 method)"
]
}
],
"prompt_number": 231
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function Lattice(x, y)\n",
" answer = zeros(x+1, y+1)\n",
" for i = 1:y+1\n",
" for j = 1:x+1\n",
" if i == 1.0 || j == 1.0\n",
" answer[i, j] = 1.0\n",
" else\n",
" answer[i, j] = answer[i-1, j] + answer[i, j-1]\n",
" end\n",
" end\n",
" end\n",
" return answer[x+1, y+1]\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 222,
"text": [
"Lattice (generic function with 1 method)"
]
}
],
"prompt_number": 222
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"big(int((Lattice(20,20))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 246,
"text": [
"137846528820"
]
}
],
"prompt_number": 246
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Power digit sum\n",
"
\n",
"Problem 16"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.\n",
"\n",
"What is the sum of the digits of the number 21000?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function PowerDigit(x)\n",
" n = string(big(2)^x)\n",
" answer = 0\n",
" for i= 1:length(n)\n",
" answer += int(n[i] - '0') # subtract '0' to convert char into int\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"PowerDigit (generic function with 1 method)"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PowerDigit(1000)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"1366"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Number letter counts\n",
"
\n",
"Problem 17"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.\n",
"\n",
"If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?\n",
"\n",
"\n",
"NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of \"and\" when writing out numbers is in compliance with British usage."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function LetterCounts(n)\n",
" l = {\n",
" 1 => \"one\",\n",
" 2 => \"two\",\n",
" 3 => \"three\",\n",
" 4 => \"four\",\n",
" 5 => \"five\",\n",
" 6 => \"six\",\n",
" 7 => \"seven\",\n",
" 8 => \"eight\",\n",
" 9 => \"nine\",\n",
" 10 => \"ten\",\n",
" 11 => \"eleven\",\n",
" 12 => \"twelve\",\n",
" 13 => \"thirteen\",\n",
" 14 => \"fourteen\",\n",
" 15 => \"fifteen\",\n",
" 16 => \"sixteen\",\n",
" 17 => \"seventeen\",\n",
" 18 => \"eighteen\",\n",
" 19 => \"nineteen\",\n",
" 20 => \"twenty\",\n",
" 30 => \"thirty\",\n",
" 40 => \"forty\",\n",
" 50 => \"fifty\",\n",
" 60 => \"sixty\",\n",
" 70 => \"seventy\",\n",
" 80 => \"eighty\",\n",
" 90 => \"ninety\",\n",
" 1000 => \"onethousand\"\n",
" }\n",
" \n",
"# adds:\n",
"# 100, 200, 300...\n",
"# 101, 102, 103...\n",
"# 201, 202, 203...\n",
"# 110, 120, 130...\n",
" for h=1:9\n",
" l[(h*100)] = l[h] * \"hundred\"\n",
" for ones=1:9\n",
" l[(h*100) + ones] = l[h*100] * \"and\" * l[ones]\n",
" l[(h*100) + (ones*10)] = l[h*100] * \"and\" * l[ones*10]\n",
" end\n",
" end\n",
"\n",
"# adds:\n",
"# 21, 22, 23...\n",
"# 31, 32, 33...\n",
"# 111, 112, 113...\n",
"# 121, 122, 123...\n",
"# 231, 232, 233...\n",
" for ones=1:9\n",
" for tens=2:9\n",
" l[(tens*10) + ones] = l[tens*10] * l[ones]\n",
" for h=1:9\n",
" l[(h*100) + (tens*10) + ones] = l[h*100] * \"and\" * l[tens*10] * l[ones]\n",
" l[(h*100) + (10) + ones] = l[h*100] * \"and\" * l[10 + ones]\n",
" end\n",
" end\n",
" end\n",
" return length(l[n])\n",
"end\n",
"\n",
"answer = 0\n",
"\n",
"for x=1:1000\n",
" answer += LetterCounts(x)\n",
"end\n",
"\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 96,
"text": [
"21124"
]
}
],
"prompt_number": 96
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Maximum path sum I\n",
"
\n",
"Problem 18"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.\n",
"\n",
" 3 \n",
" 7 4 \n",
" 2 4 6 \n",
" 8 5 9 3 \n",
"\n",
"That is, 3 + 7 + 4 + 9 = 23.\n",
"\n",
"Find the maximum total from top to bottom of the triangle below:\n",
"\n",
" 75\n",
" 95 64\n",
" 17 47 82\n",
" 18 35 87 10\n",
" 20 04 82 47 65\n",
" 19 01 23 75 03 34\n",
" 88 02 77 73 07 63 67\n",
" 99 65 04 28 06 16 70 92\n",
" 41 41 26 56 83 40 80 70 33\n",
" 41 48 72 33 47 32 37 16 94 29\n",
" 53 71 44 65 25 43 91 52 97 51 14\n",
" 70 11 33 28 77 73 17 78 39 68 17 57\n",
" 91 71 52 38 17 14 91 43 58 50 27 29 48\n",
" 63 66 04 68 89 53 67 30 73 16 69 87 40 31\n",
" 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\n",
"\n",
"NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function MakeTriangle()\n",
" triangle = zeros(Int64, 15, 15)\n",
" triangle[1,1] = 75\n",
" triangle[2,1:2] = [95 64]\n",
" triangle[3,1:3] = [17 47 82]\n",
" triangle[4,1:4] = [18 35 87 10]\n",
" triangle[5,1:5] = [20 04 82 47 65]\n",
" triangle[6,1:6] = [19 01 23 75 03 34]\n",
" triangle[7,1:7] = [88 02 77 73 07 63 67]\n",
" triangle[8,1:8] = [99 65 04 28 06 16 70 92]\n",
" triangle[9,1:9] = [41 41 26 56 83 40 80 70 33]\n",
" triangle[10,1:10] = [41 48 72 33 47 32 37 16 94 29]\n",
" triangle[11,1:11] = [53 71 44 65 25 43 91 52 97 51 14]\n",
" triangle[12,1:12] = [70 11 33 28 77 73 17 78 39 68 17 57]\n",
" triangle[13,1:13] = [91 71 52 38 17 14 91 43 58 50 27 29 48]\n",
" triangle[14,1:14] = [63 66 04 68 89 53 67 30 73 16 69 87 40 31]\n",
" triangle[15,1:15] = [04 62 98 27 23 09 70 98 73 93 38 53 60 04 23]\n",
" return triangle\n",
"end\n",
"\n",
"function MaxPathSum(triangle)\n",
" sums = zeros(Int64, size(triangle))\n",
" sums[1,1] = triangle[1,1]\n",
" rows, cols = size(triangle)\n",
" for row = 2:rows\n",
" for col = 1:row\n",
" val = triangle[row,col]\n",
" if col == 1\n",
" sums[row,col] = val + sums[row-1,col]\n",
" else\n",
" sums[row,col] = val + max(sums[row-1,col], sums[row-1,col-1])\n",
" end\n",
" end \n",
" end \n",
" return maximum(sums[end,1:end])\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 247,
"text": [
"MaxPathSum (generic function with 2 methods)"
]
}
],
"prompt_number": 247
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MaxPathSum(MakeTriangle())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 248,
"text": [
"1074"
]
}
],
"prompt_number": 248
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Maximum path sum II\n",
"
\n",
"Problem 67"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.\n",
"\n",
" 3\n",
" 7 4\n",
" 2 4 6\n",
" 8 5 9 3\n",
"\n",
"That is, 3 + 7 + 4 + 9 = 23.\n",
"\n",
"Find the maximum total from top to bottom in triangle.txt, a 15K text file containing a triangle with one-hundred rows.\n",
"\n",
"NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function MakeBigTriangle()\n",
" big_triangle = open(\"triangle.txt\")\n",
" lines = readlines(big_triangle)\n",
" rows = length(lines)\n",
" triangle = zeros(Int64, rows, rows)\n",
" for x=1:rows\n",
" triangle[x,1:x] = [int(split(lines[x], ' '))]\n",
" end\n",
" return triangle\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 385,
"text": [
"MakeBigTriangle (generic function with 1 method)"
]
}
],
"prompt_number": 385
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MaxPathSum(MakeBigTriangle())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 386,
"text": [
"7273"
]
}
],
"prompt_number": 386
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Counting Sundays\n",
"
\n",
"Problem 19"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You are given the following information, but you may prefer to do some research for yourself.\n",
"\n",
"1 Jan 1900 was a Monday.\n",
"\n",
"* Thirty days has September,\n",
"- April, June and November.\n",
"- All the rest have thirty-one,\n",
"- Saving February alone,\n",
"- Which has twenty-eight, rain or shine.\n",
"- And on leap years, twenty-nine.\n",
"\n",
"A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.\n",
"How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"first_sundays = 0\n",
"months = [\n",
" 31, #jan \n",
" 28, #feb\n",
" 31, #mar\n",
" 30, #apr\n",
" 31, #may \n",
" 30, #jun\n",
" 31, #jul\n",
" 31, #aug\n",
" 30, #sep\n",
" 31, #oct\n",
" 30, #nov\n",
" 31 #dec\n",
" ]\n",
" day = 3 # jan 1, 1901 is a tue (3)\n",
" m = 1 # m = month in year\n",
"for m_range = 1:1200 # m_range = total months elapsed\n",
" yr = floor((m_range - 1) / 12) + 1901\n",
" if day == 1 \n",
"# print(\"$m/$yr: $day\\n\")\n",
" first_sundays += 1\n",
" end \n",
" if (m == 2) && (yr % 4 == 0) && ((yr % 100 != 0) || (yr % 400 == 0))\n",
" day += 1 # leap year\n",
" end\n",
" drift = months[m] - 28\n",
" day = ((day + drift) % 7 == 0) ? 7 : (day + drift) % 7\n",
" m = (m_range % 12 == 0) ? 1 : m + 1\n",
"end\n",
"return first_sundays"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 44,
"text": [
"171"
]
}
],
"prompt_number": 44
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Factorial digit sum\n",
"
\n",
"Problem 20"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"n! means n \u00d7 (n \u2212 1) \u00d7 ... \u00d7 3 \u00d7 2 \u00d7 1\n",
"\n",
"For example, 10! = 10 \u00d7 9 \u00d7 ... \u00d7 3 \u00d7 2 \u00d7 1 = 3628800,\n",
"and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.\n",
"\n",
"Find the sum of the digits in the number 100!"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"sum(digits(factorial(big(100)))) # digits does not work on BigInt"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "LoadError",
"evalue": "no method convert(Type{Unsigned},BigInt)\nat In[45]:1",
"output_type": "pyerr",
"traceback": [
"no method convert(Type{Unsigned},BigInt)\nat In[45]:1",
" in digits at intfuncs.jl:289",
" in digits at intfuncs.jl:288"
]
}
],
"prompt_number": 45
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function FactDigitSum(n)\n",
" fact = string(reduce(*, 1:big(n)))\n",
" answer = 0\n",
" for i= 1:length(fact)\n",
" answer += int(fact[i] - '0') # subtract '0' to convert char into int\n",
" end\n",
" return answer\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 48,
"text": [
"FactDigitSum (generic function with 1 method)"
]
}
],
"prompt_number": 48
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"FactDigitSum(100)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 49,
"text": [
"648"
]
}
],
"prompt_number": 49
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Amicable numbers\n",
"
\n",
"Problem 21"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).\n",
"If d(a) = b and d(b) = a, where a \u2260 b, then a and b are an amicable pair and each of a and b are called amicable numbers.\n",
"\n",
"For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.\n",
"\n",
"Evaluate the sum of all the amicable numbers under 10000."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function ProperDivisor(n)\n",
" divisors = [1]\n",
" n_sqrt = floor(sqrt(n))\n",
" for i = 2:n_sqrt\n",
" if n % i == 0\n",
" if n/i == i\n",
" push!(divisors, i)\n",
" else\n",
" push!(divisors, i)\n",
" push!(divisors, n/i)\n",
" end\n",
" end\n",
" end\n",
" return divisors\n",
"end\n",
"\n",
"function Amicable(n)\n",
" sum1 = sum(ProperDivisor(n))\n",
" sum2 = sum(ProperDivisor(sum1))\n",
" return sum2 == n && sum1 != sum2\n",
"end\n",
"\n",
"amicables = Int64[]\n",
"for num = 2:10000\n",
" if Amicable(num)\n",
" print(num, \" \")\n",
" push!(amicables, num)\n",
" end\n",
"end\n",
"\n",
"return sum(amicables)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"220 "
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"284 1184 1210 2620 2924 5020 5564 6232 6368 "
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 27,
"text": [
"31626"
]
}
],
"prompt_number": 27
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Names scores\n",
"
\n",
"Problem 22"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.\n",
"\n",
"For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 \u00d7 53 = 49714.\n",
"\n",
"What is the total of all the name scores in the file?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"alpha_score = Dict{Char,Int64}()\n",
"for character = 1:26\n",
" alpha_score[(char(character + 64))] = character\n",
"end\n",
"\n",
"name_list = open(readall, \"names.txt\")\n",
"names = sort(split(replace(name_list, '\"',\"\"), \",\"))\n",
"\n",
"score = 0\n",
"for name = 1:length(names)\n",
" name_score = 0\n",
" for letter = 1:length(names[name])\n",
" name_score += alpha_score[names[name][letter]]\n",
" end\n",
" name_score *= name\n",
" score += name_score\n",
"end\n",
"\n",
"return score"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 26,
"text": [
"871198282"
]
}
],
"prompt_number": 26
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Non-abundant sums\n",
"
\n",
"Problem 23"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.\n",
"\n",
"A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.\n",
"\n",
"As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.\n",
"\n",
"Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"\n",
"abundant_nums = [12]\n",
"for n = 13:20161\n",
" if sum(ProperDivisor(n)) > n\n",
" push!(abundant_nums, n)\n",
" end\n",
"end\n",
"\n",
"answer = [1:23]\n",
"for i = 24:20161\n",
" found = false\n",
" for num in abundant_nums\n",
" if (i - num) in abundant_nums\n",
" found = true\n",
" break\n",
" end\n",
" end\n",
" if found == false\n",
" answer = push!(answer, i)\n",
" end\n",
"end\n",
"\n",
"print(\"runtime: \", time() - begin_time)\n",
"return sum(answer)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 129"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
".338219165802"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 32,
"text": [
"4179871"
]
}
],
"prompt_number": 32
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# scratchpad\n",
"ab_num_sums = Array(Int64, 1)\n",
"for num in abundant_nums\n",
" sums_array = pmap((x) -> x+num, abundant_nums)\n",
" ab_num_sums = cat(1, ab_num_sums, sums_array)\n",
"end\n",
"\n",
"answer = [1]\n",
"for i = 2:28123\n",
" answer = sum(push!(i in ab_num_sums? i : pass))\n",
"end\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "LoadError",
"evalue": "abundant_nums not defined\nat In[31]:6",
"output_type": "pyerr",
"traceback": [
"abundant_nums not defined\nat In[31]:6",
" in anonymous at no file"
]
}
],
"prompt_number": 31
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Lexicographic permutations\n",
"
\n",
"Problem 24"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:\n",
"\n",
"\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",
"collapsed": false,
"input": [
"sum(map(x -> 10^(x[1]-1) * x[2], enumerate(nthperm([0:9], 1000000))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 41,
"text": [
"645193872"
]
}
],
"prompt_number": 41
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"1000-digit Fibonacci number\n",
"
\n",
"Problem 25"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Fibonacci sequence is defined by the recurrence relation:\n",
"\n",
"Fn = Fn\u22121 + Fn\u22122, where F1 = 1 and F2 = 1.
\n",
"Hence the first 12 terms will be:\n",
"
F1 = 1\n",
"
F2 = 1\n",
"
F3 = 2\n",
"
F4 = 3\n",
"
F5 = 5\n",
"
F6 = 8\n",
"
F7 = 13\n",
"
F8 = 21\n",
"
F9 = 34\n",
"
F10 = 55\n",
"
F11 = 89\n",
"
F12 = 144\n",
"\n",
"The 12th term, F12, is the first term to contain three digits.\n",
"\n",
"What is the first term in the Fibonacci sequence to contain 1000 digits?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function Fib_num_digits(n)\n",
" fib_seq = [\"1\",\"1\"]\n",
" while length(fib_seq[end]) < n\n",
" push!(fib_seq, string(BigInt(fib_seq[end-1]) + BigInt(fib_seq[end])))\n",
"# print(fib_seq[end], \" \")\n",
" end\n",
" return length(fib_seq)\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
"Fib_num_digits (generic function with 1 method)"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = Fib_num_digits(1000)\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 0."
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"20959210395812988"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 17,
"text": [
"4782"
]
}
],
"prompt_number": 17
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Reciprocal cycles\n",
"
\n",
"Problem 26"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:\n",
"\n",
" 1/2\t= \t0.5\n",
" 1/3\t= \t0.(3)\n",
" 1/4\t= \t0.25\n",
" 1/5\t= \t0.2\n",
" 1/6\t= \t0.1(6)\n",
" 1/7\t= \t0.(142857)\n",
" 1/8\t= \t0.125\n",
" 1/9\t= \t0.(1)\n",
" 1/10\t= \t0.1\n",
"\n",
"Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.\n",
"\n",
"Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function ReciprocalCycles(n) \n",
" seq_len = 0\n",
" answer = 0\n",
"\n",
" for i = 2:n\n",
" remainders = zeros(Int64,i)\n",
" value = 1\n",
" len = 0\n",
" \n",
" while value < i\n",
" value *= 10\n",
" end\n",
" while value != 0\n",
" if value in remainders\n",
" break\n",
" end\n",
" push!(remainders, value)\n",
" while (value < i)\n",
" value *= 10\n",
" len += 1\n",
" end\n",
" value %= i\n",
" end\n",
" if value != 0 && len > seq_len\n",
" seq_len = len\n",
" answer = i\n",
" end\n",
" end\n",
" return answer, seq_len\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"ReciprocalCycles (generic function with 1 method)"
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = ReciprocalCycles(1000)\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 0."
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"3948509693145752"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 16,
"text": [
"(983,982)"
]
}
],
"prompt_number": 16
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Quadratic primes\n",
"
\n",
"Problem 27"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Euler discovered the remarkable quadratic formula:\n",
"\n",
"n\u00b2 + n + 41\n",
"\n",
"It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41\u00b2 + 41 + 41 is clearly divisible by 41.\n",
"\n",
"The incredible formula n\u00b2 \u2212 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, \u221279 and 1601, is \u2212126479.\n",
"\n",
"Considering quadratics of the form:\n",
"\n",
"n\u00b2 + an + b, where |a| < 1000 and |b| < 1000\n",
"\n",
"where |n| is the modulus/absolute value of n\n",
"e.g. |11| = 11 and |\u22124| = 4\n",
"Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function QuadraticPrimes()\n",
" max_len = 0\n",
" best_a = 0\n",
" best_b = 0\n",
" for a = -999:999\n",
" for b = -999:999\n",
" if isprime(b)\n",
" n = 0\n",
" while isprime(abs((n^2) + (a*n) + b))\n",
" n += 1\n",
" end\n",
" if n > max_len\n",
" max_len = n\n",
" best_a = a\n",
" best_b = b\n",
" end\n",
" end\n",
" end\n",
" end\n",
" return best_a * best_b\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 83,
"text": [
"QuadraticPrimes (generic function with 1 method)"
]
}
],
"prompt_number": 83
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = QuadraticPrimes()\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 6"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
".396510124206543"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 84,
"text": [
"-59231"
]
}
],
"prompt_number": 84
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Number spiral diagonals\n",
"
\n",
"Problem 28"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:\n",
"\n",
" 21 22 23 24 25\n",
" 20 7 8 9 10\n",
" 19 6 1 2 11\n",
" 18 5 4 3 12\n",
" 17 16 15 14 13\n",
"\n",
"It can be verified that the sum of the numbers on the diagonals is 101.\n",
"\n",
"What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function NumSpiralDiag(n)\n",
" i = 1\n",
" result = 1\n",
" while i < n\n",
" i += 2\n",
" result = result + (i^2 * 4) - ((i-1) * 6)\n",
" end\n",
" return result\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 19,
"text": [
"NumSpiralDiag (generic function with 2 methods)"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = NumSpiralDiag(1001)\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 0."
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"005847930908203125"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 20,
"text": [
"669171001"
]
}
],
"prompt_number": 20
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Consecutive prime sum\n",
"
\n",
"Problem 50"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The prime 41, can be written as the sum of six consecutive primes:\n",
"\n",
" 41 = 2 + 3 + 5 + 7 + 11 + 13\n",
"This is the longest sum of consecutive primes that adds to a prime below one-hundred.\n",
"\n",
"The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.\n",
"\n",
"Which prime, below one-million, can be written as the sum of the most consecutive primes?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function GeneratePrimes(n)\n",
" primes = Int[]\n",
" for i = 1:n\n",
" if isprime(i)\n",
" push!(primes, i)\n",
" end\n",
" end\n",
" return primes\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 4,
"text": [
"GeneratePrimes (generic function with 1 method)"
]
}
],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function ConsecutivePrimes(n)\n",
" primes_list = GeneratePrimes(n/250)\n",
" l = length(primes_list)\n",
" count = 0\n",
" prime = 0\n",
" count_result = 0\n",
" prime_result = 0\n",
" for i = 1:l\n",
" for j = 1:l\n",
" x = l-j\n",
" count = x-i\n",
" if count > count_result \n",
" num = sum({primes_list[y] for y=i:x})\n",
" if num < n\n",
" if isprime(num)\n",
" count_result = count\n",
" prime_result = num\n",
" print(\"Result: $prime_result, $count_result\\n\")\n",
" end\n",
" end\n",
" end\n",
" end\n",
" end\n",
" return prime_result, count_result\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
"ConsecutivePrimes (generic function with 1 method)"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = ConsecutivePrimes(1000000)\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Result: 958577, 535\n",
"Result: 978037, 538\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Result: 997651, 542\n",
"runtime: 0.0333561897277832"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 14,
"text": [
"(997651,542)"
]
}
],
"prompt_number": 14
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Distinct powers\n",
"
\n",
"Problem 29"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider all integer combinations of ab for 2 \u2264 a \u2264 5 and 2 \u2264 b \u2264 5:\n",
"\n",
"22=4, \n",
"23=8, \n",
"24=16, \n",
"25=32
\n",
"32=9, \n",
"33=27, \n",
"34=81, \n",
"35=243
\n",
"42=16, \n",
"43=64, \n",
"44=256, \n",
"45=1024
\n",
"52=25, \n",
"53=125, \n",
"54=625, \n",
"55=3125\n",
"\n",
"If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:\n",
"\n",
"4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125\n",
"\n",
"How many distinct terms are in the sequence generated by ab for 2 \u2264 a \u2264 100 and 2 \u2264 b \u2264 100?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"function DistinctPowers(a, b)\n",
" matrix = zeros(BigFloat, a, b)\n",
" matrix = [ BigFloat(row)^col for row=2:a, col=2:b ]\n",
" return length(unique(matrix))\n",
"end"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"DistinctPowers (generic function with 1 method)"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"begin_time = time()\n",
"answer = DistinctPowers(100, 100)\n",
"print(\"runtime: \", time() - begin_time)\n",
"return answer"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"runtime: 0."
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"6840958595275879"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"9183"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 59
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 60
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}