Número de Frobenius de duas moedas

O número de Frobenius de dois inteiros positivos coprimos é o maior inteiro que não pode ser escrito como combinação inteira não negativa desses dois valores. No problema das duas moedas, se as denominações a e b têm mdc um, alguns valores se formam com exatidão e outros não; o número de Frobenius é o maior valor impossível. Esta calculadora aceita dois inteiros positivos, verifica se são coprimos e devolve ab menos a menos b, a fórmula fechada para duas denominações. Use-a em quebra-cabeças de selos postais, problemas no estilo Chicken McNugget, preparação para concursos e no ensino de semigrupos numéricos, sem montar um sistema de álgebra computacional.

O que é o número de Frobenius de duas moedas e como a fórmula funciona

O problema de Frobenius de duas moedas pede o maior inteiro que não pode ser expresso como ax mais by, em que x e y são inteiros não negativos e a e b são inteiros positivos coprimos. Quando o mdc de a e b vale um, todo inteiro suficientemente grande é representável e existe uma exceção máxima bem definida. Sylvester provou que essa exceção é a vezes b menos a menos b.

Por exemplo, as denominações quatro e sete dão dezessete: com quatros e setes você forma todo inteiro maior que dezessete, mas dezessete não. As denominações três e cinco dão sete. As denominações dois e qualquer inteiro ímpar n dão n menos dois.

A contagem complementar de inteiros positivos não representáveis é a menos um vezes b menos um, dividido por dois; para quatro e sete essa contagem é nove. Se uma denominação é um, todo inteiro não negativo é representável, a fórmula devolve menos um e a contagem de não representáveis é zero. Isso é matematicamente coerente, ainda que uma moeda de uma unidade torne o enigma trivial.

A capacidade ecoa o par interpretado, o mdc (sempre um em caso de sucesso), um indicador coprime, o número de Frobenius, a contagem de não representáveis e a cadeia da fórmula ab menos a menos b, para que você mostre a identidade ao lado da resposta.

Contrato de entrada, verificação de coprimalidade e comportamento de erro

Strings decimais e os apelidos x ou m para o primeiro valor e y ou n para o segundo são aceitos, para que planilhas, strings de consulta e formulários de sala reutilizem um único contrato. Depois da leitura, o mecanismo calcula o mdc de Euclides. Se esse mdc não for exatamente um, o número de Frobenius é indefinido porque todo inteiro não divisível pelo mdc permanece inalcançável para sempre, de modo que não há um maior valor impossível.

O tratador então rejeita o par com uma mensagem clara de que a e b devem ser coprimos. Armadilhas clássicas incluem seis e nove, quatro e seis, e dez e quinze. Em um par coprimo válido o produto a vezes b é formado dentro da faixa de inteiros seguros, o número de Frobenius é ab menos a menos b e a contagem de não representáveis é o inteiro exato (a menos um) vezes (b menos um) sobre dois.

Não há passo em ponto flutuante que possa desviar um quase-inteiro para uma resposta errada. Campos ausentes, strings vazias e tipos não numéricos falham antes de qualquer aritmética. A validação com falha não é cobrada.

Onde uma calculadora de Frobenius de duas moedas se justifica

Professores usam uma calculadora do número de Frobenius para que alunos verifiquem problemas de selos postais de duas moedas ou no estilo Chicken McNugget sem inverter um sinal em ab menos a menos b. Treinadores de concurso precisam de um oráculo determinístico que rejeite pares não coprimos em vez de devolver uma fórmula que deixa de significar qualquer coisa quando há um fator comum.

Cadernos de semigrupo numérico e demonstrações de programação inteira costumam começar com dois geradores e querem o condutor, que é um a mais que o número de Frobenius, antes de crescer para mais geradores. Combine esta página com um verificador de coprimos quando você só precisa do teste de mdc, e com uma ferramenta euclidiana estendida quando precisa dos coeficientes de Bézout em vez do maior valor impossível.

Mantenha as solicitações dentro dos limites documentados, fixe os campos numéricos nos testes e você terá respostas reproduzíveis para deveres, plugins LMS e workers de borda, sem levantar um sistema de álgebra computacional para uma identidade de duas linhas que todo curso de teoria dos números acaba escrevendo no quadro.