Marginnya terlalu sempit

30

Sekitar tahun 1637, Pierre de Fermat menulis di tepi salinan Arithmetica-nya: 

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.

Sayangnya bagi kami, margin masih terlalu sempit untuk memuat buktinya. Hari ini, kita akan menulis ke dalam margin sebuah program sederhana yang mengkonfirmasi bukti untuk input sewenang-wenang.

Tantangan

Kami menginginkan program untuk fungsi yang memberikan daya, pisahkan menjadi dua pasang dua kekuatan yang sedekat mungkin dengan kekuatan. Kami ingin program yang melakukan ini sekecil mungkin sehingga dapat masuk ke dalam margin.

Memasukkan

Kekuatan dan jumlah tenaga: c,x

Kendala: c > 2danx > 2

Input dapat melalui argumen program, argumen fungsi, atau dari pengguna.

Keluaran

String sebenarnya ini: " a^x + b^x < c^x" dengan a, b, c, dan xdiganti dengan nilai-nilai integer literal mereka. adan bharus dipilih sehingga a^x + b^x < c^xdan tidak ada nilai lain aatau bakan membuatnya lebih dekat c^x. Juga:a>=b>0

Output dapat melalui nilai pengembalian fungsi, stdout, disimpan ke file, atau ditampilkan di layar.

Contoh:

> 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

Karena kemampuan menulis rata-rata Fermat, karakter yang tidak patut tidak diizinkan. Program dengan jumlah karakter paling sedikit menang.

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N characters

Atau, Anda dapat mulai dengan:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

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

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

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

Anda juga dapat membuat tautan nama bahasa yang kemudian akan muncul di cuplikan papan peringkat:

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

Tampilkan cuplikan kode

code-golf number TheNumberOne
sumber
1
Saya pikir itu harus a>=b>0atau contoh pertama Anda tidak valid. Dan mengapa kita harus ditampilkan <ketika Anda menginginkannya <=?
flawr
@ flawr Tetap :)
TheNumberOne
Apakah boleh untuk mengambil argumen dalam urutan yang berlawanan? Pertama x, lalu c?
Reto Koradi
@RetoKoradi Sure :)
TheNumberOne

Jawaban:

9

Pyth, 38 byte

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

Mengambil input dalam format ini:

x
c
orlp
sumber
8

Matlab, 169 153 byte

Skor bisa + -1 tergantung pada masalah yang tidak terpecahkan di komentar =) Skor tetap sama. Ini hanya pencarian bruteforce untuk (a,b)pasangan terbaik .

Cukup mengecewakan: Saya pertama kali mencoba bereksperimen dengan beberapa hal 'mewah' dan kemudian menyadari dua bersarang sederhana untuk loop jauh lebih pendek ...

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)

Versi lama:

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])
cacat
sumber
Hapus spasi di m = 0? Namun, itu tidak akan membuat Anda dekat dengan jawaban saya: -PP
Luis Mendo
Juga, sepertinya Anda dapat menghapus q=dari definisi fungsi
Luis Mendo
Saya tidak melihat qvariabel yang digunakan di mana pun. Anda dapat mencukur beberapa byte hanya dengan melakukan function f(c,x)dan menghapus titik koma juga.
rayryeng
8

Mathematica, 79 95 80 byte

Ini mungkin cocok dengan margin.

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

Pengujian

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

output

DavidC
sumber
7

CJam, 51 46 43 byte

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

Program lengkap ini membaca daya, lalu basis dari STDIN.

Cobalah online di juru bahasa CJam .

Dennis
sumber
6

Matlab, 141 140 byte

Ini dikodekan sebagai fungsi yang menampilkan hasilnya di 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])

Contoh penggunaan:

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

Atau coba online di Octave .

Terima kasih kepada @ flawr karena menghapus satu byte.

Luis Mendo
sumber
Saya selalu menghindari sprintfkarena sepertinya sangat rumit padahal sebenarnya tidak! Dan saya lupa bsxfunsekali lagi, jadi itu solusi yang sangat elegan. Saya terutama menyukai cara Anda menyalahgunakan pengindeksan tunggal / ganda dalam argumen terakhir =) (Anda juga dapat menghapus ruang di sana!)
flawr
Terima kasih! Saya biasanya menggunakan dispjuga, kecuali dalam Code Golf :-P
Luis Mendo
Jika Anda menggunakan fprintfalih-alih sprintf, itu tidak menampilkan "ans"
Jonas
@Jonas Tapi itu mencetak hasilnya dan kemudian prompt >>di baris yang sama, yang agak aneh
Luis Mendo
Anda dapat menggunakan fprintf, tetapi Anda harus memasukkan carriage return manual.
rayryeng
5

CJam, 53 51 byte

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

Cobalah online

Format input adalah x c, yang merupakan kebalikan dari urutan yang digunakan dalam contoh.

Penjelasan:

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

R, 139 karakter

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

Python 2, 182 161 157 byte

Saya biasanya menjawab dalam MATLAB, tetapi karena sudah ada dua solusi dalam bahasa itu, saya pikir saya akan mencoba bahasa lain :)

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]

Kode tidak dikunci dengan penjelasan

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

Contoh Berjalan

Saya menjalankan ini di 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

Cobalah online!

http://ideone.com/tMjGdh

Jika Anda ingin menjalankan kode, klik tautan edit di dekat bagian atas, lalu ubah parameter STDIN dengan dua bilangan bulat yang dipisahkan oleh spasi. Bilangan bulat pertama adalah cdan yang berikutnya adalah x. Saat ini, c=3dan x=3hasilnya ditampilkan saat ini.

rayryeng - Reinstate Monica
sumber
3

Pyth, 53 52 50 byte

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

Cobalah online.

Dibawa sebagai input di c,xmana cnomor target dan xbasis.

PurkkaKoodari
sumber
2

C, 175 byte

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

Untuk memasukkan kode ke margin, saya telah memasukkan baris baru dan membagi string literal di atas - kode golf yang akan dihitung / dikompilasi adalah

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

Fungsi fmengambil cdan xsebagai argumen, dan menghasilkan hasilnyastdout .

Penjelasan

Ini adalah solusi berulang yang zig-zag pada baris yang didefinisikan oleh a^x + b^x = c^x. Kita mulai dengan a=cdan b=1. Jelas, itu menempatkan kita di sisi yang salah dari garis itu, karena c^x + 1 > c^x. Kami mengurangi asampai kami melewati batas. Ketika kita berada di bawah garis, kita menambah bsampai kita melewatinya ke arah lain. Ulangi sampai bbertemu a, mengingat solusi terbaik di Adan Bsaat kita pergi. Kemudian cetak.

p adalah implementasi rekursif sederhana dari a^x (untuk x>0) karena C tidak memberikan operator untuk eksponensial.

Dalam 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

Keterbatasan

c^xharus dapat diwakili dalam kisaran int. Jika batasan itu terlalu ketat, tanda tangan dari pdapat secara sepele dimodifikasi menjadi long p(long,int)atau double p(double,int), dan mdan Muntuk masing long- doublemasing, tanpa modifikasi apa pun untukf() .

Program uji

Ini menerima cdan xsebagai argumen baris perintah, dan mencetak hasilnya.

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

Haskell, 120 byte

Saya pikir saya telah bermain golf ini sebanyak yang saya bisa:

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

Tidak Disatukan:

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]

Pemakaian:

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

Haskell, 132 128 byte

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]

Contoh penggunaan: 7 # 3mengembalikan string "6^3 + 5^3 < 7^3".

nimi
sumber
0

Perl 5, 119 byte

Subrutin:

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

Gunakan sebagai contoh:

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

Ruby, 125 byte

Fungsi anonim. Buat daftar anilai, gunakan untuk membuat a,bpasangan, lalu temukan maks untuk yang cocok dengan kriteria dan kembalikan string dari sana.

->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}"}
Nilai Tinta
sumber