Skip to content

Instantly share code, notes, and snippets.

@mbarkhau

mbarkhau/euler_hack_008.ipynb

Created July 3, 2017 22:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mbarkhau/4bb53b21d7e357202aafb5dc4141b44b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mbarkhau/4bb53b21d7e357202aafb5dc4141b44b to your computer and use it in GitHub Desktop.
Download ZIP
euler_hack_008.ipynb
Display the source blob
Display the rendered blob
Raw
euler_hack_008.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%reload_ext Cython\n",
"# %%cython\n",
"\n",
"import io\n",
"import re\n",
"import csv\n",
"import json\n",
"import math\n",
"import random\n",
"import numbers\n",
"import decimal\n",
"import fractions\n",
"import statistics\n",
"import operator as op\n",
"import itertools as it\n",
"import functools as ft"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Euler Hack #8 (2017-07-03)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 3 - Largest prime factor\n",
" \n",
"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",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"775146.0992245268"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.sqrt(600851475143)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# https://stackoverflow.com/a/3941967/62997\n",
"def primes(limit):\n",
" a = [True] * limit # Initialize the primality list\n",
" a[0] = a[1] = False\n",
"\n",
" for i, isprime in enumerate(a):\n",
" if isprime:\n",
" yield i\n",
" for n in range(i*i, limit, i): # Mark factors non-prime\n",
" a[n] = False"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def find_largest_prime(num):\n",
" prime_list = list(primes(int(math.sqrt(num)) + 1))\n",
" for prime in reversed(prime_list):\n",
" if num % prime == 0:\n",
" return prime"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"29"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"find_largest_prime(13195)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6857"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"find_largest_prime(600851475143)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 71 - Ordered fractions\n",
"\n",
"Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.\n",
"\n",
"If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:\n",
"\n",
"1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, **2/5**, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8\n",
"\n",
"It can be seen that 2/5 is the fraction immediately to the left of 3/7.\n",
"\n",
"By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.42857142857142855"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"3/7"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.428571"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"428571/1000000"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [],
"source": [
"def find_closest(x, max_d):\n",
" d = max_d\n",
" n = round(x * d)\n",
" closest_n = n\n",
" closest_d = d\n",
" closest = n / d\n",
" while n > 0 and d > 0:\n",
" y = n / d\n",
" if closest < y < x:\n",
" closest_n = n\n",
" closest_d = d\n",
" closest = y\n",
" # print(f\"current {n} / {d} = {y}\")\n",
" # print(f\"closest {closest_n} / {closest_d} = {closest}\")\n",
" if y > x:\n",
" n -= 1\n",
" else:\n",
" d -= 1\n",
" \n",
" return closest_n, closest_d"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(428570, 999997)"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"find_closest(3/7, max_d=1000000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 65 - Convergents of e\n",
"\n",
"Too much text. https://projecteuler.net/problem=65"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [],
"source": [
"def convergent(seq, nth):\n",
" c = 0\n",
" while nth > 0:\n",
" c = fractions.Fraction(1, c + seq[nth])\n",
" nth -= 1\n",
" return seq[0] + c"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(17, 12)"
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sqrt_2_seq = [1] + [2] * 100\n",
"convergent(seq=sqrt_2_seq, nth=3)"
]
},
{
"cell_type": "code",
"execution_count": 97,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"272"
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"e_seq = [2]\n",
"for k in range(1, 100):\n",
" e_seq += [1, 2 * k, 1]\n",
"c = convergent(seq=e_seq, nth=99)\n",
"sum(map(int, str(c.numerator)))\n",
"# 1457/536"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 60 - Prime pair sets\n",
"\n",
"The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.\n",
"\n",
"Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime."
]
},
{
"cell_type": "code",
"execution_count": 193,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"prime_list = list(map(str, primes(100_000_000)))\n",
"prime_set = set(prime_list)"
]
},
{
"cell_type": "code",
"execution_count": 199,
"metadata": {},
"outputs": [],
"source": [
"search_prime_list = prime_list[:10_000]"
]
},
{
"cell_type": "code",
"execution_count": 200,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def find_pair_set(n, prev_pairs=[], min_i=0):\n",
" if n == 0:\n",
" return prev_pairs\n",
" if n == 1:\n",
" print(\"-->\", prev_pairs)\n",
" \n",
" for i, x in enumerate(search_prime_list[min_i:]):\n",
" is_all_pairs = all(\n",
" (x + y in prime_set and y + x in prime_set)\n",
" for y in prev_pairs\n",
" )\n",
" if is_all_pairs:\n",
" next_pairs = prev_pairs + [x]\n",
" pair_set = find_pair_set(n - 1, next_pairs, min_i + i)\n",
" if pair_set is not None:\n",
" return pair_set\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 214,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"%%cython\n",
"\n",
"def cy_find_pair_set(\n",
" int n,\n",
" set prime_set,\n",
" list search_prime_list,\n",
" tuple prev_pairs=(),\n",
" int min_i=0):\n",
" if n == 0:\n",
" return prev_pairs\n",
" if n == 1:\n",
" print(\"-->\", prev_pairs)\n",
" \n",
" cdef int i\n",
" cdef str x\n",
" cdef tuple next_pairs, pair_set\n",
" # cdef bool is_all_pairs, is_all_x_y_prime, is_all_y_x_prime\n",
" cdef list _search_primes = search_prime_list[min_i:]\n",
" \n",
" for i, x in enumerate(_search_primes):\n",
" is_all_x_y_prime = all((x + y in prime_set) for y in prev_pairs)\n",
" if not is_all_x_y_prime:\n",
" continue\n",
" is_all_y_x_prime = all((y + x in prime_set) for y in prev_pairs)\n",
" if not is_all_y_x_prime:\n",
" continue\n",
" \n",
" next_pairs = prev_pairs + (x,)\n",
" pair_set = cy_find_pair_set(\n",
" n - 1, prime_set, search_prime_list, next_pairs, min_i + i)\n",
" if pair_set is not None:\n",
" return pair_set\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 216,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"--> ('3', '7', '109', '673')\n",
"--> ('3', '7', '109', '29059')\n",
"--> ('3', '7', '109', '79693')\n",
"--> ('3', '7', '109', '91159')\n",
"--> ('3', '7', '109', '93187')\n",
"--> ('3', '7', '229', '76819')\n",
"--> ('3', '7', '541', '4159')\n",
"--> ('3', '7', '541', '74317')\n",
"--> ('3', '7', '541', '83023')\n",
"--> ('3', '7', '673', '22921')\n",
"--> ('3', '7', '673', '65293')\n",
"--> ('3', '7', '823', '27823')\n",
"--> ('3', '11', '701', '8747')\n",
"--> ('3', '11', '701', '53777')\n",
"--> ('3', '11', '2069', '2297')\n",
"--> ('3', '11', '2069', '8219')\n",
"--> ('3', '11', '2069', '8747')\n",
"--> ('3', '17', '449', '2069')\n",
"--> ('3', '17', '449', '6353')\n",
"--> ('3', '17', '449', '6599')\n",
"--> ('3', '17', '2069', '2297')\n",
"--> ('3', '31', '1237', '6571')\n",
"--> ('3', '31', '7591', '8431')\n",
"--> ('3', '37', '67', '2377')\n",
"--> ('3', '37', '67', '5923')\n",
"--> ('3', '37', '1237', '8713')\n",
"--> ('3', '37', '1699', '8713')\n",
"--> ('3', '37', '2377', '4159')\n",
"--> ('3', '37', '4729', '7963')\n",
"--> ('3', '37', '5923', '7963')\n",
"--> ('3', '73', '607', '18523')\n",
"--> ('3', '73', '6793', '7159')\n",
"--> ('3', '191', '2069', '8747')\n",
"--> ('3', '229', '613', '49177')\n",
"--> ('3', '331', '739', '8431')\n",
"--> ('3', '373', '823', '15559')\n",
"--> ('3', '467', '617', '4253')\n",
"--> ('3', '467', '617', '87623')\n",
"--> ('3', '1237', '6571', '8713')\n",
"--> ('3', '1699', '6571', '8713')\n",
"--> ('3', '2503', '5281', '5869')\n",
"--> ('3', '3923', '4919', '8783')\n",
"--> ('3', '4729', '7963', '9181')\n",
"--> ('7', '19', '97', '3727')\n",
"--> ('7', '19', '97', '4507')\n",
"--> ('7', '19', '433', '71143')\n",
"--> ('7', '19', '433', '82219')\n",
"--> ('7', '19', '937', '36871')\n",
"--> ('7', '19', '1249', '3727')\n",
"--> ('7', '19', '3727', '5659')\n",
"--> ('7', '61', '487', '8941')\n",
"--> ('7', '61', '487', '63601')\n",
"--> ('7', '61', '1693', '3181')\n",
"--> ('7', '109', '673', '20887')\n",
"--> ('7', '109', '673', '34303')\n",
"--> ('7', '109', '883', '13807')\n",
"--> ('7', '127', '6949', '7723')\n",
"--> ('7', '229', '433', '18433')\n",
"--> ('7', '229', '433', '28729')\n",
"--> ('7', '433', '1471', '3613')\n",
"--> ('7', '433', '3613', '9613')\n",
"--> ('7', '487', '757', '51061')\n",
"--> ('7', '487', '757', '88651')\n",
"--> ('7', '541', '2467', '8167')\n",
"--> ('7', '547', '853', '27241')\n",
"--> ('7', '757', '829', '92593')\n",
"--> ('7', '829', '2671', '3361')\n",
"--> ('7', '853', '2269', '8779')\n",
"--> ('7', '853', '8017', '8779')\n",
"--> ('7', '1237', '1549', '3019')\n",
"--> ('7', '1249', '3727', '6949')\n",
"--> ('7', '1249', '4441', '6949')\n",
"--> ('7', '2089', '2953', '3181')\n",
"--> ('7', '2089', '3181', '4219')\n",
"--> ('7', '2269', '3613', '5821')\n",
"--> ('7', '3019', '7351', '9613')\n",
"--> ('11', '23', '743', '1871')\n",
"--> ('11', '23', '1871', '8171')\n",
"--> ('11', '23', '1871', '8681')\n",
"--> ('11', '23', '3083', '8747')\n",
"--> ('11', '23', '5849', '8681')\n",
"--> ('11', '23', '6329', '7331')\n",
"--> ('11', '239', '1049', '1847')\n",
"--> ('11', '239', '1091', '1847')\n",
"--> ('11', '239', '3467', '5807')\n",
"--> ('11', '251', '941', '42863')\n",
"--> ('11', '353', '4967', '5849')\n",
"--> ('11', '353', '4967', '8219')\n",
"--> ('11', '353', '6791', '8831')\n",
"--> ('11', '701', '7541', '8747')\n",
"--> ('11', '1103', '5807', '6329')\n",
"--> ('11', '2297', '4967', '7127')\n",
"--> ('11', '4013', '4643', '5153')\n",
"--> ('11', '4547', '6791', '8831')\n",
"--> ('11', '4643', '5153', '5849')\n",
"--> ('13', '19', '577', '28219')\n",
"--> ('13', '19', '709', '20173')\n",
"--> ('13', '19', '5077', '6043')\n",
"--> ('13', '19', '6991', '9697')\n",
"--> ('13', '61', '331', '19543')\n",
"--> ('13', '61', '2383', '5431')\n",
"--> ('13', '103', '997', '79423')\n",
"--> ('13', '127', '6733', '7993')\n",
"--> ('13', '331', '577', '83203')\n",
"--> ('13', '1543', '3967', '8053')\n",
"--> ('13', '2383', '5431', '8599')\n",
"--> ('13', '2383', '6733', '8599')\n",
"--> ('13', '2851', '4951', '9697')\n",
"--> ('13', '4327', '4591', '9883')\n",
"--> ('13', '4363', '8461', '9091')\n",
"--> ('13', '4951', '6343', '9697')\n",
"--> ('13', '5197', '5701', '6733')\n"
]
},
{
"data": {
"text/plain": [
"('13', '5197', '5701', '6733', '8389')"
]
},
"execution_count": 216,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cy_find_pair_set(5, prime_set, search_prime_list)"
]
},
{
"cell_type": "code",
"execution_count": 201,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"--> ['3', '7', '109', '673']\n",
"--> ['3', '7', '109', '29059']\n",
"--> ['3', '7', '109', '79693']\n",
"--> ['3', '7', '109', '91159']\n",
"--> ['3', '7', '109', '93187']\n",
"--> ['3', '7', '229', '76819']\n",
"--> ['3', '7', '541', '4159']\n",
"--> ['3', '7', '541', '74317']\n",
"--> ['3', '7', '541', '83023']\n",
"--> ['3', '7', '673', '22921']\n",
"--> ['3', '7', '673', '65293']\n",
"--> ['3', '7', '823', '27823']\n",
"--> ['3', '11', '701', '8747']\n",
"--> ['3', '11', '701', '53777']\n",
"--> ['3', '11', '2069', '2297']\n",
"--> ['3', '11', '2069', '8219']\n",
"--> ['3', '11', '2069', '8747']\n",
"--> ['3', '17', '449', '2069']\n",
"--> ['3', '17', '449', '6353']\n",
"--> ['3', '17', '449', '6599']\n",
"--> ['3', '17', '2069', '2297']\n",
"--> ['3', '31', '1237', '6571']\n",
"--> ['3', '31', '7591', '8431']\n",
"--> ['3', '37', '67', '2377']\n",
"--> ['3', '37', '67', '5923']\n",
"--> ['3', '37', '1237', '8713']\n",
"--> ['3', '37', '1699', '8713']\n",
"--> ['3', '37', '2377', '4159']\n",
"--> ['3', '37', '4729', '7963']\n",
"--> ['3', '37', '5923', '7963']\n",
"--> ['3', '73', '607', '18523']\n",
"--> ['3', '73', '6793', '7159']\n",
"--> ['3', '191', '2069', '8747']\n",
"--> ['3', '229', '613', '49177']\n",
"--> ['3', '331', '739', '8431']\n",
"--> ['3', '373', '823', '15559']\n",
"--> ['3', '467', '617', '4253']\n",
"--> ['3', '467', '617', '87623']\n",
"--> ['3', '1237', '6571', '8713']\n",
"--> ['3', '1699', '6571', '8713']\n",
"--> ['3', '2503', '5281', '5869']\n",
"--> ['3', '3923', '4919', '8783']\n",
"--> ['3', '4729', '7963', '9181']\n",
"--> ['7', '19', '97', '3727']\n",
"--> ['7', '19', '97', '4507']\n",
"--> ['7', '19', '433', '71143']\n",
"--> ['7', '19', '433', '82219']\n",
"--> ['7', '19', '937', '36871']\n",
"--> ['7', '19', '1249', '3727']\n",
"--> ['7', '19', '3727', '5659']\n",
"--> ['7', '61', '487', '8941']\n",
"--> ['7', '61', '487', '63601']\n",
"--> ['7', '61', '1693', '3181']\n",
"--> ['7', '109', '673', '20887']\n",
"--> ['7', '109', '673', '34303']\n",
"--> ['7', '109', '883', '13807']\n",
"--> ['7', '127', '6949', '7723']\n",
"--> ['7', '229', '433', '18433']\n",
"--> ['7', '229', '433', '28729']\n",
"--> ['7', '433', '1471', '3613']\n",
"--> ['7', '433', '3613', '9613']\n",
"--> ['7', '487', '757', '51061']\n",
"--> ['7', '487', '757', '88651']\n",
"--> ['7', '541', '2467', '8167']\n",
"--> ['7', '547', '853', '27241']\n",
"--> ['7', '757', '829', '92593']\n",
"--> ['7', '829', '2671', '3361']\n",
"--> ['7', '853', '2269', '8779']\n",
"--> ['7', '853', '8017', '8779']\n",
"--> ['7', '1237', '1549', '3019']\n",
"--> ['7', '1249', '3727', '6949']\n",
"--> ['7', '1249', '4441', '6949']\n",
"--> ['7', '2089', '2953', '3181']\n",
"--> ['7', '2089', '3181', '4219']\n",
"--> ['7', '2269', '3613', '5821']\n",
"--> ['7', '3019', '7351', '9613']\n",
"--> ['11', '23', '743', '1871']\n",
"--> ['11', '23', '1871', '8171']\n",
"--> ['11', '23', '1871', '8681']\n",
"--> ['11', '23', '3083', '8747']\n",
"--> ['11', '23', '5849', '8681']\n",
"--> ['11', '23', '6329', '7331']\n",
"--> ['11', '239', '1049', '1847']\n",
"--> ['11', '239', '1091', '1847']\n",
"--> ['11', '239', '3467', '5807']\n",
"--> ['11', '251', '941', '42863']\n",
"--> ['11', '353', '4967', '5849']\n",
"--> ['11', '353', '4967', '8219']\n",
"--> ['11', '353', '6791', '8831']\n",
"--> ['11', '701', '7541', '8747']\n",
"--> ['11', '1103', '5807', '6329']\n",
"--> ['11', '2297', '4967', '7127']\n",
"--> ['11', '4013', '4643', '5153']\n",
"--> ['11', '4547', '6791', '8831']\n",
"--> ['11', '4643', '5153', '5849']\n",
"--> ['13', '19', '577', '28219']\n",
"--> ['13', '19', '709', '20173']\n",
"--> ['13', '19', '5077', '6043']\n",
"--> ['13', '19', '6991', '9697']\n",
"--> ['13', '61', '331', '19543']\n",
"--> ['13', '61', '2383', '5431']\n",
"--> ['13', '103', '997', '79423']\n",
"--> ['13', '127', '6733', '7993']\n",
"--> ['13', '331', '577', '83203']\n",
"--> ['13', '1543', '3967', '8053']\n",
"--> ['13', '2383', '5431', '8599']\n",
"--> ['13', '2383', '6733', '8599']\n",
"--> ['13', '2851', '4951', '9697']\n",
"--> ['13', '4327', '4591', '9883']\n",
"--> ['13', '4363', '8461', '9091']\n",
"--> ['13', '4951', '6343', '9697']\n",
"--> ['13', '5197', '5701', '6733']\n"
]
},
{
"data": {
"text/plain": [
"['13', '5197', '5701', '6733', '8389']"
]
},
"execution_count": 201,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"find_pair_set(n=5)"
]
},
{
"cell_type": "code",
"execution_count": 213,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"26033"
]
},
"execution_count": 213,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sum(map(int, ['13', '5197', '5701', '6733', '8389']))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment