Project Euler Q33 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a469358e-2f57-4bd6-9c8d-c59f3d77920b",
   "metadata": {},
   "source": [
    "### Q33\n",
    "There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.\n",
    "\n",
    "If the product of these four fractions is given in its lowest common terms, find the value of the denominator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "019a77e5-ff2f-4124-a105-b452fcb4a385",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prod(x_vector):\n",
    "    result = 1\n",
    "    for i in x_vector:\n",
    "        result *= i\n",
    "    return result\n",
    "\n",
    "def gcd(x, y):\n",
    "    while(y):\n",
    "        x, y = y, x % y\n",
    "    return x\n",
    "\n",
    "def denominator_of_product_of_digit_cancelling_fractions():\n",
    "    numerators = []\n",
    "    denominators = []\n",
    "    for x in range(1,10):\n",
    "        for y in range(x+1,10):\n",
    "            if 90*x*y//(10*y-x) in range(10,100,10) or 90*x*y//(10*x-y) in range(10,100,10):\n",
    "                numerators.append(x)\n",
    "                denominators.append(y)\n",
    "    return prod(denominators)//gcd(prod(numerators),prod(denominators))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "59e8ca52-58a2-4a3f-a66e-83022712d0c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 21 µs, sys: 3 µs, total: 24 µs\n",
      "Wall time: 26.5 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "denominator_of_product_of_digit_cancelling_fractions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79478346-509c-4a9b-be00-8b46e58873ef",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

Loading