{
"metadata": {
"name": "",
"signature": "sha256:9b3bf3613a6db426648987f92f283b140832ff4e669568dea20da6919d034906"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 1\n",
"sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"233168"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 2\n",
"def fib_seq():\n",
" a, b = 0, 1\n",
" while True:\n",
" n = a + b\n",
" yield n\n",
" a, b = b, n\n",
"def even(seq):\n",
" for n in seq:\n",
" if n % 2 == 0:\n",
" yield n\n",
"def less_or_eq(n, seq):\n",
" for i in seq:\n",
" if i > n:\n",
" break\n",
" yield i\n",
"sum(less_or_eq(4000000, even(fib_seq())))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"4613732"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 3\n",
"import itertools\n",
"def prime(n, primes):\n",
" for p in primes:\n",
" if n % p == 0:\n",
" return False\n",
" if p * p > n:\n",
" break\n",
" return True\n",
"\n",
"def furui(n):\n",
" primes = [2]\n",
" \n",
" for i in itertools.chain([2], range(3, n, 2)):\n",
" if prime(i, primes):\n",
" primes.append(i)\n",
" while n % i == 0:\n",
" n //= i\n",
" yield i\n",
" if i * i > n:\n",
" yield n\n",
" break\n",
"n=600851475143\n",
"print(list(furui(n)))\n",
"%timeit list(furui(n))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[71, 839, 1471, 6857]\n",
"1000 loops, best of 3: 1.43 ms per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 3(alt.)\n",
"def primegen():\n",
" yield 2\n",
" n = 1\n",
" while True:\n",
" x = 4 * n\n",
" yield x - 1\n",
" yield x + 1\n",
" n += 1\n",
"\n",
"def factor(n):\n",
" for p in primegen():\n",
" while n % p == 0:\n",
" n //= p\n",
" yield p\n",
" if p * p > n:\n",
" yield n\n",
" break\n",
"n=600851475143\n",
"print(list(factor(n)))\n",
"%timeit list(factor(n))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[71, 839, 1471, 6857]\n",
"1000 loops, best of 3: 378 \u00b5s per loop"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 4\n",
"mi = 100\n",
"mx = 999\n",
"largest = (0, 0, 0)\n",
"for i in range(999, mi - 1, -1):\n",
" for j in range(999, i - 1, -1):\n",
" v = i * j\n",
" if v > largest[0]:\n",
" s = str(v)\n",
" if s == s[::-1]:\n",
" largest = (v, i, j)\n",
" else:\n",
" break\n",
"print(largest)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(906609, 913, 993)\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 5\n",
"N = 20\n",
"\n",
"def gcd(n, m):\n",
" while True:\n",
" r = n % m\n",
" if r == 0:\n",
" return m\n",
" n = m\n",
" m = r\n",
"\n",
"def lcm(n, m):\n",
" return n * m // gcd(n, m)\n",
"\n",
"lcmN = 1\n",
"for n in range(1, N + 1):\n",
" lcmN = lcm(lcmN, n)\n",
"print(lcmN)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"232792560\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 6\n",
"N = 100\n",
"s1 = sum([x**2 for x in range(1, n+1)])\n",
"s2 = sum([x for x in range(1, n+1)]) ** 2\n",
"\n",
"print(s1, s2, s2-s1)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"2870 44100 41230\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 7\n",
"from itertools import count\n",
"from math import sqrt\n",
"\n",
"nth = 10001\n",
"primes = [2]\n",
"for i in count(3, 2):\n",
" lim = int(sqrt(i) + 0.5) \n",
" if all(i % p != 0 for p in primes if p <= lim):\n",
" primes.append(i)\n",
" if len(primes) == nth: break\n",
"print(primes[-1])\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"104743\n"
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 8\n",
"v = \"\"\"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\"\"\".replace('\\n', '')\n",
"ncd = 5\n",
"\n",
"from functools import reduce\n",
"\n",
"def f(v):\n",
" for s in (v[i:i+ncd] for i in range(0, len(v) - ncd + 1)):\n",
" yield reduce(lambda x, y: x * y, (int(n) for n in s))\n",
"print(max(f(v)))\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"40824\n"
]
}
],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 9\n",
"N = 1000\n",
"def tripletN(N):\n",
" for a in range(1, N // 3):\n",
" for b in range(a + 1, (N-a+1)//2):\n",
" c = N - a - b\n",
" yield a,b,c\n",
"for a,b,c in tripletN(N):\n",
" if a*a + b*b == c*c:\n",
" print((a,b,c), sum((a,b,c)), a*b*c)\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(200, 375, 425) 1000 31875000\n"
]
}
],
"prompt_number": 10
},
{
"cell_type": "code",
"collapsed": true,
"input": [
"# problem 10(1)\n",
"from math import sqrt\n",
"from itertools import count,takewhile\n",
"try:\n",
" from itertools import ifilter\n",
"except:\n",
" ifilter = filter\n",
"\n",
"def primegen():\n",
" primes = [2]\n",
" yield 2\n",
" for i in count(3, 2):\n",
" lim = int(sqrt(i) + 0.5) \n",
" if all(i % p != 0 for p in primes if p <= lim):\n",
" primes.append(i)\n",
" yield i\n",
"\n",
"def primegen2():\n",
" g = count(2)\n",
" while True:\n",
" prime = next(g)\n",
" yield prime\n",
" g = ifilter(lambda x, prime=prime: x%prime, g)\n",
" \n",
"\n",
"L = lambda x: x < 2000000\n",
"print(sum(takewhile(L, primegen())))\n",
"#print(sum(takewhile(L, primegen2())))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "pyerr",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-11-0813b9799025>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 25\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 26\u001b[0m \u001b[0mL\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m \u001b[1;33m<\u001b[0m \u001b[1;36m2000000\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 27\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtakewhile\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mL\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mprimegen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 28\u001b[0m \u001b[1;31m#print(sum(takewhile(L, primegen2())))\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
"\u001b[1;32m<ipython-input-11-0813b9799025>\u001b[0m in \u001b[0;36mprimegen\u001b[1;34m()\u001b[0m\n\u001b[0;32m 12\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mcount\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 13\u001b[0m \u001b[0mlim\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msqrt\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m0.5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 14\u001b[1;33m \u001b[1;32mif\u001b[0m \u001b[0mall\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[1;36m0\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mp\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mprimes\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m<=\u001b[0m \u001b[0mlim\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 15\u001b[0m \u001b[0mprimes\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 16\u001b[0m \u001b[1;32myield\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
"\u001b[1;32m<ipython-input-11-0813b9799025>\u001b[0m in \u001b[0;36m<genexpr>\u001b[1;34m(.0)\u001b[0m\n\u001b[0;32m 12\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mcount\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 13\u001b[0m \u001b[0mlim\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msqrt\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m0.5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 14\u001b[1;33m \u001b[1;32mif\u001b[0m \u001b[0mall\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[1;36m0\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mp\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mprimes\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m<=\u001b[0m \u001b[0mlim\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 15\u001b[0m \u001b[0mprimes\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 16\u001b[0m \u001b[1;32myield\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
"\u001b[1;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"prompt_number": 11
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 10(2)\n",
"N = 2000000\n",
"from math import sqrt\n",
"\n",
"def make_sieve(n):\n",
" sieve = [True]*n\n",
" for i in range(2, int(sqrt(n))+1):\n",
" if sieve[i]:\n",
" for i in range(i + i, n, i):\n",
" sieve[i] = False\n",
" return sieve\n",
"\n",
"sieve = make_sieve(N)\n",
"print(sum(i for i in range(2, N) if sieve[i]))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"142913828922\n"
]
}
],
"prompt_number": 12
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 11\n",
"sgrid = \"\"\"\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",
"\n",
"grid = []\n",
"for l in sgrid.split('\\n'):\n",
" if not l:\n",
" continue \n",
" grid.append([])\n",
" row = grid[-1]\n",
" for c in l.split(' '):\n",
" row.append(int(c))\n",
"\n",
"import functools\n",
"import operator\n",
"def prod(it):\n",
" return functools.reduce(operator.mul, it)\n",
"\n",
"def f(grid, rows, cols, numbers):\n",
" for r in range(0, rows):\n",
" for c in range(0, cols):\n",
" if c < cols - numbers:\n",
" yield prod(grid[r][c:c+numbers]), 'H', r, c\n",
" if r < rows - numbers:\n",
" yield prod(grid[x][c] for x in range(r, r + numbers)), 'V', r, c\n",
" if c < cols - numbers and r < rows - numbers:\n",
" yield prod(grid[r+x][c+x]\n",
" for x in range(0, numbers)), 'DU', r, c\n",
" if c > numbers and r < rows - numbers:\n",
" yield prod(grid[r+x][c-x]\n",
" for x in range(0, numbers)), 'DD', r, c\n",
"\n",
"print(max(f(grid, len(grid), len(grid[0]), 4)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(70600674, 'DD', 12, 6)\n"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 12(brute force)\n",
"import itertools\n",
"from math import sqrt\n",
"\n",
"def trianglenumber():\n",
" c = itertools.count(1)\n",
" s = 0\n",
" for n in c:\n",
" s += n\n",
" yield s\n",
"\n",
"def divisors(n):\n",
" lim = int(sqrt(n))\n",
" for i in (i for i in range(1, lim + 1) if n % i == 0):\n",
" if i != lim:\n",
" yield n//i\n",
" yield i\n",
"\n",
"for t, d in ((t, len(list(divisors(t)))) for t in trianglenumber()):\n",
" if d > 500:\n",
" break\n",
"d"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 16,
"text": [
"576"
]
}
],
"prompt_number": 16
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 12(alt)\n",
"import itertools\n",
"from math import sqrt\n",
"\n",
"def ndivisors(n):\n",
" lim = int(sqrt(n))\n",
" cnt = 0\n",
" for i in (i for i in range(1, lim + 1) if n % i == 0):\n",
" if i != lim:\n",
" cnt += 1\n",
" cnt += 1\n",
" return cnt\n",
"\n",
"def divisors_of_tri(n):\n",
" # n * (n+1) never have any common divisor\n",
" # (n * (n+1))/2 => n/2 * (n+1) or n * (n+1)/2\n",
" if n % 2 == 0:\n",
" return ndivisors(n/2) * ndivisors(n+1)\n",
" else:\n",
" return ndivisors(n) * ndivisors((n+1)//2)\n",
"\n",
"ith, d = next(itertools.dropwhile(lambda x: x[1] < 500, ((i, divisors_of_tri(i)) for i in itertools.count(1))))\n",
"print(ith * (ith + 1)//2, d)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"76576500 576\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 13\n",
"v = \"\"\"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",
"\n",
"print(str(sum(int(x) for x in v.splitlines()))[:10])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"5537376230\n"
]
}
],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 14\n",
"N = 1000000\n",
"\n",
"def collatzseq(n):\n",
" yield n\n",
" while n != 1:\n",
" if n % 2:\n",
" n = 3 * n + 1\n",
" else:\n",
" n = n // 2\n",
" yield n\n",
"\n",
"max((sum(1 for x in (collatzseq(i))), i) for i in range(2,N))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "pyerr",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-20-149ced036b8c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 11\u001b[0m \u001b[1;32myield\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 12\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 13\u001b[1;33m \u001b[0mmax\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[1;32min\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mcollatzseq\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mN\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;32m<ipython-input-20-149ced036b8c>\u001b[0m in \u001b[0;36m<genexpr>\u001b[1;34m(.0)\u001b[0m\n\u001b[0;32m 11\u001b[0m \u001b[1;32myield\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 12\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 13\u001b[1;33m \u001b[0mmax\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[1;32min\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mcollatzseq\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mN\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;32m<ipython-input-20-149ced036b8c>\u001b[0m in \u001b[0;36m<genexpr>\u001b[1;34m(.0)\u001b[0m\n\u001b[0;32m 11\u001b[0m \u001b[1;32myield\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 12\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 13\u001b[1;33m \u001b[0mmax\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[1;32min\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mcollatzseq\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mN\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"prompt_number": 20
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 14\n",
"N = 1000000\n",
"\n",
"memo = [1] * N\n",
"def ncollatzseq(n):\n",
" i = n\n",
" cnt = 1\n",
" while i != 1 and i >= n:\n",
" cnt += 1\n",
" if i % 2:\n",
" i = 3 * i + 1\n",
" else:\n",
" i = i // 2\n",
" cnt += memo[i] - 1\n",
" memo[n] = cnt\n",
" return cnt\n",
"max((ncollatzseq(i), i) for i in range(2,N))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 21,
"text": [
"(525, 837799)"
]
}
],
"prompt_number": 21
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 15\n",
"N = 20\n",
"\n",
"m = [[0]*20 for x in itertools.repeat(0, 20)]\n",
"\n",
"for i in range(0, N):\n",
" m[0][i] = i + 2\n",
" m[i][0] = i + 2\n",
"\n",
"for i in range(1, N):\n",
" m[i][i] = m[i - 1][i] + m[i][i - 1]\n",
" for j in range(i + 1, N):\n",
" m[j][i] = m[i][j] = m[i][j - 1] + m[i - 1][j]\n",
" \n",
"for i in m:\n",
" print(i)\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]\n",
"[3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231]\n",
"[4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771]\n",
"[5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626]\n",
"[6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628, 15504, 20349, 26334, 33649, 42504, 53130]\n",
"[7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760, 54264, 74613, 100947, 134596, 177100, 230230]\n",
"[8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280, 170544, 245157, 346104, 480700, 657800, 888030]\n",
"[9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770, 490314, 735471, 1081575, 1562275, 2220075, 3108105]\n",
"[10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420, 817190, 1307504, 2042975, 3124550, 4686825, 6906900, 10015005]\n",
"[11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756, 352716, 646646, 1144066, 1961256, 3268760, 5311735, 8436285, 13123110, 20030010, 30045015]\n",
"[12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716, 705432, 1352078, 2496144, 4457400, 7726160, 13037895, 21474180, 34597290, 54627300, 84672315]\n",
"[13, 91, 455, 1820, 6188, 18564, 50388, 125970, 293930, 646646, 1352078, 2704156, 5200300, 9657700, 17383860, 30421755, 51895935, 86493225, 141120525, 225792840]\n",
"[14, 105, 560, 2380, 8568, 27132, 77520, 203490, 497420, 1144066, 2496144, 5200300, 10400600, 20058300, 37442160, 67863915, 119759850, 206253075, 347373600, 573166440]\n",
"[15, 120, 680, 3060, 11628, 38760, 116280, 319770, 817190, 1961256, 4457400, 9657700, 20058300, 40116600, 77558760, 145422675, 265182525, 471435600, 818809200, 1391975640]\n",
"[16, 136, 816, 3876, 15504, 54264, 170544, 490314, 1307504, 3268760, 7726160, 17383860, 37442160, 77558760, 155117520, 300540195, 565722720, 1037158320, 1855967520, 3247943160]\n",
"[17, 153, 969, 4845, 20349, 74613, 245157, 735471, 2042975, 5311735, 13037895, 30421755, 67863915, 145422675, 300540195, 601080390, 1166803110, 2203961430, 4059928950, 7307872110]\n",
"[18, 171, 1140, 5985, 26334, 100947, 346104, 1081575, 3124550, 8436285, 21474180, 51895935, 119759850, 265182525, 565722720, 1166803110, 2333606220, 4537567650, 8597496600, 15905368710]\n",
"[19, 190, 1330, 7315, 33649, 134596, 480700, 1562275, 4686825, 13123110, 34597290, 86493225, 206253075, 471435600, 1037158320, 2203961430, 4537567650, 9075135300, 17672631900, 33578000610]\n",
"[20, 210, 1540, 8855, 42504, 177100, 657800, 2220075, 6906900, 20030010, 54627300, 141120525, 347373600, 818809200, 1855967520, 4059928950, 8597496600, 17672631900, 35345263800, 68923264410]\n",
"[21, 231, 1771, 10626, 53130, 230230, 888030, 3108105, 10015005, 30045015, 84672315, 225792840, 573166440, 1391975640, 3247943160, 7307872110, 15905368710, 33578000610, 68923264410, 137846528820]\n"
]
}
],
"prompt_number": 22
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 16\n",
"sum(int(i) for i in str(2**1000))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 23,
"text": [
"1366"
]
}
],
"prompt_number": 23
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 17\n",
"oneto9 = sum((3,3,5,4,4,3,5,5,4))\n",
"tento19 = sum((3,6,6,8,8,7,7,9,8,8))\n",
"twentyto99 = sum((6,6,5,5,5,7,6,6)) * 10 + oneto9 * 8\n",
"oneto99 = oneto9 + tento19 + twentyto99\n",
"hundred = 7\n",
"_and_ = 3\n",
"thousand = 8\n",
"onehundredto999 = oneto9 * 100 + hundred * 900 + _and_ * 9 * 99 + oneto99 * 9\n",
"3 + thousand + onehundredto999 + oneto99\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 24,
"text": [
"21124"
]
}
],
"prompt_number": 24
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 18 & 67\n",
"def maketable(s):\n",
" return [[int(y) for y in x.split()] for x in s.splitlines()]\n",
"\n",
"def f(t):\n",
" # calculate totals from the bottom to the top of triangle\n",
" s = [[ x for x in t[-1]]] # the bottom row\n",
" for r in t[-2::-1]:\n",
" c = []\n",
" p = s[-1] # use last inserted one\n",
" for j, v in enumerate(r):\n",
" nv = v + max(p[j] ,p[j + 1])\n",
" c.append(nv)\n",
" s.append(c)\n",
" return s\n",
"\n",
"tr = \"\"\"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",
"for i in f(maketable(tr)):\n",
" print(i)\n",
"print(f(maketable(open(\"triangle.txt\", \"r\").read()))[-1])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]\n",
"[125, 164, 102, 95, 112, 123, 165, 128, 166, 109, 122, 147, 100, 54]\n",
"[255, 235, 154, 150, 140, 179, 256, 209, 224, 172, 174, 176, 148]\n",
"[325, 246, 187, 178, 256, 329, 273, 302, 263, 242, 193, 233]\n",
"[378, 317, 231, 321, 354, 372, 393, 354, 360, 293, 247]\n",
"[419, 365, 393, 387, 419, 425, 430, 376, 454, 322]\n",
"[460, 434, 419, 475, 508, 470, 510, 524, 487]\n",
"[559, 499, 479, 536, 514, 526, 594, 616]\n",
"[647, 501, 613, 609, 533, 657, 683]\n",
"[666, 614, 636, 684, 660, 717]\n",
"[686, 640, 766, 731, 782]\n",
"[704, 801, 853, 792]\n",
"[818, 900, 935]\n",
"[995, 999]\n",
"[1074]\n",
"[7273]"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 25
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 19\n",
"days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
"def isleapyear(y):\n",
" return y % 400 == 0 or (y % 100 != 0 and y % 4 == 0)\n",
"\n",
"# number of days in 1900 was 365(was not leap year) and 1900-1-1 was Monday(=1)\n",
"# then 1901-1-1 was Tuesday(=2)\n",
"d = (sum(days) + 1) % 7\n",
"s = 0\n",
"for y in range(1901, 2001):\n",
" for m in range(0, 12):\n",
" if d % 7 == 0:\n",
" s += 1\n",
" d += days[m]\n",
" if m == 1 and isleapyear(y):\n",
" d += 1\n",
"print(s)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"171\n"
]
}
],
"prompt_number": 26
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 19(alt)\n",
"from datetime import date\n",
"sum(date(y, m + 1, 1).weekday() == 6 for m in range(12) for y in range(1901, 2001))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 27,
"text": [
"171"
]
}
],
"prompt_number": 27
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 20\n",
"N = 100\n",
"def fact(n):\n",
" p = 1\n",
" for i in range(1, n + 1):\n",
" p *= i\n",
" return p\n",
"\n",
"import operator\n",
"import functools\n",
"def fact2(n):\n",
" return functools.reduce(operator.mul, range(2, n + 1), 1)\n",
"\n",
"sum(int(d) for d in str(fact(N))), sum(int(d) for d in str(fact2(N)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 28,
"text": [
"(648, 648)"
]
}
],
"prompt_number": 28
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 21\n",
"N = 10000\n",
"def divisors(n):\n",
" yield 1\n",
" lim = int(n ** 0.5 + 0.5)\n",
" for i in (i for i in range(2, lim + 1) if n % i == 0):\n",
" j = n // i\n",
" yield i\n",
" if i != j:\n",
" yield j\n",
"\n",
"numbers = [sum(divisors(i)) for i in range(0,N)]\n",
"sum(i for i in range(1, N) if i < N and numbers[i] < N and numbers[i] != i and numbers[numbers[i]] == i)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 29,
"text": [
"31626"
]
}
],
"prompt_number": 29
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 22\n",
"import csv\n",
"offset = ord(\"A\") - 1\n",
"def score(name, names):\n",
" return sum(ord(c) - offset for c in name) * (names.index(name) + 1)\n",
" \n",
"names = sorted(next(csv.reader(open(\"names.txt\"))))\n",
"sum(score(name, names) for name in names)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 30,
"text": [
"871198282"
]
}
],
"prompt_number": 30
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 23\n",
"N = 28123\n",
"\n",
"def divisors(n):\n",
" yield 1\n",
" lim = int(n ** 0.5 + 0.5)\n",
" for i in (i for i in range(2, lim + 1) if n % i == 0):\n",
" j = n // i\n",
" yield i\n",
" if i != j:\n",
" yield j\n",
"\n",
"def abundant_number(n):\n",
" return sum(divisors(n)) > n\n",
"\n",
"abundant_numbers = [ x for x in range(1, N) if abundant_number(x) ]\n",
"sum(set(range(1,N)) - { x + y for x in abundant_numbers for y in abundant_numbers })"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 31,
"text": [
"4179871"
]
}
],
"prompt_number": 31
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 24\n",
"import itertools\n",
"Nth = 1000000\n",
"digits = '0123456789'\n",
"i, v = next(itertools.dropwhile(lambda x: x[0] < Nth, enumerate(itertools.permutations(digits, len(digits)), start=1)))\n",
"i, int(''.join(v))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 32,
"text": [
"(1000000, 2783915460)"
]
}
],
"prompt_number": 32
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Nth = 1000000\n",
"digits = '0123456789'\n",
"\n",
"import math\n",
"def num_of_permutations(n, k):\n",
" return math.factorial(n) // math.factorial(n - k)\n",
"\n",
"def f(digits, nth):\n",
" num_digits = len(digits)\n",
" da = [ x for x in digits ]\n",
" for i in range(1, num_digits + 1):\n",
" nd = num_of_permutations(num_digits - i, num_digits - i)\n",
" times = nth // nd\n",
" nth %= nd\n",
" yield da[times]\n",
" del(da[times])\n",
"\n",
"int(''.join(f(digits, Nth - 1))) # 0-origin"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 33,
"text": [
"2783915460"
]
}
],
"prompt_number": 33
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 25\n",
"Ndigit = 1000\n",
"\n",
"def fib_seq():\n",
" yield 1\n",
" a, b = 0, 1\n",
" while True:\n",
" n = a + b\n",
" yield n\n",
" a, b = b, n\n",
"\n",
"next(i for i, x in enumerate(fib_seq(), start=1) if len(str(x)) == Ndigit )"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 34,
"text": [
"4782"
]
}
],
"prompt_number": 34
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 26\n",
"N = 1000\n",
"\n",
"def f(n):\n",
" for p in range(2, n):\n",
" for i in range(1, p):\n",
" # fermat's little theorem\n",
" if (10 ** i - 1) % p == 0:\n",
" yield i, p\n",
" break\n",
"\n",
"print(max(f(N)))\n",
"\n",
"import itertools\n",
"print(max(next(x[1]) for x in itertools.groupby(\n",
" ((i, p) for p in range(2, N) for i in range(1, p) if 10**i % p == 1), lambda x: x[1])))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(982, 983)\n",
"(982, 983)"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 27\n",
"from math import sqrt\n",
"import itertools\n",
"\n",
"def make_sieve(n):\n",
" sieve = [True]*n\n",
" for i in range(2, int(sqrt(n))+1):\n",
" if sieve[i]:\n",
" for i in range(i + i, n, i):\n",
" sieve[i] = False\n",
" return sieve\n",
"\n",
"sieve = make_sieve(200000)\n",
"\n",
"# n**2 + an + b is prime\n",
"# n >= 0, abs(a) and abs(b) < 1000\n",
"#\n",
"# when n = 0, 0**2 + a*0 + b then b must be prime\n",
"# and if b is 2 and a is even -> even\n",
"# then b must be odd prime\n",
"#\n",
"# when n = 1, an + b > 0 then a > -b\n",
"\n",
"A=B=1000\n",
"\n",
"def f():\n",
" for b in (i for i, v in enumerate(sieve[3:], start=3) if v and i < B):\n",
" for a in range(-b + 1, A):\n",
" for n in itertools.count():\n",
" if not sieve[(n ** 2 + a * n + b)]:\n",
" break\n",
" yield n, a, b\n",
"\n",
"m = max(f())\n",
"print(m, m[1] * m[2])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(70, -61, 971) -59231\n"
]
}
],
"prompt_number": 36
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 28\n",
"def f(n):\n",
" yield 1\n",
" l = 1\n",
" for i in range(3, n + 1, 2):\n",
" d = i - 1\n",
" b = l + d\n",
" l += d * 4\n",
" yield from range(b, l + 1, d)\n",
"\n",
"N = 1001\n",
"print(sum(f(N)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"669171001\n"
]
}
],
"prompt_number": 37
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 29\n",
"import itertools\n",
"A = range(2, 100 + 1)\n",
"B = range(2, 100 + 1)\n",
"print(len({ a ** b for a in A for b in B }))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"9183\n"
]
}
],
"prompt_number": 38
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 30\n",
"import itertools\n",
"import functools\n",
"import operator\n",
"\n",
"# integer addition is commutative\n",
"# so, only the digits contained in the number have meaning in this problem.\n",
"# eg. 1634 = 1**4 + 6**4 + 3**4 + 4**4 = 4**4 + 3**4 + 6**4 + 1**4\n",
"# 9**5 * 7 = 6digit\n",
"limit = 9**5 * 6\n",
"\n",
"def genseq(m, n):\n",
" yield from itertools.chain.from_iterable(\n",
" map(lambda x: itertools.combinations_with_replacement('01234567890', x),\n",
" range(m, n)))\n",
"\n",
"\n",
"def find(seq):\n",
" # collect numbers under the limit and make unite numbers having same digits(without order)\n",
" for n in {y for y in filter(lambda x: int(x) < limit,\n",
" (''.join(sorted(x)) for x in seq))}:\n",
" v = sum(int(i) ** 5 for i in n)\n",
" if v <= 1: continue\n",
" if n == ''.join(sorted(str(v))):\n",
" #print(v, n)\n",
" yield v\n",
"\n",
"sum(find(genseq(3, 7)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 39,
"text": [
"443839"
]
}
],
"prompt_number": 39
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 32\n",
"import itertools\n",
"import math\n",
"\n",
"# 1 generate multiplicand\n",
"# 2 generate multiplier without digits in multiplier\n",
"# 3 check length of the product is expected\n",
"# and multiplicand, multiplier and product is 1 to n pandigital\n",
"def f(n):\n",
" digits = { str(x) for x in range(1, n + 1) }\n",
" # divide n digit into two. a half of n -> muliplier + multiplicand / another half of n -> product\n",
" # also becase of commutative-property, only need to check a half patterns \n",
" for i in range(1, n // 2 // 2 + 1):\n",
" nmr = math.ceil(n / 2 - i)\n",
" for md in itertools.permutations(digits, i):\n",
" rdigits = digits - set(md)\n",
" for j in range(nmr, nmr + 1):\n",
" for mr in itertools.permutations(rdigits, j):\n",
" x = int(''.join(md))\n",
" y = int(''.join(mr))\n",
" s = x * y\n",
" ss = str(s)\n",
" if len(ss) + i + j == n and not (rdigits - set(mr) - set(ss)):\n",
" yield(s)\n",
"\n",
"sum(set(f(9)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 40,
"text": [
"45228"
]
}
],
"prompt_number": 40
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 35\n",
"def make_sieve(n):\n",
" sieve = [True]*n\n",
" for i in range(2, int(n ** 0.5)+1):\n",
" if sieve[i]:\n",
" for i in range(i + i, n, i):\n",
" sieve[i] = False\n",
" return sieve\n",
"\n",
"def prime_gen(sieve):\n",
" yield from (i for i, v in enumerate(sieve[2:], start=2) if v)\n",
"\n",
"def gen_is_circluar_prime(sieve):\n",
" def f(x):\n",
" def rotation_gen(x):\n",
" sx = str(x)\n",
" yield from(int(sx[i:] + sx[:i]) for i in range(1, len(sx) + 1))\n",
" return all(sieve[i] for i in rotation_gen(x))\n",
" return f\n",
"\n",
"N = 1000000\n",
"sieve = make_sieve(N)\n",
"is_circluar_prime = gen_is_circluar_prime(sieve)\n",
"\n",
"sum(1 for n in (filter(lambda x: is_circluar_prime(x), prime_gen(sieve))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"55"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 38\n",
"N = 9\n",
"pdigital = set(str(x) for x in range(1, N + 1))\n",
"\n",
"def gen(r):\n",
" for n in r:\n",
" for i in range(9 * 10 ** (n - 1), 10 ** n):\n",
" cp = [x for x in str(i)]\n",
" for j in range(2, N // n + 1):\n",
" cp.extend(x for x in str(i * j))\n",
" if len(cp) != N: continue\n",
" yield cp\n",
"\n",
"print(max(int(''.join(i)) for i in filter(lambda x: set(x) == pdigital, gen(range(1, N // 2 + 1)))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"932718654\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 46\n",
"import itertools\n",
"\n",
"def make_sieve(n):\n",
" sieve = [True]*n\n",
" for i in range(2, int(n ** 0.5)+1):\n",
" if sieve[i]:\n",
" for i in range(i + i, n, i):\n",
" sieve[i] = False\n",
" return sieve\n",
"\n",
"def gen_prime(sieve):\n",
" yield from (i for i, v in enumerate(sieve[2:], start=2) if v)\n",
"\n",
"def gen_twice_a_square():\n",
" yield from (2 * c**2 for c in itertools.count(1))\n",
"\n",
"sieve = make_sieve(6000)\n",
"primes = list(gen_prime(sieve))\n",
"twices_a_square = list(itertools.takewhile(lambda x: x < 6000, gen_twice_a_square()))\n",
"\n",
"def f(n, p):\n",
" l = n - p\n",
" return any(x for x in twices_a_square if x == l)\n",
"\n",
"def g(n):\n",
" return not any(p for p in itertools.takewhile(lambda x: x < n, primes) if f(n, p))\n",
"\n",
"def gen_odd_composite(sieve):\n",
" yield from (i for i, v in enumerate(sieve[9:], start=9) if not v and i % 2)\n",
"\n",
"next(n for n in gen_odd_composite(sieve) if g(n))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 6,
"text": [
"5777"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 48\n",
"N = 1000\n",
"print(str(sum(i ** i for i in range(1, N+1)))[-10:])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"9110846700\n"
]
}
],
"prompt_number": 42
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 65\n",
"import functools\n",
"from fractions import Fraction\n",
"\n",
"n = 100\n",
"def f(x):\n",
" if x == 0: return 2\n",
" elif x % 3 != 2: return 1\n",
" else: return x // 3 * 2 + 2\n",
"\n",
"def g(x, y):\n",
" return y + Fraction(1, x)\n",
"\n",
"seq = (f(x) for x in range(n - 1, -1, -1))\n",
"sum(int(x) for x in str(functools.reduce(g, seq).numerator))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"272"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 81\n",
"import itertools\n",
"\n",
"def f(matrix):\n",
" result = []\n",
" result.append(list(itertools.accumulate(matrix[0])))\n",
" for prev, cur in zip(result, matrix[1:]):\n",
" r = [cur[0] + prev[0]]\n",
" for p, c in zip(prev[1:], cur[1:]):\n",
" r.append(c + min(r[-1], p))\n",
" result.append(r)\n",
" return result\n",
"\n",
"print(f([[131,673,234,103, 18],\n",
" [201, 96,342,965,150],\n",
" [630,803,746,422,111],\n",
" [537,699,497,121,956],\n",
" [805,732,524, 37,331]]))\n",
"\n",
"matrix = [[int(c) for c in l.split(',') ] for l in open('matrix.txt')]\n",
"print(f(matrix)[-1])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[[131, 804, 1038, 1141, 1159], [332, 428, 770, 1735, 1309], [962, 1231, 1516, 1938, 1420], [1499, 1930, 2013, 2059, 2376], [2304, 2662, 2537, 2096, 2427]]\n",
"[404948, 370782, 347440, 339116, 325763, 322648, 323613, 303767, 304228, 310297, 313330, 314126, 317348, 317785, 324970, 331105, 327861, 328299, 335787, 333039, 326929, 332060, 332921, 331595, 326033, 335892, 342146, 335160, 338894, 341592, 350597, 350462, 350793, 351743, 341786, 333987, 343473, 347298, 352770, 353689, 343921, 348332, 355545, 363244, 368698, 362955, 368634, 351820, 352622, 354746, 351627, 360120, 363413, 371847, 377293, 381257, 390090, 392517, 386618, 392027, 390027, 397763, 393196, 400818, 403473, 402533, 404950, 406115, 410257, 407261, 416835, 424410, 409537, 416921, 418412, 420784, 423139, 425890, 419356, 427337]\n"
]
}
],
"prompt_number": 43
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 72\n",
"def f(N):\n",
" # making phi table\n",
" # phi(n) = n(1 - 1/p1)(1-1/p2)...(1-1/pm) (px are px|n)\n",
" phi_table = list(range(N + 1))\n",
" # phi_table[i] = i \u2192 phi(n) = \"n\"(1-1/p1)...\n",
" for n in range(2, N + 1):\n",
" if phi_table[n] == n:\n",
" # n is prime\n",
" for l in range(n, N + 1, n):\n",
" # for all n multiples\n",
" phi_table[l] = phi_table[l] - phi_table[l] // n\n",
" # phi_table[l] = l(1-1/n) ... (1-1/nn)\n",
" return phi_table[2:]\n",
"sum(f(1000000))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"303963552391"
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 79\n",
"import collections\n",
"\n",
"def load():\n",
" def t():\n",
" return collections.defaultdict(t)\n",
"\n",
" g = t()\n",
" t = [{} for x in range(10)]\n",
" for l in (l.strip() for l in open('keylog.txt')):\n",
" for n, s in zip(l, l[1:]):\n",
" t[int(n)][int(s)] = '*'\n",
" t[int(s)]['#'] = '*'\n",
" return t\n",
"\n",
"def p(t):\n",
" a = []\n",
" r = {}\n",
" for i, e in enumerate(t):\n",
" if not e:\n",
" continue\n",
" if len(e) == 1:\n",
" a.append(i)\n",
" print('T', i)\n",
" elif '#' not in e:\n",
" print('S', i, sorted(e))\n",
" a.insert(0, i)\n",
" else:\n",
" r[i] = e\n",
" print('P', i, sorted(set(e) - set('#')))\n",
" return a, r\n",
"\n",
"a, r = p(load())\n",
"while r:\n",
" for k, v in sorted(r.items(), key=lambda x: len(x[1])):\n",
" if len(set(v) - set(a + ['#'])) == 0:\n",
" a.insert(1, k)\n",
" del r[k]\n",
"''.join(str(x) for x in a)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"T 0\n",
"P 1 [0, 2, 6, 8, 9]\n",
"P 2 [0, 8, 9]\n",
"P 3 [1, 6, 8]\n",
"P 6 [0, 2, 8, 9]\n",
"S 7 [1, 2, 3, 6, 9]\n",
"P 8 [0, 9]\n",
"P 9 [0]\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"'73162890'"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 89\n",
"import re\n",
"\n",
"m = {\n",
" 'I': 1, 'IV': 4, 'V': 5, 'IX': 9,\n",
" 'X': 10, 'XL': 40, 'L': 50, 'XC': 90,\n",
" 'C': 100, 'CD': 400, 'D': 500, 'CM': 900,\n",
" 'M': 1000\n",
"}\n",
"rm = sorted(m.items(), key=lambda x: x[1], reverse=True)\n",
"p = re.compile('I[VX]?|X[LC]?|C[DM]?|V|L|D|M')\n",
"\n",
"def d(s):\n",
" return sum(m[d.group(0)] for d in p.finditer(s))\n",
" \n",
"def e(n):\n",
" s = []\n",
" for c, i in rm:\n",
" if n >= i:\n",
" v = n // i\n",
" s.extend([c] * v)\n",
" n -= i * v\n",
" return ''.join(s)\n",
"\n",
"sum(len(l) - len(e(d(l))) for l in open('roman.txt').read().split('\\n'))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"743"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# problem 243\n",
"# R(d) = \u03c6(d)/(d-1)\n",
"# \u03c6(n) = n(1-1/p1)(1-1/p2)...(1-1/pn) p1,p2,...,pn are prime divisors of n\n",
"import functools\n",
"import itertools\n",
"\n",
"def make_sieve(n):\n",
" sieve = [True]*n\n",
" for i in range(2, int(sqrt(n))+1):\n",
" if sieve[i]:\n",
" for i in range(i + i, n, i):\n",
" sieve[i] = False\n",
" return sieve\n",
"\n",
"sieve = make_sieve(1000)\n",
" \n",
"def prime_gen():\n",
" yield from (i for i, v in enumerate(sieve[2:], start=2) if v)\n",
"\n",
"def factor(n):\n",
" for p in primegen():\n",
" while n % p == 0:\n",
" n //= p\n",
" yield p\n",
" if p * p > n:\n",
" if n != 1:\n",
" yield n\n",
" break\n",
"\n",
"def phi(n):\n",
" # euler's totient function\n",
" # this function could be written using below rule for this kind of problem, but I choose generic way\n",
" # \u03c6(p) = p-1 when p is prime.\n",
" # \u03c6(nm) = \u03c6(n)\u03c6(m) when n and m don't have common divisor.\n",
" # \u03c6(30) = \u03c6(2)\u03c6(3)\u03c6(5) = 1 * 2 * 4 = 8\n",
" return n * functools.reduce(lambda x, y: x * (1-1/y), set(factor(n)), 1)\n",
"\n",
"ratio = 15499/94744\n",
"d = 1\n",
"for p in prime_gen():\n",
" d *= p\n",
" if phi(d)/(d-1) < ratio:\n",
" d //= p\n",
" break\n",
"n = int(d * phi(d)/(d-1))\n",
"for i in itertools.count(1):\n",
" if (n * i)/(d * i - 1) < ratio:\n",
" break\n",
"print(i * d)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"892371480\n"
]
}
],
"prompt_number": 44
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}