Straight-line programs for the solutions of Pell's equation
Abstract
For nonsquare d≥ 2, we construct fixed straight-line programs for the least non-trivial solution (X1,Y1) of x2−dy2=1, using addition, truncated subtraction, multiplication, integer division, exponentiation, and remainder. A geometric-sum identity recovers (X1,Y1) from the coordinate sums of an initial segment of Pell solutions, without knowing how many solutions were summed. Weighted binary encodings make these sums accessible to arithmetic computation. Counting operations with reuse of computed values, one program uses $94$ operations, with intermediate bit lengths bounded by 222O(d). Four additional operations give a $98$-operation program with the bound 22O(d). Hua's bound gives corresponding programs with $103$ and $107$ operations and replaces O(d) by O(√dlog d) in these size bounds. Once the fundamental solution is known, generating-function formulas compute the n-th positive solution in $21$ further operations by extracting its coordinates as base-b digits. We prove that 2X1(X1+1)−1 is the least integer base for which both formulas are defined and correct for every n≥1.
Related
- Short Recurrences and Straight-Line Programs for Primes
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
- A Sharp Bound of Crossing Limit Cycle for Planar piecewise linear Systems with a Straight Switching Line
- Realizing graph automorphisms as geometric symmetries of straight line drawings
- Pillai's equation between k-generalized Pell numbers and Tribonacci numbers
BibTeX
@misc{dumitru2026straightline,
title = {{Straight-line programs for the solutions of Pell's equation}},
author = {Bogdan Dumitru and Mihai Prunescu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28649},
eprint = {2609.28649},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28649},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Straight-line programs for the solutions of Pell's equation
AU - Bogdan Dumitru
AU - Mihai Prunescu
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28649
UR - https://arxiv.org/abs/2609.28649
AB - For nonsquare d≥ 2, we construct fixed straight-line programs for the least non-trivial solution (X_1,Y_1) of x^2−dy^2=1, using addition, truncated subtraction, multiplication, integer division, exponentiation, and remainder. A geometric-sum identity recovers (X_1,Y_1) from the coordinate sums of an initial segment of Pell solutions, without knowing how many solutions were summed. Weighted binary encodings make these sums accessible to arithmetic computation. Counting operations with reuse of computed values, one program uses $94$ operations, with intermediate bit lengths bounded by 2^2^2^O(d). Four additional operations give a $98$-operation program with the bound 2^2^O(d). Hua's bound gives corresponding programs with $103$ and $107$ operations and replaces O(d) by O(√dlog d) in these size bounds. Once the fundamental solution is known, generating-function formulas compute the n-th positive solution in $21$ further operations by extracting its coordinates as base-b digits. We prove that 2X_1(X_1+1)−1 is the least integer base for which both formulas are defined and correct for every n≥1.
ER -