Browse Teach Curate

Fast Logarithmic-Time Algorithm for the Frobenius Number in Three Variables

An algorithm that computes the Frobenius number of three coprime positive integers (the largest value not expressible as a non-negative integer combination) in worst-case time logarithmic in the inputs, building on Tripathi's approach via ARM sequences and the smallest reachable integer in each residue class modulo the least denomination.

Data Text

A fast algorithm for the Frobenius problem in three variables Daniel Rosin January 3, 2025 1

The Frobenius problem asks: given coin denominations with no common factor, what is the largest amount that cannot be made exactly from them? (For coins of 3 and 5 the answer is 7.) Sylvester solved …