# The Margin is too Narrow

Around the year 1637, Pierre de Fermat wrote in the margins of his copy of the 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.


Unfortunately for us, the margin is still too narrow to contain the proof. Today, we are going to write into the margins a simple program that confirms the proof for arbitrary inputs.

# The Challenge

We want a program for function that given a power, separates it into two pairs of two powers that are as close to the power as possible. We want the program that does this to be as small as possible so it can fit into the margins.

# Input

The power and the power number: c, x

Constraints: c > 2 and x > 2

Input can be through program arguments, function arguments, or from the user.

# Output

This exact string: "a^x + b^x < c^x" with a, b, c, and x replaced with their literal integer values. a and b must be chosen so that a^x + b^x < c^x and no other values of a or b would make it closer to c^x. Also: a>=b>0

Output can be through function return value, stdout, saved to a file, or displayed on screen.

Examples:

> 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


Due to Fermat's average writing skills, unprintable characters are not allowed. The program with the least number of characters wins.

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

## Language Name, N characters


## Language Name, N bytes


where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

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


If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

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


You can also make the language name a link which will then show up in the leaderboard snippet:

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


var QUESTION_ID=57363,OVERRIDE_USER=32700;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• I think it should be a>=b>0 or your first example would be invalid. And why do we have to display < when you want it to be <=? Sep 8, 2015 at 22:57
• @flawr Fixed :) Sep 8, 2015 at 23:19
• Would it be ok to take the arguments in the opposite order? First x, then c? Sep 9, 2015 at 2:55
• @RetoKoradi Sure :) Sep 9, 2015 at 2:55

# Pyth, 38 bytes

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


Takes input in this format:

x
c


# Matlab, 169 153 bytes

The score can be +-1 depending on the unsolved problems in the comments=) The score stays the same. This is just a bruteforce search for the best (a,b) pair.

Pretty disappointing: I first tried experimented with some 'fancy' stuff and then realized two simple nested for loops are way shorter...

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)


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

• Remove the spaces in m = 0? Still, that won't get you close to my answer :-PP Sep 9, 2015 at 9:27
• Also, it looks like you could remove q= from the function definition Sep 9, 2015 at 9:33
• I don't see the q variable being used anywhere. You can shave off a couple of bytes by simply doing function f(c,x) and removing the semi-colon as well. Sep 9, 2015 at 15:29

# Mathematica, 79 95 80 bytes

This just might fit on the 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]


Testing

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


# CJam, 5146 43 bytes

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


This full program reads the power, then the base from STDIN.

Try it online in the CJam interpreter.

## Matlab, 141 140 bytes

This is coded as function that displays the result in 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])


Example use:

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


Thanks to @flawr for removing one byte.

• I always avoided sprintf because it seemed so complicated while actually it really isn't! And I forgot about bsxfun once again, so thats a very elegant solution. I especially like the way you abused the single/double indexing in the last argument=) (You could remove a space there too!) Sep 9, 2015 at 10:06
• Thanks! I usually use disp too, except in Code Golf :-P Sep 9, 2015 at 10:14
• If you use fprintf instead of sprintf, it doesn't display "ans" Sep 9, 2015 at 12:10
• @Jonas But it prints the result and then the prompt >> in the same line, which is a bit strange Sep 9, 2015 at 12:13
• You can use fprintf, but you'd have to insert a manual carriage return. Sep 9, 2015 at 16:42

# CJam, 53 51 bytes

l~:C\:X#:U;C2m*{Xf#:+_U<*}$W=~"^"X+:T" + "@T" < "CT  Try it online The input format is x c, which is the reverse of the order used in the examples. Explanation: 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.


# R, 139 characters

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)})  # Python 2, 182161 157 bytes I usually answer in MATLAB, but because there are already two solutions in that language, I'd figure I'd try another language :) 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 with explanations 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])  # Example Runs I ran this in 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  # Try it online! http://ideone.com/tMjGdh If you want to run the code, click on the edit link near the top, then modify the STDIN parameter with two integers separated by a space. The first integer is c and the next one is x. Right now, c=3 and x=3 and its result is currently displayed. # Pyth, 5352 50 bytes Ls^ReQbs[j" + "+R+\^eQ_Sh.MyZf<yT^FQ^UhQ2" < "j\^Q  Try it online. Takes as input c,x where c is the target number and x is the base. # Pyth, 60 bytes Input is given as c,k =k^ReQUKhQLfghTeT^tb2jd.i+R+\^eQa@yUKxJsMykh.M?>Z^KeQ0ZJK"+<  Try it Online # 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);}  To fit the code into the margin, I've inserted newlines and split a string literal above - the golfed code to be counted/compiled is 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);}  Function f takes c and x as arguments, and produces the result on stdout. ### Explanation This is an iterative solution that zigzags the line defined by a^x + b^x = c^x. We start with a=c and b=1. Obviously, that puts us on the wrong side of the line, because c^x + 1 > c^x. We decrement a until we cross the line. When we're below the line, we increment b until we cross it in the other direction. Repeat until b meets a, remembering the best solution in A and B as we go. Then print it. p is a simple recursive implementation of a^x (for x>0) since C provides no operator for exponentiation. In 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  ### Limitations c^x must be representable within the range of int. If that limitation is too restrictive, the signature of p could be trivially modified to long p(long,int) or double p(double,int), and m and M to long or double respectively, without any modification to f(). ### Test program This accepts c and x as command-line arguments, and prints the result. #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; }  # Haskell, 120 bytes I think I've golfed this as much as I can: 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]  Usage: Prelude> 30 % 11 "28^30 + 28^30 < 30^30"  # 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]


Usage example: 7 # 3 returns the string "6^3 + 5^3 < 7^3".

# Perl 5, 119 bytes

A subroutine:

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


Use as e.g.:

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


# Ruby, 125 bytes

Anonymous function. Builds a list of a values, uses it to construct a,b pairs, then finds the max for the ones that fit the criteria and returns a string from there.

->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}"}