107 lines
2.9 KiB
Plaintext
107 lines
2.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e8fb07d9",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Counting Fractions in a Range](https://projecteuler.net/problem=73)\n",
|
|
"\n",
|
|
"As mentioned in [problem 71](https://projecteuler.net/problem=71), it's easy to compute the next value to appear between two neighbors in a Farey sequence by computing their mediant. Using this fact, we can can repeatedly calculate mediants to get *every* value between two neighbors in the sequence, stopping when the denominators get too big - in fact, for this problem, we *only* need to calculate the denominators.\n",
|
|
"\n",
|
|
"This essentially amounts to a depth-first search of the [Stern-Brocot tree](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) - check it out if you'd like a visualization.\n",
|
|
"\n",
|
|
"Theoretically, we could count using a recursive function, but Python will hit its recursion limit if we try to use it to solve this problem."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "81408bb4",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def stern_brocot_count(d, low, high):\n",
|
|
" middle = low + high\n",
|
|
" if middle > d:\n",
|
|
" return 0\n",
|
|
" \n",
|
|
" return 1 + stern_brocot_count(d, low, middle) + stern_brocot_count(d, middle, high)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "ef9c62b5",
|
|
"metadata": {},
|
|
"source": [
|
|
"Instead, we'll solve the problem with the same principle, just implemented with a stack."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "489b8afb",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"7295372"
|
|
]
|
|
},
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"d = 12000\n",
|
|
"total = 0\n",
|
|
"stack = [(3, 2)]\n",
|
|
"while stack != []:\n",
|
|
" low, high = stack.pop()\n",
|
|
" middle = low + high\n",
|
|
" \n",
|
|
" if middle > d:\n",
|
|
" continue\n",
|
|
" total += 1\n",
|
|
" \n",
|
|
" stack.extend([(low, middle), (middle, high)])\n",
|
|
" \n",
|
|
"total"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "192090b1",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### 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
|
|
}
|