Der Rand ist zu schmal

30

Um das Jahr 1637 schrieb Pierre de Fermat am Rande seines Exemplars der Arithmetica: 

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.

Leider ist die Marge für uns immer noch zu eng, um den Beweis aufzunehmen. Heute werden wir ein einfaches Programm in die Ränder schreiben, das den Beweis für willkürliche Eingaben bestätigt.

Die Herausforderung

Wir wollen ein Funktionsprogramm, das eine Potenz in zwei Paare von zwei Potenzen aufteilt, die der Potenz so nahe wie möglich kommen. Wir möchten, dass das Programm, das dies tut, so klein wie möglich ist, damit es in die Ränder passt.

Eingang

Die Kraft und die Macht Nummer: c,x

Einschränkungen: c > 2undx > 2

Die Eingabe kann über Programmargumente, Funktionsargumente oder vom Benutzer erfolgen.

Ausgabe

Diese exakte Zeichenfolge: „ a^x + b^x < c^x“ mit a, b, c, und xmit ihren wörtlichen ganzzahlige Werte ersetzt. aund bmuss so gewählt werden a^x + b^x < c^xund keine anderen Werte von aoder bwürden es näher bringen c^x. Ebenfalls:a>=b>0

Die Ausgabe kann über den Funktionsrückgabewert stdout erfolgen, in einer Datei gespeichert oder auf dem Bildschirm angezeigt werden.

Beispiele:

> 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

Aufgrund der durchschnittlichen Schreibfähigkeiten von Fermat sind nicht druckbare Zeichen nicht zulässig. Das Programm mit der geringsten Anzahl von Zeichen gewinnt.

Bestenlisten

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N characters

Alternativ können Sie mit Folgendem beginnen:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

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

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

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

Code-Snippet anzeigen

code-golf number Die Nummer eins
quelle
1
Ich denke es sollte sein a>=b>0oder dein erstes Beispiel wäre ungültig. Und warum müssen wir anzeigen, <wenn Sie es möchten <=?
Fehler
@
Fehler
Wäre es in Ordnung, die Argumente in umgekehrter Reihenfolge zu behandeln? Erst xdann c?
Reto Koradi
@ RetoKoradi Sicher :)
TheNumberOne

Antworten:

9

Pyth, 38 Bytes

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

Nimmt Eingaben in diesem Format vor:

x
c
orlp
quelle
8

Matlab, 169.153 Bytes

Die Punktzahl kann + -1 sein, abhängig von den ungelösten Problemen in den Kommentaren =) Die Punktzahl bleibt gleich. Dies ist nur eine Bruteforce-Suche nach dem besten (a,b)Paar.

Ziemlich enttäuschend: Ich habe zuerst versucht, mit 'ausgefallenen' Dingen zu experimentieren, und dann festgestellt, dass zwei einfach verschachtelte For-Loops viel kürzer sind ...

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)

Alte 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])
Fehler
quelle
Entfernen Sie die Leerzeichen in m = 0? Dennoch, das wird dich nicht nah an meine Antwort bringen: -PP
Luis Mendo
Es sieht auch so aus, als könnten Sie q=aus der Funktionsdefinition entfernen
Luis Mendo
Ich sehe nicht, dass die qVariable irgendwo verwendet wird. Sie können ein paar Bytes abschneiden, indem Sie einfach das Semikolon function f(c,x)entfernen.
Rayryeng - Wiedereinsetzung von Monica
8

Mathematica, 79 95 80 Bytes

Dies könnte auf den Rand passen.

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

Testen

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

Ausgabe

DavidC
quelle
7

CJam, 51 46 43 Bytes

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

Dieses vollständige Programm liest die Leistung und dann die Basis von STDIN.

Probieren Sie es online im CJam-Interpreter aus .

Dennis
quelle
6

Matlab, 141 140 Bytes

Dies ist eine Funktion, die das Ergebnis in stdout anzeigt.

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])

Beispiel Verwendung:

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

Oder versuchen Sie es online in Octave .

Vielen Dank an @flawr für das Entfernen eines Bytes.

Luis Mendo
quelle
Ich habe es immer gemieden, sprintfweil es so kompliziert schien, obwohl es das eigentlich nicht ist! Und ich habe es bsxfunnoch einmal vergessen , das ist also eine sehr elegante Lösung. Mir gefällt besonders die Art und Weise, wie Sie die einfache / doppelte Indizierung im letzten Argument missbraucht haben =) (Sie könnten dort auch ein Leerzeichen entfernen!)
Fehler
Vielen Dank! Ich benutze normalerweise dispauch, außer in Code Golf :-P
Luis Mendo
Wenn Sie fprintfanstelle von verwenden sprintf, wird "ans" nicht angezeigt
Jonas
@ Jonas Aber es druckt das Ergebnis und dann die Eingabeaufforderung >>in der gleichen Zeile, was ein bisschen seltsam ist
Luis Mendo
Sie können verwenden fprintf, müssen jedoch einen manuellen Wagenrücklauf einfügen.
Rayryeng - Wiedereinsetzung von Monica
5

CJam, 53 51 Bytes

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

Probieren Sie es online aus

Das Eingabeformat x cist das Gegenteil der in den Beispielen verwendeten Reihenfolge.

Erläuterung:

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
quelle
5

R, 139 Zeichen

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
quelle
4

Python 2, 182 161 157 Bytes

Normalerweise antworte ich in MATLAB, aber da es in dieser Sprache bereits zwei Lösungen gibt, würde ich wahrscheinlich eine andere Sprache ausprobieren :)

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]

Ungolfed Code mit Erklärungen

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])

Beispielläufe

Ich habe dies in IPython ausgeführt:

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

Probieren Sie es online!

http://ideone.com/tMjGdh

Wenn Sie den Code ausführen möchten, klicken Sie oben auf den Link Bearbeiten und ändern Sie den Parameter STDIN mit zwei durch ein Leerzeichen getrennten Ganzzahlen. Die erste Ganzzahl ist cund die nächste ist x. Im Moment wird c=3und x=3und das Ergebnis angezeigt.

rayryeng - Setzen Sie Monica wieder ein
quelle
3

Pyth, 53 52 50 Bytes

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

Probieren Sie es online aus.

Wird als Eingabe verwendet, c,xwobei cdie Zielnummer und xdie Basis ist.

PurkkaKoodari
quelle
2

C 175 Bytes

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);}

Um den Code in den Rand einzufügen, habe ich Zeilenumbrüche eingefügt und ein String-Literal darüber geteilt - der Code, der gezählt / kompiliert werden soll, ist

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);}

Funktion fnimmt cund xals Argumente und erzeugt das Ergebnis auf stdout.

Erläuterung

Dies ist eine iterative Lösung, die die durch definierte Linie im Zickzack darstellt a^x + b^x = c^x. Wir beginnen mit a=cund b=1. Das bringt uns offensichtlich auf die falsche Seite, weil c^x + 1 > c^x. Wir dekrementieren, abis wir die Grenze überschreiten. Wenn wir uns unterhalb der Linie befinden, erhöhen bwir uns, bis wir sie in die andere Richtung überqueren. Wiederholen , bis btrifft a, die Erinnerung an die beste Lösung Aund Bwie wir gehen. Dann drucken Sie es aus.

pist eine einfache rekursive Implementierung von a^x(for x>0), da C keinen Operator für die Potenzierung bereitstellt.

Im Pseudocode: 

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

Einschränkungen

c^xmuss darstellbar sein im Bereich von int. Wenn diese Beschränkung zu restriktiv ist, die Unterschrift pkönnte trivially modifiziert long p(long,int)oder double p(double,int)und mund Man longoder doublejeweils ohne Änderung f().

Testprogramm

Dies akzeptiert cund xals Befehlszeilenargumente und gibt das Ergebnis aus.

#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
quelle
1

Haskell, 120 Bytes

Ich glaube, ich habe so viel Golf gespielt, wie ich kann:

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

Ungolfed:

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]

Verwendung:

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

Haskell, 132 128 Bytes

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]

Verwendungsbeispiel: 7 # 3Gibt die Zeichenfolge zurück "6^3 + 5^3 < 7^3".

nimi
quelle
0

Perl 5, 119 Bytes

Ein Unterprogramm:

{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]}

Verwendung als zB:

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

Ruby, 125 Bytes

Anonyme Funktion. Erstellt eine Liste von aWerten, erstellt daraus a,bPaare, ermittelt dann die maximale Anzahl der Werte, die den Kriterien entsprechen, und gibt von dort eine Zeichenfolge zurück.

->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}"}
Wert Tinte
quelle