La marge est trop étroite

30

Autour de l'année 1637, Pierre de Fermat écrit en marge de sa copie de l'Arithmétique: 

It is impossible to separate a cube into two cubes, or a fourth power 
into two fourth powers, or in general, any power higher than the 
second, into two like powers. I have discovered a truly marvelous 
proof of this, which this margin is too narrow to contain.

Malheureusement pour nous, la marge est encore trop étroite pour contenir la preuve. Aujourd'hui, nous allons écrire dans les marges un programme simple qui confirme la preuve des entrées arbitraires.

Le défi

Nous voulons un programme pour une fonction qui, étant donné une puissance, la sépare en deux paires de deux puissances aussi proches que possible de la puissance. Nous voulons que le programme qui le fait soit aussi petit que possible afin qu'il puisse s'insérer dans les marges.

Contribution

La puissance et le nombre de puissance: c,x

Contraintes: c > 2etx > 2

L'entrée peut se faire par le biais d'arguments de programme, d'arguments de fonction ou de l'utilisateur.

Sortie

Cette chaîne exacte: « a^x + b^x < c^x» avec a, b, cet xremplacé par leurs valeurs entières littérales. aet bdoit être choisi de telle sorte que a^x + b^x < c^xet aucune autre valeur de aou bne le rendrait plus proche c^x. Également:a>=b>0

La sortie peut se faire via la valeur de retour de la fonction, stdout, enregistrée dans un fichier ou affichée à l'écran.

Exemples:

> 3 3
2^3 + 2^3 < 3^3
> 4 3
3^3 + 3^3 < 4^3
> 5 3
4^3 + 3^3 < 5^3
> 6 3
5^3 + 4^3 < 6^3
> 7 3
6^3 + 5^3 < 7^3
> 8 3
7^3 + 5^3 < 8^3

En raison des compétences d'écriture moyennes de Fermat, les caractères non imprimables ne sont pas autorisés. Le programme avec le moins de caractères gagne.

Classements

Voici un extrait de pile pour générer à la fois un classement régulier et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N characters

Alternativement, vous pouvez commencer par:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou si vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

## Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de classement:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Afficher l'extrait de code

code-golf number Le numéro un
la source
1
Je pense que cela devrait être le cas, a>=b>0sinon votre premier exemple serait invalide. Et pourquoi devons-nous afficher <quand vous le souhaitez <=?
flawr
@flawr Fixed :)
TheNumberOne
Serait-il acceptable de prendre les arguments dans l'ordre inverse? D'abord x, alors c?
Reto Koradi
@RetoKoradi Sure :)
TheNumberOne

Réponses:

9

Pyth, 38 octets

Ls^Rvzbjd.imj\^,dz+eoyNf<yTy]Q^UQ2Q"+<

Prend entrée dans ce format:

x
c
orlp
la source
8

Matlab, 169 153 octets

Le score peut être + -1 en fonction des problèmes non résolus dans les commentaires =) Le score reste le même. Ceci est juste une recherche bruteforce pour la meilleure (a,b)paire.

Assez décevant: j'ai d'abord essayé des choses `` fantaisistes '', puis j'ai réalisé que deux boucles imbriquées simples étaient bien plus courtes ...

function f(c,x);
m=0;p=@(x)int2str(x);
X=['^' p(x)];
for b=1:c;for a=b:c;
n=a^x+b^x;
if n<c^x&n>m;m=n;s=[p(a) X ' + ' p(b) X ' < ' p(c) X];end;end;end;
disp(s)

Ancienne version:

function q=f(c,x);
[b,a]=meshgrid(1:c);
z=a.^x+b.^x;
k=find(z==max(z(z(:)<c^x & a(:)>=b(:))),1);
p=@(x)int2str(x);x=['^' p(x)];
disp([p(a(k)) x ' + ' p(b(k)) x ' < ' p(c) x])
flawr
la source
Supprimer les espaces dans m = 0? Pourtant, cela ne vous rapprochera pas de ma réponse: -PP
Luis Mendo
En outre, il semble que vous puissiez supprimer q=de la définition de la fonction
Luis Mendo
Je ne vois la qvariable utilisée nulle part. Vous pouvez raser quelques octets en faisant simplement function f(c,x)et en supprimant également le point-virgule.
rayryeng
8

Mathematica, 79 95 80 octets

Cela pourrait bien tenir sur la marge.

c_~f~x_:=Inactivate[a^x+b^x<c^x]/.Last@Solve[a^x+b^x<c^x&&a>=b>0,{a,b},Integers]

Essai

f[3, 3]
f[4, 3]
f[5, 3]
f[6, 3]
f[7, 3]
f[8, 3]

output

DavidC
la source
7

CJam, 51 46 43 octets

q~_2m*\f+{W$f#)\:+_@<*}$W='^@s+f+"+<".{S\S}

Ce programme complet lit la puissance, puis la base de STDIN.

Essayez-le en ligne dans l' interpréteur CJam .

Dennis
la source
6

Matlab, 141 140 octets

Ceci est codé comme une fonction qui affiche le résultat dans stdout.

function f(c,x)
b=(1:c).^x;d=bsxfun(@plus,b,b');d(d>c^x)=0;[~,r]=max(d(:));sprintf('%i^%i + %i^%i < %i^%i',[mod(r-1,c)+1 ceil(r/c) c;x x x])

Exemple d'utilisation:

>> f(8,3)
ans =
7^3 + 5^3 < 8^3

Ou essayez-le en ligne dans Octave .

Merci à @flawr d'avoir supprimé un octet.

Luis Mendo
la source
J'ai toujours évité sprintfparce que ça semblait si compliqué alors qu'en réalité ça ne l'est vraiment pas! Et j'ai oublié une bsxfunfois de plus, c'est donc une solution très élégante. J'aime particulièrement la façon dont vous avez abusé de l'indexation simple / double dans le dernier argument =) (Vous pouvez aussi y supprimer un espace!)
flawr
Merci! J'utilise habituellement dispaussi, sauf dans Code Golf :-P
Luis Mendo
Si vous utilisez à la fprintfplace de sprintf, il n'affiche pas "ans"
Jonas
@Jonas Mais il imprime le résultat puis l'invite >>dans la même ligne, ce qui est un peu étrange
Luis Mendo
Vous pouvez utiliser fprintf, mais vous devez insérer un retour chariot manuel.
rayryeng
5

CJam, 53 51 octets

l~:C\:X#:U;C2m*{Xf#:+_U<*}$W=~"^"X+:T" + "@T" < "CT

Essayez-le en ligne

Le format d'entrée est x c, qui est l'inverse de l'ordre utilisé dans les exemples.

Explication:

l~    Read and interpret input.
:C    Store c in variable C.
\     Swap x to top.
:X    Store it in variable X.
#     Calculate c^x.
:U;   Store it in variable U as the upper limit, and pop it from stack.
C2m*  Generate all pairs of values less than c. These are candidates for a/b.
{     Start of mapping function for sort.
  X     Get value of x.
  f#    Apply power to calculate [a^x b^x] for a/b candidates.
  :+    Sum them to get a^x+b^x.
  _U<   Compare value to upper limit.
  *     Multiply value and comparison result to get 0 for values above limit.
}$    End of sort block.
W=    Last a/b pair in sorted list is the solution.
~     Unpack it.
"^"X+ Build "^x" string with value of x.
:T    Store it in variable T, will use it 2 more times in output.
" + " Constant part of output.
@     Rotate b to top of stack.
T     "^x" again.
" < " Constant part of output.
C     Value of c.
T     And "^x" one more time, to conclude the output.
Reto Koradi
la source
5

R, 139 caractères

function(c,x)with(expand.grid(a=1:c,b=1:c),{d=a^x+b^x-c^x
d[d>0]=-Inf
i=which.max(d)
sprintf("%i^%4$i + %i^%4$i < %i^%4$i",a[i],b[i],c,x)})
flodel
la source
4

Python 2, 182 161 161 157 octets

Je réponds habituellement dans MATLAB, mais comme il y a déjà deux solutions dans cette langue, je pense que j'essaierais une autre langue :)

def f(c,x):print max([('%d^%d + %d^%d < %d^%d'%(a,x,b,x,c,x),a**x+b**x) for b in range(1,c+1) for a in range(b,c+1) if a**x+b**x<c**x],key=lambda x:x[1])[0]

Code non golfé avec explications

def f(c,x): # Function declaration - takes in c and x as inputs

    # This generates a list of tuples where the first element is 
    # the a^x + b^x < c^x string and the second element is a^x + b^x
    # Only values that satisfy the theorem have their strings and their
    # corresponding values here
    # This is a brute force method for searching
    lst = [('%d^%d + %d^%d < %d^%d'%(a,x,b,x,c,x),a**x+b**x) for b in range(1,c+1) for a in range(b,c+1) if a**x+b**x<c**x]

    # Get the tuple that provides the largest a^x + b^x value
    i = max(lst, key=lambda x:x[1])

    # Print out the string for this corresponding tuple
    print(i[0])

Exemples d'exécutions

J'ai exécuté ceci dans IPython:

In [46]: f(3,3)
2^3 + 2^3 < 3^3

In [47]: f(4,3)
3^3 + 3^3 < 4^3

In [48]: f(5,3)
4^3 + 3^3 < 5^3

In [49]: f(6,3)
5^3 + 4^3 < 6^3

In [50]: f(7,3)
6^3 + 5^3 < 7^3

In [51]: f(8,3)
7^3 + 5^3 < 8^3

Essayez-le en ligne!

http://ideone.com/tMjGdh

Si vous souhaitez exécuter le code, cliquez sur le lien d' édition en haut, puis modifiez le paramètre STDIN avec deux entiers séparés par un espace. Le premier entier est cet le suivant est x. En ce moment, c=3et x=3son résultat est actuellement affiché.

rayryeng - Réintégrer Monica
la source
3

Pyth, 53 52 50 octets

Ls^ReQbs[j" + "+R+\^eQ_Sh.MyZf<yT^FQ^UhQ2" < "j\^Q

Essayez-le en ligne.

Prend en entrée c,xoù cest le nombre cible et xest la base.

PurkkaKoodari
la source
2

C, 175 octets

a,b,m,A,B,M;p(
a,x){return--x
?a*p(a,x):a;}f
(c,x){M=p(c,x)
;for(a=c,b=1;a
>=b;)(m=p(c,x)
-p(a,x)-p(b,x
))<0?--a:m<M?
(M=m,B=b++,A=
a):b++;printf
("%d^%d + %d"
"^%d < %d^%d",
A,x,B,x,c,x);}

Pour ajuster le code dans la marge, j'ai inséré des sauts de ligne et divisé un littéral de chaîne ci-dessus - le code golfé à compter / compiler est

a,b,m,A,B,M;p(a,x){return--x?a*p(a,x):a;}f(c,x){M=p(c,x);for(a=c,b=1;a>=b;)(m=p(c,x)-p(a,x)-p(b,x))<0?--a:m<M?(M=m,B=b++,A=a):b++;printf("%d^%d + %d^%d < %d^%d",A,x,B,x,c,x);}

La fonction fprend cet xcomme arguments, et produit le résultat sur stdout.

Explication

Il s'agit d'une solution itérative qui zigzague la ligne définie par a^x + b^x = c^x. Nous commençons par a=cet b=1. De toute évidence, cela nous place du mauvais côté de la ligne, car c^x + 1 > c^x. Nous décrémentons ajusqu'à franchir la ligne. Lorsque nous sommes en dessous de la ligne, nous augmentons bjusqu'à ce que nous la traversions dans l'autre sens. Répétez jusqu'à ce que vous vous bréunissiez a, en vous souvenant de la meilleure solutionAB fur et à mesure. Imprimez-le ensuite.

pest une implémentation récursive simple de a^x(pourx>0 ) car C ne fournit aucun opérateur pour l'exponentiation.

En pseudo-code: 

a=c
b=1
M = c^x

while a >= b
do
   m = c^x - a^x - b^x
   if m < 0
      a -= 1
   else // (m > 0, by Fermat's Last Theorem)
      if m < M
         A,B,M = a,b,m
      b += 1
done
return A,B

Limites

c^xdoit être représentable dans la plage de int. Si cette limitation est trop restrictive, la signature de ppourrait être trivialement modifiée en long p(long,int)ou double p(double,int), etm et Men longou doublerespectivement, sans aucune modification def() .

Programme de test

Cela accepte cet xcomme arguments de ligne de commande et imprime le résultat.

#include<stdio.h>
int main(int argc, char**argv) {
    if (argc <= 2) return 1;
    int c = atoi(argv[1]);
    int x = atoi(argv[2]);
    f(c,x);
    puts("");
    return 0;
}
Toby Speight
la source
1

Haskell, 120 octets

Je pense que je l'ai joué autant que possible:

c%x=a&" + "++b&" < "++c&""where(_,a,b)=maximum[(a^x+b^x,a,b)|b<-[1..c],a<-[b..c],a^x+b^x<c^x];u&v=show u++"^"++show c++v

Non golfé:

fn c x = format a " + " ++ format b " < " ++ format c ""
    where format :: Integer -> String -> String
          -- `format u v` converts `u`, appends an exponent string, and appends `v`
          format u v = show u ++ "^" ++ show c ++ v
          -- this defines the variables `a` and `b` above
          (_, a, b) = maximum [(a^x + b^x, a, b) | b <- [1..c], 
                                                   a <- [b..c],
                                                   a^x + b^x < c^x]

Usage:

Prelude> 30 % 11
"28^30 + 28^30 < 30^30"
CR Drost
la source
0

Haskell, 132 128 octets

x!y=x++show y
c#x=(\[_,a,b]->""!a++"^"!x++" + "!b++"^"!x++" < "!c++"^"!x)$maximum[[a^x+b^x,a,b]|a<-[0..c],b<-[0..a],a^x+b^x<c^x]

Exemple d'utilisation: 7 # 3renvoie la chaîne "6^3 + 5^3 < 7^3".

nimi
la source
0

Perl 5, 119 octets

Un sous-programme:

{for$b(1..($z=$_[0])){for(1..$b){@c=("$b^$o + $_^$o < $z^$o",$d)if($d=$b**($o=$_[1])+$_**$o)<$z**$o and$d>$c[1]}}$c[0]}

Utilisez par exemple:

print sub{...}->(8,3)
msh210
la source
0

Rubis, 125 octets

Fonction anonyme. Construit une liste de avaleurs, l'utilise pour construire des a,bpaires, puis trouve le maximum pour celles qui correspondent aux critères et renvoie une chaîne à partir de là.

->c,x{r=[];(1..c).map{|a|r+=([a]*a).zip 1..a}
a,b=r.max_by{|a,b|z=a**x+b**x;z<c**x ?z:0}
"#{a}^#{x} + #{b}^#{x} < #{c}^#{x}"}
Encre de valeur
la source