PE_problem_5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 5\n",
    "\n",
    "## Smallest multiple\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "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?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explanation and codes are little bit longer, it can be much shorter,by using some of libraries and built-in functions...\n",
    "I made the 3 functions:\n",
    "    1. looking for factor of a positive integer number\n",
    "    2. cheking for remainder adding lists and sorting\n",
    "    3. finding smallest positive number by every number or so called lowest common multiple of the set of numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "# function to factor a given positive integer n\n",
    "def factors(n):\n",
    "    factors = []\n",
    "    # remove any factors of 2 first\n",
    "    while n % 2 == 0:\n",
    "        factors.append(2)\n",
    "        n = n/2\n",
    "    # now look for odd factors\n",
    "    p = 3\n",
    "    while n != 1:\n",
    "        while n % p == 0:\n",
    "            factors.append(p)\n",
    "            n = n/p\n",
    "        p += 2\n",
    "    return factors\n",
    " \n",
    "# merge two lists of factors based on maximum multiplicities\n",
    "def factor_append(factors,new):\n",
    "    if len(factors) == 0: return new\n",
    "    for i in range(len(new)):\n",
    "        if i > 0 and new[i] == new[i-1]: continue\n",
    "        new_count = new.count(new[i])\n",
    "        old_count = factors.count(new[i])\n",
    "        if new_count > old_count:\n",
    "            for j in range(new_count - old_count): factors.append(new[i])\n",
    "    factors.sort()\n",
    "    return factors\n",
    " \n",
    "# find the smallest positive evenly divisible number for a positive integer n, also known as lowest common multiple\n",
    "def lcm(num):\n",
    "    F = []\n",
    "    for i in range(1,num + 1):\n",
    "        F = factor_append(F,factors(i))\n",
    "    product = 1\n",
    "    for i in F: product *= i\n",
    "    return product\n",
    " \n",
    "\n",
    "product = lcm(20)\n",
    "\n",
    " \n",
    "print (\"Answer is: {}\".format(product))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answer is: 232792560"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution in C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```C\n",
    "#include <stdio.h>\n",
    "#include <stdint.h>\n",
    "\n",
    "int main()\n",
    "{\n",
    "\n",
    "/*the least common multiple of all integers from 2 to 20. We\n",
    "find it with : p_1^m_1 * p_2^m_2... where p[i] are prime numbers and m[i] \n",
    "are the greatest exponent for each p[i] number among the prime factors\n",
    "decomposition of integers between 2 and 20.*/\n",
    "\n",
    "\tint N = 20;\n",
    "\tint prime[8] = {2, 3, 5, 7, 11, 13, 17, 19}; /* primes below 20 */\n",
    "\tint power[8] = {0, 0, 0, 0,  0,  0,  0,  0};\n",
    "\n",
    "\tfor (int i = 2; i < N+1; ++i)\n",
    "\t{\n",
    "    \n",
    "/* for each integer i, for each prime primes[k], find its \n",
    "exponent in prime decomposition of i. */\n",
    "\t\t\n",
    "        int j = i, p;\n",
    "\t\tfor (int m = 0; m < 8; m++)\n",
    "\t\t{\n",
    "\t\t\tp = 0;\n",
    "\t\t\twhile (j > 0 && j%prime[m] == 0)\n",
    "\t\t\t{\n",
    "\t\t\t\t++p;\n",
    "\t\t\t\tj /= prime[m];\n",
    "\t\t\t}\n",
    "\n",
    "\t\t\t/* take exponent if it is greater than used  */\n",
    "            \n",
    "\t\t\tif (p > power[m]) power[m] = p;\n",
    "\t\t}\n",
    "\t}\n",
    "\n",
    "\t\n",
    "\tint answer = 1;\n",
    "\tfor (int m = 0; m < 8; ++m)\n",
    "\t\twhile (power[m]-- > 0)\n",
    "\t\t\tanswer *= prime[m];\n",
    "\n",
    "\tprintf(\"Output: %d\\n\", answer);\n",
    "\treturn 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output: 232792560"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}