Project Euler Q27 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cccdab0e-89d5-468e-9dec-802431de81df",
   "metadata": {},
   "source": [
    "### Q27\n",
    "Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with \\(n=0\\).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "91e5a1d2-2632-4f67-b305-22fcb4092693",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prime_numbers(n, max_len = False):\n",
    "    result = []\n",
    "    if max_len:\n",
    "        n = max_len**2//5000 + max_len*20\n",
    "    sieve = [True] * (n+1)\n",
    "    for p in range(2, n+1):\n",
    "        if (sieve[p]):\n",
    "            result.append(p)\n",
    "            if max_len and len(result) >= max_len:\n",
    "                return result\n",
    "            for i in range(p, n+1, p):\n",
    "                sieve[i] = False\n",
    "    return result\n",
    "\n",
    "def prod_of_coeff_of_max_quad_primes_eqn(coeff_limits):\n",
    "    max_a = coeff_limits[0]\n",
    "    max_b = coeff_limits[1]\n",
    "    prime_numbers_set = set(prime_numbers((max_b-1)**2+(max_b-1)*max_a+max_b))\n",
    "    candidate_b = [p for p in prime_numbers_set if p <= max_b][::-1]\n",
    "    max_set = {'n':0,'a':0,'b':0}\n",
    "    for b in candidate_b:\n",
    "        for a in range(max_a+1)[::-1]:\n",
    "            for a_sign in [1,-1]:\n",
    "                n = 0\n",
    "                while n*n + a_sign*a*n + b in prime_numbers_set:\n",
    "                    n += 1\n",
    "                if n > max_set['n']:\n",
    "                    max_set['a'] = a_sign*a\n",
    "                    max_set['b'] = b\n",
    "                    max_set['n'] = n\n",
    "    return max_set['a']*max_set['b']\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5623787a-5826-47b6-8c1b-3cea11d65c28",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 282 ms, sys: 770 µs, total: 283 ms\n",
      "Wall time: 279 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-59231"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "prod_of_coeff_of_max_quad_primes_eqn([999,1000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d2a7108-8b3b-4832-a6a1-25c9bfb18674",
   "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