Il existe une équation, en supposant n
et x
sont positifs,
qui exprime la relation entre deux monômes, l'un étant une fausse représentation commune de l'autre. Beaucoup de gens font la simple erreur de les assimiler (ie 3x^2
et (3x)^2
).
Défi
Étant donné un entier positif i
, déterminez et renvoyez la solution n
et x
avec la plus petite somme sous forme de tableau [n, x]
. En cas d'égalité, tout ensemble de solutions est acceptable.
Cas de test
62658722541234765
[15, 11]
202500
[4, 15]
524288
[8, 4]
33044255768277
[13, 9]
code-golf
number-theory
Zach Gates
la source
la source
[x, n]
au lieu de[n, x]
?n
et desx
entiers, non?[n, x]
et il n'y a pas de contrainte de temps @Fatalizen
etx
sont des entiers @LuisMendoRéponses:
Brachylog , 35 octets
Essayez-le en ligne!
Explication
Nous construisons une liste
[N, X]
, oùN >= X
, après lui avoir assigné des valeurs, nous essayons à la fois[N, X]
et[X, N]
comme sortie possible. Par exemple, siN
obtient attribué3
, nous testerons par retours en arrière[3, 1]
,[1, 3]
,[3, 2]
,[2, 3]
,[3, 3]
et[3, 3]
. Après cela, la prochaine étape de retour en arrière se produira sur la valeur deN
, qui ira à4
, etc.la source
Mathematica, 61 octets
Merci aux miles pour avoir sauvé 2 octets, plus tout un tas d'octets que j'ai comptés sans raison!
Calcule une table de paires {n, x}, où x = (i / n) ^ (1 / n), en utilisant toutes les valeurs possibles de n; ne conserve que ceux dont le x correspondant est un entier; renvoie ensuite la paire avec la plus grande valeur de n.
Ici, "toutes les valeurs possibles de n" vont de 1 à 2 * ln (i). Cela ignore la solution {n, x} = {i, 1}, mais ce n'est pas grave car la solution {n, x} = {1, i} suffira si c'est le meilleur choix. Ainsi, x n'a jamais besoin d'être inférieur à 2, ce qui signifie que n * 2 ^ n ≤ i, et tous ces n sont inférieurs à 2 * ln (i).
On peut montrer en utilisant le calcul que la paire {n, x} qui minimise leur somme dans ce contexte est la même que la paire {n, x} avec le plus grand n (sans compter {i, 1}). C'est pourquoi l'initiale
Last
est assez bonne pour trouver la paire optimale.la source
IntegerQ@*Last
pour économiser 2 octets, mais je compte également 63 et non 86 octets dans cette version actuelle.MATL , 22 octets
Les sorties sont
x
,n
dans cet ordre.L'entrée est limitée par le
double
type de données par défaut de MATL , qui peut représenter avec précision des entiers jusqu'à2^53
seulement. Cela exclut le premier test (toujours, il donne le résultat correct, mais cela ne peut pas être garanti en général pour des entrées si grandes).Essayez-le en ligne!
Explication
Le code utilise deux boucles imbriquées:
do...while
boucle extérieure passe par toutes les sommes possiblesn+x
dans l'ordre croissant. La boucle sera arrêtée dès qu'une solution sera trouvée. Cela garantit que nous sortons la solution avec une somme minimale.for each
boucle intérieure teste toutn
etx
avec cette somme. Lorsque la somme coïncide avec l'entrée, la boucle interne est quittée et la condition de boucle de la boucle externe est définie defalse
sorte que l'une soit également quittée.Code commenté:
la source
Gelée ,
2316 octetsÉtant donné
i
, cela génère toutes les paires entières avec remplacement dans[1, i]
. Il effectue ensuite le même filtrage et tri que dans la solution précédente illustrée ci-dessous. Puisqu'il n'y a pas de contrainte de temps, la force brute fonctionnera avec suffisamment de temps.Essayez-le en ligne! , mais n'essayez pas de grandes valeurs en ligne.
Sur mon PC, il faut environ 6 minutes pour calculer le résultat de l'
i = 2048
utilisation de la version inefficace.Version efficace
Il s'agit de la solution précédente pour 23 octets qui est capable de résoudre rapidement les grandes valeurs.
Étant donné
i
, calcule les diviseurs dei
pour générer des paires de[n, x]
oùn
est un diviseur etx = floor( (i/n)^(1/n) )
. Ensuite, il le filtre pour les valeurs oùn * x^n == i
, trie les paires restantes par leur somme et renvoie la première paire.Essayez-le en ligne! ou Vérifiez tous les cas de test.
Explication
la source
PHP, 104 octets
Cela génère toutes les solutions possibles qui ne sont pas dans le format proposé 73 octets
la source
Perl, 52 octets
Comprend +2 pour
-ap
Donnez votre avis sur STDIN
mono.pl
:A pris un effort pour le faire fonctionner
1
aussi. Je n'ai aucune idée si les erreurs en virgule flottante peuvent faire de ce retour la mauvaise réponse pour certaines entrées.la source