Home
About
Resume
Projects
Links
Blog
Download notebook
{ "cells": [ { "cell_type": "markdown", "id": "a469358e-2f57-4bd6-9c8d-c59f3d77920b", "metadata": {}, "source": [ "### Q46\n", "What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?" ] }, { "cell_type": "code", "execution_count": 1, "id": "820c6f59-d5d1-4f67-a379-b41d8bb337ac", "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 goldbach_conjecture(search_range = 10000):\n", " prime_set = set(prime_numbers(search_range))\n", " odd_composite_set = set(range(3,search_range+1,2)).difference(prime_set)\n", " for i in sorted(list(odd_composite_set)):\n", " j = 1\n", " is_match = False\n", " while 2*j*j < i:\n", " if (i - 2*j*j) in prime_set:\n", " is_match = True\n", " break\n", " j += 1\n", " if not is_match:\n", " return i" ] }, { "cell_type": "code", "execution_count": 2, "id": "48799cef-e52c-49e6-b182-358c18a5ad36", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 1.38 ms, sys: 475 µs, total: 1.85 ms\n", "Wall time: 1.85 ms\n" ] }, { "data": { "text/plain": [ "5777" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "goldbach_conjecture()" ] }, { "cell_type": "code", "execution_count": null, "id": "af630329-9130-41b7-9eae-dbff1852f068", "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 }
Previous Notebook:
Project Euler Q45
Next Notebook:
Project Euler Q47
Loading