Source-linked AI summary
Computing bounded solutions to linear Diophantine equations with the sum of divisors
Max A. Alekseyev
TL;DR
The paper addresses bounded solution-finding for equations involving the sum-of-divisors function, a setting that includes longstanding open problems. It develops a search method combining pruning and shortcuts, then applies it to discover solutions, certify bounded lists, and raise lower bounds for unresolved cases.
Problem
Finding and certifying solutions to equations involving σ matters because some, including the odd perfect number question, remain unresolved.
Source: §1 · p. 1Method
Results
Applications discover new solutions, certify complete lists below substantially larger bounds, and significantly raise lower bounds for equations with no known solutions.
Source: §1 · pp. 1–2Takeaways & Limitations
For odd almost-perfect numbers other than 1, the search establishes that none exist below 10^90.
Source: §5.1 · p. 8A completed search up to U0 generally cannot be extended to a larger U1; the search must be regenerated.
Source: §7 · p. 13
Abstract
from arXiv · showhide
We propose an efficient computational method for finding all solutions $n\leq U$ to the Diophantine equation $a\sigma(n)=bn+c$, where $a,b,c$ are fixed integer coefficients, $U$ is a given upper bound, and $\sigma(n)$ denotes the sum of divisors of $n$. The method combines advanced pruning of possible prime factors of $n$ and their combinations with several optimization techniques, organized around a \emph{prime-wheel} data structure developed for this purpose. It is implemented in the {\sc SageMath} computer algebra system within the framework of recursively enumerated sets and supports native {\sc MapReduce} parallelization. We apply the method to numerous previously studied equations, discovering new solutions, certifying complete solution lists below substantially larger bounds than previously reported, and substantially improving lower bounds in several open problems involving the sum-of-divisors function.
1. Introduction
Equations involving the sum-of-divisors function include longstanding open questions, while the general equation aσ(n)=bn+c provides a framework for studying them. The paper develops a bounded search method and applies it to discover solutions, certify lists, and raise lower bounds.
1. Introduction
- The existence of an odd perfect number remains an open question within a broader collection of unresolved equations involving σ.Prime numbers satisfy σ(n)=n+1, while perfect numbers satisfy σ(n)=2n.Source: §1 · p. 1
- The method finds all solutions to aσ(n)=bn+c up to a given bound U, for fixed coefficients and positive integer n.Source: §1 · p. 1
- Applications discover new terms and certify complete solution lists below substantially larger bounds than previously reported.Source: §1 · p. 1
- For equations with no known solutions, including quasiperfect and odd almost-perfect numbers, the method significantly raises known lower bounds.Source: §1 · p. 2
2. Notation
The paper’s notation records prime-factor structure and divisor counts used in the search.
2. Notation
- spf(n) and lpf(n) are the smallest and largest prime factors; ν_p(n) is the exponent of p in n.Source: §2 · p. 2
- Ω(n) counts prime factors with multiplicity, while ω(n) counts them without multiplicity.Source: §2 · p. 2
- τ(n) counts divisors, and p_1=2, p_2=3, p_3=5, … index the primes in natural order.Source: §2 · p. 2
3. Method outline
The method recursively traverses a tree of integers up to U, using shortcuts for simple residual cases and a prime wheel to prune candidates. Additional arithmetic restrictions sharpen the search for odd-σ residuals and residuals with shared coefficient factors.
3. Method outline
- Integers up to U form a tree traversed by constrained depth-first search, with each node representing a residual problem for its descendants.At node m, descendants have the form mn′, with spf(n′)>lpf(m), and satisfy a reduced equation.Source: §3 · p. 2
3.1. Shortcuts.
- Shortcuts find residual solutions with Ω(n′)≤2 or ω(n′)=1 without traversing every descendant.Source: §3.1 · p. 2
- For n′=pq, the method rewrites the equation in p and q, then obtains suitable prime pairs by factoring a discriminant or testing divisibility and bounds.For single-prime-power residuals, candidate primes come from factors of a′−c′ or prime-power factors of a′.Source: §3.1 · pp. 2–4
3.2. Pruning with prime wheel.
- A rolling tuple of consecutive primes and dynamic lower bounds excludes infeasible smallest-prime candidates while retaining feasible prime powers for descendants.The wheel is constructed to eventually reach a state covering the smallest prime factor of any solution under consideration.Source: §3.2 · pp. 4–5
3.3. Case of odd σ(n′).
- When parity conditions imply an odd-square residual, the search restricts exponents to even values and uses quadratic-residue tests to prune candidate prime powers.Related parity cases permit a square or twice-square residual and extend the test to p=2.Source: §3.3 · p. 6
- If gcd(a′,c′)>1, its prime factors are forced into n′; incompatible overlap with m rules out solutions, otherwise the search jumps to residuals containing those factors.Source: §3.4 · p. 6
4. SageMath implementation
The SageMath implementation traverses the search tree as a recursively enumerated set, reducing configurations and pruning descendant searches with inherited constraints. It supports MapReduce parallelization, optional search constraints, handling of solutions above U, and a public function for running the method.
4.1. RES framework.
- The RES traversal represents each node by a configuration tuple and uses succ(t) to compute its successors.The tuple contains the reduced coefficients, m, lp, and an aux dictionary for additional constraints.Source: §4.1 · pp. 6–7
4.2. Configuration reduction.
- reduce_abc(t) reduces configurations and prunes subtrees when a configuration has no solutions, including cases where a required prime factor contradicts the lower bound on prime factors.It also recognizes a′ = b′ = c′, reporting the corresponding infinite family instead of traversing that subtree.Source: §4.2 · p. 7
4.3. MapReduce parallelization.
- MapReduce parallelizes traversal and per-node processing; separate configurations have independent wheel state, while practical scaling depends on scheduling and unequal subtree sizes.The prime wheel generates successors and proc(t) handles shortcuts such as producing solutions.Source: §4.3 · p. 7
4.4. Additional constraints.
- Optional constraints include squarefreeness, evenness, coprimality, bounds on ω(n) and Ω(n), and a prescribed τ(n); inherited constraints narrow descendant searches and can skip impossible shortcut cases.For example, ω(n′) ≥ 2 rules out n′ = p^k, and Ω(n′) ≥ 3 rules out n′ = pq.Source: §4.4 · p. 7
4.5. Solutions above U.
- Solutions above U can be sought and reported with strict enabled, but this adds moderate overhead and does not make every large solution reachable by complete search.The larger of the two 2772-hyperperfect numbers reported in Section 5.2 is too large to be reached by a complete search at the corresponding bound.Source: §4.5 · p. 8
4.6. Availability.
- The method is available in the stated GitHub repository through res_solve_sigma_abc(), which takes a, b, c, and U and supports optional parameters.The code documents the full parameter list and format.Source: §4.6 · p. 8
5. Applications
The applications extend searches for numbers with small abundance and hyperperfect numbers, and apply the method to f-perfect variants. Results include new terms, larger certified bounds, and stronger lower bounds for open problems.
5.1. Numbers with a small abundance.
- The quasiperfect lower bound rose to 10^90; searches found no non-power-of-2 almost-perfect numbers below 10^45 or odd almost-perfect numbers other than 1 below 10^90.The 10^90 searches used odd-σ structure and are not representative of general equations.Source: §5.1 · p. 8
- The abundance sequences were routinely completed through 10^20, and the broader congruence σ(n) ≡ 6 (mod n) was completed below 10^27.Abundance 12 includes the infinite subsequence (6p^k) for k≥3; the search focused on sporadic solutions outside it.Source: §5.1 · pp. 8–9
5.2. Hyperperfect numbers.
- The search extended k-hyperperfect sequences to bounds of at least 10^20 and found two new 2772-hyperperfect numbers; the smaller is the fifth, while the larger remains unplaced.The smaller number is 186690534609915040044368953.Source: §5.2 · p. 9
- All solutions to 2σ(n) = 3n + 3 below 3.7 · 10^23 were determined, and previously unknown terms above that bound were also found.The computation required 6336 core-hours.Source: §5.2 · p. 9
5.3. f-perfect numbers.
- For linear f, fixing τ(n)=d converts the f-perfect equation to the target form, and feasible d values are selected using the smallest n with τ(n)=d.The bound n≤U gives an upper bound for τ(n), sharpened using highly composite numbers when U<10^480.Source: §5.3 · p. 10
- All (x + 1)-perfect and (x − 1)-perfect numbers below 10^26 were determined, including a new (x + 1)-perfect term and the position of a recently discovered (x − 1)-perfect term.The new term is 20055918935605248255.Source: §5.3 · p. 10
6. Complexity and search-space analysis
The analysis estimates prime-wheel search costs locally, shows how those costs vary by configuration, and compares the search with sieving and observed behavior. Its bounds depend on equation coefficients and branch-specific arithmetic constraints, so they do not provide a sharp global complexity bound.
6.1. Maximal prime wheels.
- At a fixed configuration, the local estimate simplifies the wheel by ignoring prime powers, shortcuts, gcd-jumps, and additional constraints.The estimate analyzes maximal product-feasible wheels and uses prime-number and Mertens-product asymptotics.Source: §6.1 · pp. 10–11
- For fixed ρ > 1, the number of admissible starting primes satisfies Mρ(V) = T^(1/ρ)+o(1), and at the root M(U) = (log U)^(a/b)+o(1).For σ(n) = 2n + d, the root count is (log U)^(1/2)+o(1).Source: §6.1 · p. 11
- For positive d, the finite-range estimate predicts the last relevant starting prime; for negative d, the wheel-dependent threshold makes that cutoff imprecise.For d > 0 at U = 10^28, the estimate gives X ≈ 8.5, corresponding to starting primes 2, 3, 5, and 7.Source: §6.1 · p. 11
6.2. Dependence on the configuration.
- As the search descends, ρm can approach 1, where the local theorem no longer gives a power saving in log U; summing local costs and shortcut arithmetic remains an obstacle to a sharp global bound.The changing ratio explains the observed dependence of running time on both equation coefficients and the branch being explored.Source: §6.2 · p. 12
- A depth-first serial traversal needs O(log U) simultaneously active configurations, but the implementation also stores successor lists and, in parallel runs, frontier states and arithmetic workspaces.Each descent multiplies the partial product by an integer greater than 1, limiting path depth to ⌊log2 U⌋.Source: §6.2 · p. 12
6.3. Empirical behavior and comparison with earlier algorithms.
- The method avoids sieving every n ≤ U by combining direct shortcuts for prime powers and products of two distinct primes with completeness-preserving prime-wheel pruning.Theorem 3.4 guarantees that the pruning does not discard a feasible continuation.Source: §6.3 · p. 12
- Representative searches reach bounds between about 1025 and 1028 for general constant-abundance equations, while special odd-σ searches reach 1090 through stronger arithmetic pruning.The larger bounds rely on square/twice-square restrictions and quadratic-residue tests, not a coefficient-independent complexity guarantee.Source: §6.3 · p. 12
- For many tested equations, running time is empirically approximated by r^log10 U, with r commonly between 2 and 4; doubling cores from 40 to 80 nearly halves runtime.The paper reports these as empirical behaviors across its tested equations and computations.Source: §6.3 · p. 12
7. Concluding remarks
The implementation has seen little low-level optimization, and searches generally must be regenerated when the bound increases. The authors also describe possible parallel and broader-function extensions, alongside a related application to highly abundant least common multiples.
7. Concluding remarks
- The implementation has had little low-level optimization, and the authors expect Cythonization or a parallel-aware lower-level rewrite could yield substantial speedups.They identify SageMath's Python interpreter overhead as a factor.Source: §7 · p. 13
- Distributed execution across cluster nodes or heterogeneous computers is proposed as a scaling avenue, but has not been pursued in practice.Source: §7 · p. 13
- A completed search to U0 cannot generally be extended incrementally to U1 > U0 because changing U alters shortcut and prime-wheel tests throughout the search.An interrupted traversal at fixed U can in principle resume from serialized unexplored configurations.Source: §7 · p. 13
- A related application used Theorem 3.3 to establish that the largest n for which lcm(1, …, n) is highly abundant is 172.The approach can determine the property for n up to a few hundred, including all n ≤ 172.Source: §7 · p. 13
- With adjusted shortcuts and pruning, the authors report an efficient solver for linear equations involving Euler’s totient function; its manuscript is in preparation.Source: §7 · p. 13