Frobenius number for two coins
Coins of 4 and 7 can pay every amount above 17, but never 17 itself: this calculator finds that largest impossible amount for any two coprime values and counts the gaps. Useful for postage-stamp puzzles, contest prep and number theory classes. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 4
- B
- 7
- Gcd
- 1
- Frobenius number
- 17
- Nonrepresentable count
- 9
The Frobenius number of two coprime positive integers is the largest integer that cannot be written as a non-negative integer combination of those two values. In the two-coin problem, if your coins have denominations a and b with gcd one, some amounts can be made exactly and some cannot; the Frobenius number is the largest impossible amount. This calculator accepts two positive integers, checks that they are coprime, and returns ab minus a minus b, the closed-form answer for two denominations. Use it for postage-stamp puzzles, Chicken McNugget style problems, contest prep, and teaching numerical semigroups without standing up a computer-algebra system.
What the two-coin Frobenius number is and how the formula works
The two-coin Frobenius problem asks for the largest integer that cannot be expressed as ax plus by where x and y are non-negative integers and a and b are coprime positive integers. When the gcd of a and b equals one, every sufficiently large integer is representable, and there is a well-defined largest exception. Sylvester proved that this exception equals a times b minus a minus b.
For example, denominations four and seven give seventeen: you can make every integer larger than seventeen with fours and sevens, but seventeen itself cannot. Denominations three and five give seven. Denominations two and any odd integer n give n minus two.
The companion count of positive non-representable integers is a minus one times b minus one, divided by two; for four and seven that count is nine. If one denomination is one, every non-negative integer is representable, the formula returns negative one, and the non-representable count is zero. That is mathematically consistent even though a one-unit coin makes the puzzle trivial.
The capability echoes the parsed pair, their gcd (always one on success), a coprime flag, the Frobenius number, the non-representable count, and the formula string ab minus a minus b so you can show the identity next to the answer.
Input contract, coprimality check, and error behaviour
After parsing, the engine computes the Euclidean gcd. If that gcd is not exactly one, the Frobenius number is undefined because every integer not divisible by the gcd is forever unreachable, so there is no largest impossible amount. Classic traps include six and nine, four and six, and ten and fifteen.
On a valid coprime pair the product a times b is formed inside the safe integer range, the Frobenius number is ab minus a minus b, and the non-representable count is the exact integer (a minus one) times (b minus one) over two. There is no floating-point step that could drift a near-integer into a wrong answer. Missing fields, empty strings, and non-numeric types fail before any arithmetic.
Failed validation is not billed.
Where a two-coin Frobenius calculator earns its keep
Teachers use a Frobenius number calculator so students can check two-coin postage-stamp or Chicken McNugget style problems without flipping a sign in ab minus a minus b. Contest coaches need a deterministic oracle that rejects non-coprime pairs instead of returning a formula that no longer means anything when a common factor is present. Numerical-semigroup notebooks and integer-programming demos often start with two generators and want the conductor, which is one more than the Frobenius number, before they grow to more generators.
Pair this page with a coprime checker when you only need the gcd test, and with an extended Euclidean tool when you need Bézout coefficients rather than the largest impossible amount. Keep requests inside the documented bounds, pin the numeric fields in tests, and you get reproducible answers for homework, LMS plugins, and edge workers without standing up a computer-algebra system for a two-line identity that every number-theory course eventually writes on the board.
What you can do with it
Postage stamps and two-coin puzzles
Find the largest postage that cannot be made exactly with two coprime stamp values, or the largest checkout total two coin denominations cannot hit.
Classroom and contest answer keys
Mark Chicken McNugget style items with a deterministic oracle that rejects non-coprime pairs and returns ab minus a minus b for valid generators.
Numerical semigroup notebooks
Seed two-generator semigroups with the Frobenius number and the non-representable count before you add a third generator or compute the conductor.
FAQ
What is the Frobenius number of two coprime integers?
It is the largest integer that cannot be written as ax + by with non-negative integers x and y. For coprime a and b the value is ab − a − b.
Why must a and b be coprime?
If gcd(a,b) is greater than one, every integer not divisible by that gcd is unreachable, so there is no largest impossible amount.
What happens if one denomination is 1?
Every non-negative integer is representable. The formula returns −1 and the non-representable count is 0, which is the consistent closed-form result.
Does this solve the Chicken McNugget problem for three box sizes?
No. This page is the two-coin (two-generator) case only. Three or more denominations have no equally simple closed form and are out of scope.
How many amounts can never be made with two coin values?
Take one less than each value, multiply, and halve the result: (a − 1)(b − 1)/2. With coins of 4 and 7 that gives 9 impossible amounts, the largest being 17.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/frobenius-number \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":4,"b":7}'const res = await fetch("https://api.kit.forhosting.com/numth/frobenius-number", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 4,
"b": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/frobenius-number",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 4,
"b": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/frobenius-number", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":4,"b":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":4,"b":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/frobenius-number", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"a": 4,
"b": 7
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.frobenius_number",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
When the pair shares a common factor greater than one, infinitely many residues stay unreachable, so there is no largest impossible amount and the task fails with invalid_input instead of inventing a number.
Input contract, coprimality check, and error behaviour
Send a JSON body with two required positive integers a and b. Decimal strings and the aliases x or m for the first value and y or n for the second are accepted so spreadsheets, query strings, and classroom forms can reuse one contract. Each value must be a whole integer from one through ten million; fractions, scientific notation, leading junk, zero, negatives, and values outside that range fail with invalid_input naming the field.
Technical questions
What does the Frobenius number calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.