Project Euler Q21 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "86e06153",
   "metadata": {},
   "source": [
    "### Q21\n",
    "Evaluate the sum of all the amicable numbers under 10000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "16dac2f4-3864-43fc-a8a0-e99049bf2d12",
   "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 combinations(elements):\n",
    "    if len(elements) == 0: \n",
    "        return [[]]\n",
    "    comb = []\n",
    "    for i in combinations(elements[1:]):\n",
    "        comb += [i, i+[elements[0]]]\n",
    "    return comb\n",
    "\n",
    "def simple_sieve(n):\n",
    "    result = []\n",
    "    sieve = [True] * (n+1)\n",
    "    for p in range(2, n+1):\n",
    "        if (sieve[p]):\n",
    "            result.append(p)\n",
    "            for i in range(p, n+1, p):\n",
    "                sieve[i] = False\n",
    "    return result\n",
    "             \n",
    "def prime_numbers(n):\n",
    "    limit = int(n**(1/2))+1\n",
    "    primes = simple_sieve(limit)\n",
    "    low = limit\n",
    "    high = limit * 2\n",
    "    while low < n:\n",
    "        if high >= n:\n",
    "            high = n\n",
    "        mark = [True for i in range(limit + 1)]\n",
    "        for i in range(len(primes)):\n",
    "            loLim = (low // primes[i]) * primes[i]\n",
    "            if loLim < low:\n",
    "                loLim += primes[i]\n",
    "            for j in range(loLim, high, primes[i]):\n",
    "                mark[j - low] = False\n",
    "        for i in range(low, high):\n",
    "            if mark[i - low]:\n",
    "                primes.append(i)\n",
    "        low = low + limit\n",
    "        high = high + limit\n",
    "    return primes\n",
    "\n",
    "def m_power_n(m,max_range):\n",
    "    idx = 1\n",
    "    temp = m ** idx\n",
    "    result = []\n",
    "    while temp <= max_range:\n",
    "        result.append(temp)\n",
    "        temp *= m\n",
    "    return result\n",
    "\n",
    "def prime_factors(n):\n",
    "    i = 2\n",
    "    factors = []\n",
    "    while i * i <= n:\n",
    "        if n % i:\n",
    "            i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i)\n",
    "    if n > 1:\n",
    "        factors.append(n)\n",
    "    return factors\n",
    "\n",
    "def unique(x_vector):\n",
    "    return [list(x) for x in set(tuple(x) for x in x_vector)]\n",
    "\n",
    "def d(n):\n",
    "    return sum([prod(x_vector) for x_vector in [[1]]+unique(combinations(prime_factors(n))[1:-1])])\n",
    "\n",
    "def sum_amicable_numbers(max_range,exclude_end=True):\n",
    "    if not exclude_end:\n",
    "        max_range += 1\n",
    "    result = 0\n",
    "    sieve = [True]*max_range    \n",
    "    for i in prime_numbers(max_range):\n",
    "        sieve[i] = False\n",
    "        for j in m_power_n(i,max_range):\n",
    "            sieve[j] = False\n",
    "    for i in range(2,max_range-1):\n",
    "        if sieve[i] and len(prime_factors(i))>2:\n",
    "            j = d(i)\n",
    "            i_square = i*i\n",
    "            count = 2\n",
    "            while i_square < max_range:\n",
    "                sieve[i_square] = False\n",
    "                i_square *= count*count\n",
    "                count += 1\n",
    "            if j < max_range and i < j and d(j)==i:\n",
    "                result += i+j\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "73650e3b-dd45-44bf-b084-8e76364a9233",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 178 ms, sys: 9.91 ms, total: 188 ms\n",
      "Wall time: 186 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "31626"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "sum_amicable_numbers(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc914513-1ef9-4b32-9b04-ef1a7b7c7261",
   "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