113 lines
2.8 KiB
Plaintext
113 lines
2.8 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "a44edaf3",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Prime Power Triples](https://projecteuler.net/problem=87)\n",
|
|
"\n",
|
|
"First, we'll generate all the primes below $\\sqrt{50000000} \\approx 7071$ - since $7072^2 > 50000000$, we clearly don't need any larger primes."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "75ca6458",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"limit = 50000000\n",
|
|
"primes = prime_range(isqrt(limit))"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "6f022da4",
|
|
"metadata": {},
|
|
"source": [
|
|
"After this, it's just a matter of iterating through all these primes repeatedly to find triples $p^2 + q^3 + r^4 < 50000000$. For each term, we iterate from smallest to largest prime - that way, if we encounter a sum (or even just an individual power) greater than 50000000, we don't have to check any following prime (since the sum will also be greater than 50000000), so we can break early."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "f0017332",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"values = set()\n",
|
|
"for r in primes:\n",
|
|
" if r^4 >= limit:\n",
|
|
" break\n",
|
|
" \n",
|
|
" for q in primes:\n",
|
|
" if q^3 + r^4 >= limit:\n",
|
|
" break\n",
|
|
" \n",
|
|
" for p in primes:\n",
|
|
" n = p^2 + q^3 + r^4\n",
|
|
" if n >= limit:\n",
|
|
" break\n",
|
|
" \n",
|
|
" values.add(n)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "74114043",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"1097343"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"len(values)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "8e625a1d",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Prime power triples: [A134657](https://oeis.org/A134657)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"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.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|