euler_hack_007.ipynb

euler_hack_007.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Euler Hack #7 (Monday 2017-06-19)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1 - Multiples of 3 and 5\n",
    "\n",
    "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",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "225"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(n for n in range(31) if n % 3 == 0 or n % 5 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "233168\n"
     ]
    }
   ],
   "source": [
    "result = 0\n",
    "for n in range(1000):\n",
    "    if n % 3 == 0 or n % 5 == 0:\n",
    "        result += n\n",
    "        \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "66"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "m = math.floor(1000 / 15)\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "233168"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([i * 105 + 60 for i in range(66)]) + 993 + 995 + 996 + 999"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "225"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([i * 105 + 60 for i in range(2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "233168.0"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def solve(n=1000):\n",
    "    return (975 * 7 + 60 + 60) / 2 * 66 + 993 + 995 + 996 + 999\n",
    "solve()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 99 - Largest exponential\n",
    "\n",
    "Comparing two numbers written in index form like 2^11 and 3^7 is not difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.\n",
    "\n",
    "However, confirming that 632382^518061 > 519432^525806 would be much more difficult, as both numbers contain over three million digits.\n",
    "\n",
    "Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.\n",
    "\n",
    "NOTE: The first two lines in the file represent the numbers in the example given above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from math import log\n",
    "\n",
    "base1 = 632382\n",
    "exp1 = 518061\n",
    "\n",
    "base2 = 519432\n",
    "exp2 = 525806\n",
    "log(base1) * exp1 > log(base2) * exp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "709\n"
     ]
    }
   ],
   "source": [
    "largest_val = 0\n",
    "largest_line_no = -1\n",
    "\n",
    "for line_no, line in enumerate(open(\"share/p099_base_exp.txt\")):\n",
    "    base, exp = map(int, line.strip().split(\",\"))\n",
    "    val = log(base) * exp\n",
    "    if val > largest_val:\n",
    "        largest_val = val\n",
    "        largest_line_no = line_no\n",
    "\n",
    "print(largest_line_no + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 112 - Bouncy Numbers\n",
    "\n",
    "Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.\n",
    "\n",
    "Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.\n",
    "\n",
    "We shall call a positive integer that is neither increasing nor decreasing a \"bouncy\" number; for example, 155349.\n",
    "\n",
    "Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.\n",
    "\n",
    "Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.\n",
    "\n",
    "Find the least number for which the proportion of bouncy numbers is exactly 99%."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def is_bouncy(n):\n",
    "    n = str(n)\n",
    "    digits = sorted(n)\n",
    "    return \"\".join(digits) != n and \"\".join(reversed(digits)) != n\n",
    "\n",
    "print(is_bouncy(123))\n",
    "print(is_bouncy(525))\n",
    "print(is_bouncy(321))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1587000 1571130 99.0\n"
     ]
    }
   ],
   "source": [
    "bouncies = 0\n",
    "limit = 2000000 \n",
    "\n",
    "for n in range(limit + 1):\n",
    "    if is_bouncy(n):\n",
    "        bouncies += 1\n",
    "        if bouncies / n == 0.99:\n",
    "            break\n",
    "        \n",
    "print(n, bouncies, 100 * bouncies / n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 80 - Square root digital expansion\n",
    "\n",
    "It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.\n",
    "\n",
    "The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.\n",
    "\n",
    "For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40886\n"
     ]
    }
   ],
   "source": [
    "from decimal import *\n",
    "getcontext().prec = 110\n",
    "\n",
    "total = 0\n",
    "# for num in range(100):\n",
    "for num in range(1, 101):\n",
    "    num = Decimal(num) ** Decimal(.5)\n",
    "    total += sum(map(int, num.to_eng_string().replace(\".\", \"\")[:100]))\n",
    "\n",
    "rational_sqrts = [n for n in range(1, int(math.sqrt(100)))]\n",
    "print(total - sum(rational_sqrts) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 187 - Semiprimes\n",
    "\n",
    "A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.\n",
    "\n",
    "There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.\n",
    "\n",
    "How many composite integers, n < 10^8, have precisely two, not necessarily distinct, prime factors?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "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\n",
    "                \n",
    "prime_list = list(primes(int(10**6 / 2) + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(41538, 499979)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(prime_list), prime_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prime_list[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%cython\n",
    "def solve(list prime_list, int limit):\n",
    "    cdef int i, j, n, m, result, num_primes\n",
    "    result = 0\n",
    "    num_primes = len(prime_list)\n",
    "    for i, n in enumerate(prime_list):\n",
    "        for j in range(i, num_primes):\n",
    "            m = prime_list[j]\n",
    "            if n * m >= limit:\n",
    "                break\n",
    "            result += 1\n",
    "    return result\n",
    "# abandoned"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10470433"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(prime_list, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25 101\n"
     ]
    }
   ],
   "source": [
    "from bisect import bisect\n",
    "\n",
    "max_p = 98\n",
    "idx = bisect(prime_list, max_p, lo=0, hi=len(prime_list))\n",
    "print(idx, prime_list[idx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import floor, ceil, sqrt\n",
    "\n",
    "def solve(prime_list, limit):\n",
    "    result = 0\n",
    "    max_n = ceil(sqrt(limit))\n",
    "    for i, n in enumerate(prime_list):\n",
    "        if n > max_n:\n",
    "            break\n",
    "        max_p = floor(limit / n)\n",
    "        j = bisect(prime_list, max_p, lo=0, hi=len(prime_list))\n",
    "        increment = j - i\n",
    "        result += increment\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17427258\n"
     ]
    }
   ],
   "source": [
    "limit = 10**8\n",
    "# prime_list = list(primes(int(limit / 2) + 1))\n",
    "print(solve(prime_list, limit))"
   ]
  },
  {
   "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
}