Nombre de Frobenius à deux pièces

Le nombre de Frobenius de deux entiers positifs premiers entre eux est le plus grand entier qui ne peut pas s'écrire comme combinaison entière non négative de ces deux valeurs. Dans le problème des deux pièces, si vos dénominations a et b ont pour pgcd un, certains montants se forment exactement et d'autres non ; le nombre de Frobenius est le plus grand montant impossible. Ce calculateur accepte deux entiers positifs, vérifie qu'ils sont premiers entre eux et renvoie ab moins a moins b, la formule fermée pour deux dénominations. Utilisez-le pour des puzzles de timbres-poste, des problèmes de type Chicken McNugget, la préparation aux concours et l'enseignement des semi-groupes numériques, sans déployer un système de calcul formel.

Ce qu'est le nombre de Frobenius à deux pièces et comment la formule fonctionne

Le problème de Frobenius à deux pièces demande le plus grand entier qui ne peut pas s'exprimer comme ax plus by, où x et y sont des entiers non négatifs et a et b des entiers positifs premiers entre eux. Lorsque le pgcd de a et b vaut un, tout entier suffisamment grand est représentable et il existe une plus grande exception bien définie. Sylvester a prouvé que cette exception vaut a fois b moins a moins b.

Par exemple, les dénominations quatre et sept donnent dix-sept : avec des quatre et des sept vous pouvez former tout entier plus grand que dix-sept, mais pas dix-sept. Les dénominations trois et cinq donnent sept. Les dénominations deux et tout entier impair n donnent n moins deux.

Le décompte complémentaire des entiers positifs non représentables est a moins un fois b moins un, divisé par deux ; pour quatre et sept ce décompte vaut neuf. Si une dénomination vaut un, tout entier non négatif est représentable, la formule renvoie moins un et le décompte des non représentables est zéro. C'est mathématiquement cohérent même si une pièce d'une unité rend l'énigme triviale.

La capacité renvoie la paire analysée, leur pgcd (toujours un en cas de succès), un indicateur coprime, le nombre de Frobenius, le décompte des non représentables et la chaîne de formule ab moins a moins b, afin que vous puissiez afficher l'identité à côté de la réponse. L'ordre de a et b ne change pas le résultat numérique, mais la réponse conserve l'ordre envoyé pour que formulaires, carnets et tests de référence restent prévisibles d'une requête à l'autre.

Contrat d'entrée, contrôle de coprimalité et comportement d'erreur

Après l'analyse, le moteur calcule le pgcd d'Euclide. Si ce pgcd n'est pas exactement un, le nombre de Frobenius n'est pas défini car tout entier non divisible par le pgcd reste à jamais inatteignable, de sorte qu'il n'existe pas de plus grand montant impossible. Le gestionnaire rejette alors la paire avec un message clair indiquant que a et b doivent être premiers entre eux.

Les pièges classiques comprennent six et neuf, quatre et six, et dix et quinze. Sur une paire coprime valide le produit a fois b est formé dans la plage des entiers sûrs, le nombre de Frobenius est ab moins a moins b et le décompte des non représentables est l'entier exact (a moins un) fois (b moins un) sur deux. Il n'y a aucune étape à virgule flottante qui pourrait dévier un quasi-entier vers une mauvaise réponse.

Les champs manquants, les chaînes vides et les types non numériques échouent avant toute arithmétique. Une validation échouée n'est pas facturée. Le parcours n'appelle jamais le réseau, n'échantillonne jamais l'aléatoire et ne lit jamais l'horloge, si bien que la même paire produit toujours le même nombre et que les tests de référence restent stables d'un environnement d'exécution à l'autre.

Où un calculateur de Frobenius à deux pièces justifie son existence

Les enseignants utilisent un calculateur du nombre de Frobenius pour que les élèves vérifient des problèmes de timbres-poste à deux pièces ou de type Chicken McNugget sans inverser un signe dans ab moins a moins b. Les préparateurs de concours ont besoin d'un oracle déterministe qui rejette les paires non coprimes au lieu de renvoyer une formule qui ne signifie plus rien lorsqu'un facteur commun est présent.

Les carnets de semi-groupes numériques et les démonstrations de programmation en nombres entiers commencent souvent par deux générateurs et veulent le conducteur, qui vaut un de plus que le nombre de Frobenius, avant de passer à davantage de générateurs. Associez cette page à un vérificateur de nombres premiers entre eux lorsque vous n'avez besoin que du test de pgcd, et à un outil d'Euclide étendu lorsque vous avez besoin des coefficients de Bézout plutôt que du plus grand montant impossible.

Gardez les requêtes dans les bornes documentées, figez les champs numériques dans les tests, et vous obtiendrez des réponses reproductibles pour les devoirs, les greffons LMS et les workers en périphérie, sans déployer un système de calcul formel pour une identité de deux lignes que tout cours de théorie des nombres finit par écrire au tableau.