Prouver qu'un nombre est algébrique

10

Inspiré par cette réponse (soulignement le mien):

Nous allons jouer à un jeu. Supposons que vous ayez un certain nombre x . Vous commencez par x , puis vous pouvez ajouter, soustraire, multiplier ou diviser par n'importe quel entier, sauf zéro. Vous pouvez également multiplier par x . Vous pouvez faire ces choses autant de fois que vous le souhaitez. Si le total devient nul, vous gagnez.

Par exemple, supposons que x soit 2/3. Multipliez par 3, puis soustrayez 2. Le résultat est zéro. Vous gagnez!

Supposons que x soit 7 ^ (1/3). Multipliez par x , puis par x à nouveau, puis soustrayez 7. Vous gagnez!

Supposons que x soit √2 + √3. Ici, ce n'est pas facile de voir comment gagner. Mais il s'avère que si vous multipliez par x , soustrayez 10, multipliez par x deux fois et ajoutez 1, alors vous gagnez. (Ce n'est pas censé être évident; vous pouvez l'essayer avec votre calculatrice.)

Mais si vous commencez avec x = π, vous ne pouvez pas gagner. Il n'y a aucun moyen de passer de π à 0 si vous ajoutez, soustrayez, multipliez ou divisez par des nombres entiers, ou multipliez par π, quel que soit le nombre de pas que vous faites. (Ce n'est pas non plus censé être évident. C'est une chose très délicate!)

Des nombres comme √2 + √3 à partir desquels vous pouvez gagner sont appelés algébriques . Les nombres comme π avec lesquels vous ne pouvez pas gagner sont appelés transcendantaux.

Pourquoi est-ce intéressant? Chaque nombre algébrique est lié arithmétiquement aux nombres entiers, et les mouvements gagnants dans le jeu vous montrent comment. Le chemin vers zéro peut être long et compliqué, mais chaque étape est simple et il y a un chemin. Mais les nombres transcendantaux sont fondamentalement différents: ils ne sont pas liés arithmétiquement aux entiers via des étapes simples.


Essentiellement, vous utiliserez les étapes utilisées dans la question citée ci-dessus pour "gagner" le jeu pour une contribution donnée.

Étant donné une constante algébrique réelle, xconvertissez le nombre à zéro en utilisant les opérations autorisées suivantes:

  • Ajoutez ou soustrayez un entier.
  • Multipliez ou divisez par un entier non nul.
  • Multipliez par la constante d'origine x.

L'entrée est une chaîne qui peut contenir des entiers, addition, soustraction, multiplication, division, exponentiation (votre choix de **ou ^, les exposants sont utilisés pour représenter les racines) et des parenthèses. Les espaces dans l'entrée sont facultatifs, mais pas dans la sortie. Vous devez sortir les étapes nécessaires pour obtenir un résultat de zéro, donc la multiplication par 7comme une seule étape serait sortie comme *7. Un espace de fin et / ou une nouvelle ligne est autorisé.

Exemples

0               ->  +0 (or any other valid, or empty)
5/7 + 42        ->  -42 *7 -5 (or shorter: *7 -299)
2^(1/3)         ->  *x *x -2
5*(3**(1/4))    ->  *x *x *x -1875
2^(1/2)+3^(1/2) ->  *x -10 *x *x +1

Le code le plus court gagne.

mbomb007
la source
À quelle distance 0les résultats doivent-ils être? Compte tenu des erreurs d'arrondi et de la précision du flotteur, je pouvais facilement voir des situations problématiques ...
AdmBorkBork
2
@TimmyD La réponse doit être exacte, pour que je puisse effectuer les opérations et obtenir zéro. Consultez les exemples fournis. Il n'y a pas d'arithmétique à virgule flottante.
mbomb007
1
Comment est √2 + √3 algébrique? Si vous multipliez le nombre par lui-même, vous obtenez 5 + 2√6 ... à moins que je manque quelque chose, vous ne pouvez jamais forcer le radical.
Mario Ishac
@ mbomb007 Oups, mes excuses, je n'ai pas compris cela dans le PO.
Mario Ishac
1
C'est une solution à l'équation x^4-10*x^2+1. Voir WolframAlpha
mbomb007

Réponses:

3

SageMath , 108 octets

def f(s):p=map('{:+} '.format,numerator(minpoly(sage_eval(s)/1)));return'*'+p[-1][1:]+'*x '.join(p[-2::-1])

Essayez-le sur SageMathCell .

Explication:

Évaluez symboliquement la chaîne comme un nombre algébrique ( sage_eval()). Chaque nombre algébrique est un zéro d'un polynôme a [0] + a [1] x ^ 1 + a [2] x ^ 2 + ⋯ + a [n] x ^ n avec des coefficients rationnels a [0],…, a [ n ] ( minpoly()). Multipliez tous les coefficients par leur dénominateur commun pour les transformer en entiers ( numerator()), puis écrivez ce polynôme au format de sortie souhaité,

*a[n] +a[n-1] *x +a[n-2] *x … *x +a[1] *x +a[0]

SageMath, 102 octets, presque

lambda s:(lambda a,*p:'*%d'%a+'*x'.join(map(' {:+} '.format,p)))(*numerator(minpoly(1/sage_eval(s))))

Cela fonctionne pour toutes les entrées sauf 0, car un polynôme pour 1 / α est un polynôme pour α avec les coefficients inversés. :-(

Anders Kaseorg
la source
1

Mathematica, 194 224 192 octets

""<>Cases[HornerForm@MinimalPolynomial[ToExpression@#,x]//.{Times->t,x^a_:>Fold[#2~t~#&,x~Table~a],a_~t~b_~t~c_:>a~t~t[b,c]},a_~b_~_:>{b/.t:>"*"/.Plus:>If[a>0,"+",""],ToString@a," "},{0,∞}]&

Voici le caractère unicode à trois octets représentant l'infini dans Mathematica.

Puisque l'entrée est une chaîne, 13 octets sont perdus, ToExpression@ce qui interprète l'entrée de chaîne comme une expression algébrique.

HornerForm@MinimalPolynomial[2^(1/2)+3^(1/2), x]

Rendrait quelque chose comme

1 + x^2 (-10 + x^2)

La prochaine règle de remplacement masse cela en quelque chose qui est structurellement comme

1 + (x * (x * (-10 + (x * (x)))))

Cette forme Horner peut être visualisée comme un arbre:

TreeForm

Nous, selon les règles de l'OP, commençons avec la feuille la plus profonde à droite.

Cases passe par l'expression, en commençant au niveau le plus profond, en prenant chaque nœud parent et sa feuille gauche et en l'assemblant dans une table telle que

"*" "x"   " "
""  "-10" " "
"*" "x"   " "
"*" "x"   " "
"+" "1"   " "

""<> concatène tout avec la chaîne vide.

LLlAMnYP
la source
Cela revient incorrectement -299pour 5/7 + 42.
Anders Kaseorg
@Et donc il omet le * 7 ... Je revérifierai une fois que je serai à la maison
LLlAMnYP
@AndersKaseorg cela fonctionne, mais maintenant j'ai 30 octets de moins.
LLlAMnYP