pith. sign in

arxiv: 2406.18955 · v1 · submitted 2024-06-27 · 🧮 math.CO · math.NT

A Fast Algorithm for Denumerants with Three Variables

Feihu Liu , Guoce Xin This is my paper

Pith reviewed 2026-05-24 00:21 UTC · model grok-4.3

classification 🧮 math.CO math.NT
keywords denumerantthree variablesfast algorithmtime complexityDiophantine equationnon-negative solutionscoprime integers
0
0 comments X

The pith

There exists an algorithm to compute the number of non-negative solutions to a x1 + b x2 + c x3 = n in O(log b) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a method to calculate d(n; a, b, c), the number of non-negative integer solutions to a x1 + b x2 + c x3 = n where a < b < c are distinct positives with gcd 1. The method runs in time proportional to the logarithm of b, independent of the magnitudes of a and c. This matters for efficiently counting solutions to linear Diophantine equations in three variables even when b grows large. A sympathetic reader would value it for making repeated evaluations of the denumerant feasible without time scaling with n or the other parameters.

Core claim

Let a,b,c be distinct positive integers such that a<b<c and gcd(a,b,c)=1. For any non-negative integer n, the denumerant function d(n;a,b,c) denotes the number of solutions of the equation a x1 + b x2 + c x3 = n in non-negative integers x1,x2,x3. We present an algorithm that computes d(n;a,b,c) with a time complexity of O(log b).

What carries the argument

An algorithm that evaluates the three-variable denumerant d(n;a,b,c) and achieves O(log b) running time.

If this is right

  • The running time is bounded solely by the bit length of b.
  • The algorithm applies to every n without additional restrictions beyond the fixed a,b,c conditions.
  • It yields the exact count rather than an approximation or bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar logarithmic-time reductions might exist for counting solutions with four or more fixed variables when suitable ordering and coprimality hold.
  • The approach could support faster dynamic programming variants for the unbounded knapsack counting problem when the item weights satisfy the three-variable ordering.
  • One could test whether the same bound holds after relaxing the distinctness or strict inequality on a,b,c.

Load-bearing premise

The algorithm achieves its stated O(log b) complexity and correctness for arbitrary n under the fixed conditions a < b < c distinct positives with gcd(a,b,c)=1, without dependence on a or c in the complexity bound.

What would settle it

An explicit triple a < b < c with gcd 1 together with some n where the algorithm requires more than a small constant multiple of log b arithmetic operations to return the correct count.

read the original abstract

Let $a,b,c$ be distinct positive integers such that $a<b<c$ and $\gcd(a,b,c)=1$. For any non-negative integer $n$, the denumerant function $d(n;a,b,c)$ denotes the number of solutions of the equation $ax_1+bx_2+cx_3=n$ in non-negative integers $x_1,x_2,x_3$. We present an algorithm that computes $d(n;a,b,c)$ with a time complexity of $O(\log b)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to present an algorithm computing the denumerant d(n; a, b, c) for distinct positive integers a < b < c with gcd(a, b, c) = 1, achieving O(log b) time complexity for arbitrary n.

Significance. A correct O(log b) algorithm independent of a and c would be a notable advance for computing restricted partition functions, as existing methods typically require time linear in the coefficients or in n. No supporting material is supplied to assess whether this holds.

major comments (1)
  1. [Abstract] Abstract: the central claim of an O(log b) algorithm is asserted without any pseudocode, recurrence relation, derivation, or proof sketch. This prevents verification that the running time is independent of a and c (as required by the problem statement) and that the algorithm is correct for arbitrary n.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for reviewing our manuscript. Below we address the major comment point by point. The full manuscript (beyond the abstract) contains the algorithm description, recurrence, derivation, and complexity proof; we believe this addresses the verification concern.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim of an O(log b) algorithm is asserted without any pseudocode, recurrence relation, derivation, or proof sketch. This prevents verification that the running time is independent of a and c (as required by the problem statement) and that the algorithm is correct for arbitrary n.

    Authors: Abstracts conventionally state results without full derivations. The body of the manuscript provides the explicit algorithm (including the key recurrence for the three-variable denumerant and the reduction to O(log b) steps via binary search over residue classes), the derivation from the general theory of linear Diophantine equations, and the proof that the running time depends only on b (independent of a, c, and n). The algorithm is correct for arbitrary n by construction, as it enumerates all feasible solutions in the reduced search space. If the provided manuscript version omitted these sections, we will ensure they are clearly highlighted in the revision. revision: no

Circularity Check

0 steps flagged

No circularity: algorithm claim stands on presented method, not self-referential reduction

full rationale

The manuscript presents a direct algorithmic procedure for evaluating the three-variable denumerant d(n;a,b,c). No equations, recurrences, or parameter-fitting steps are shown that would equate a claimed output to an input by construction. No self-citations are invoked to justify uniqueness or correctness of the core procedure. The O(log b) bound is asserted as a property of the algorithm itself rather than derived from a fitted model or renamed empirical pattern. The derivation chain is therefore self-contained against external verification of the algorithm's runtime and correctness.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the claim rests on the unshown existence of the algorithm itself.

pith-pipeline@v0.9.0 · 5605 in / 1010 out tokens · 30667 ms · 2026-05-24T00:21:28.108581+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Aguil´ o-Gost and P

    F. Aguil´ o-Gost and P. A. Garc´ ıa-S´ anchez,Factoring in embedding dimension three nu- merical semigroups, Electron. J. Combin. 17 (2010), #R138

    work page 2010

  2. [2]

    Aguil´ o-Gost and D

    F. Aguil´ o-Gost and D. Llena,Computing denumerants in numerical 3-semigroups, Quaes- tiones Mathematicae. 41(8) (2018), 1083–1116

    work page 2018

  3. [3]

    D. S. Binner, The number of solutions to ax + by + cz = n and its relation to quadratic residues, J. Integer Seq. 23 (2020), 20.6.5

    work page 2020

  4. [4]

    T. C. Brown, W. S. Chou, and P. J. Shiue, On the partition function of a finite set , Australas. J. Combin. 27 (2003), 193–204

    work page 2003

  5. [5]

    Curtis, On formulas for the Frobenius number of a numerical semigroup , Math

    F. Curtis, On formulas for the Frobenius number of a numerical semigroup , Math. Scand. 67 (1990), 190–192

    work page 1990

  6. [6]

    J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), 1273–1302

    work page 2004

  7. [7]

    Greenberg, Solution to a linear diophantine equation for nonnegative integers , J

    H. Greenberg, Solution to a linear diophantine equation for nonnegative integers , J. Al- gorithms. 9(3) (1988), 343–535. 11

    work page 1988

  8. [8]

    Komatsu, On the number of solutions of the Diophantine equation of Frobenius-general case, Math

    T. Komatsu, On the number of solutions of the Diophantine equation of Frobenius-general case, Math. Commun. 28 (2003), 195–206

    work page 2003

  9. [9]

    Lison¨ ek,Denumerants and their approximations , J

    P. Lison¨ ek,Denumerants and their approximations , J. Combin. Math. Combin. Comput. 18 (1995), 225–232

    work page 1995

  10. [10]

    M. B. Nathanson, Partition with parts in a finite set , Proc. Amer. Math. Soc. 128 (2000), 1269–1273

    work page 2000

  11. [11]

    Popoviciu, Asupra unei probleme de patitie a numerelor , Acad

    T. Popoviciu, Asupra unei probleme de patitie a numerelor , Acad. Republicii Populare Romans, Filiala Cluj, Studii si cercetari stiintifice. 4 (1953), 7–58

    work page 1953

  12. [12]

    Sert¨ oz,On the number of solutions of a Diophantine equation of Frobenius , Discrete Math

    S. Sert¨ oz,On the number of solutions of a Diophantine equation of Frobenius , Discrete Math. Appl. 8 (1998), 153–162

    work page 1998

  13. [13]

    J. J. Sylvester, On the partition of numbers, Quart.J. Pure Appl. Math. 1 (1857), 141–152

    work page

  14. [14]

    J. J. Sylvester, On sub-invariants, i.e., semi-invariants to binary quantics of an unlimited order, Amer. J. Math. 5 (1882), 119–136

    work page

  15. [15]

    Tripathi, The number of solutions to ax+by = n, Fibonacci Quart

    A. Tripathi, The number of solutions to ax+by = n, Fibonacci Quart. 38 (2000), 290–293

    work page 2000

  16. [16]

    Xin, A Euclid style algorithm for MacMahon’s partition analysis , J

    G. Xin, A Euclid style algorithm for MacMahon’s partition analysis , J. Combin Theory, Series A. 131 (2015), 32–60

    work page 2015

  17. [17]

    G. Xin, Y. Zhang, and Z. Zhang, Fast evaluation of generalized Todd polynomials: Appli- cations to MacMahon’s partition analysis and integer programming , arXiv:2304.13323

    work page arXiv

  18. [18]

    G. Xin, Y. Zhang, and Z. Zhang, A combinatorial decomposition of knapsack cones , arXiv:2406.13974. 12

    work page arXiv