The Margin is too Narrow

Question

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.

---

Leaderboards

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

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N characters

Alternatively, you can start with:

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

Answer 1

Pyth, 38 bytes

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

Takes input in this format:

x
c

Answer 2

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

Answer 3

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]

Answer 4

CJam, 51 46 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.

Answer 5

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

Or try it online in Octave.

Thanks to @flawr for removing one byte.

Answer 6

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.

Answer 7

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

Answer 8

Python 2, 182 161 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.

Answer 9

Pyth, 53 52 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.

Answer 10

Pyth, 60 bytes

Input is given as c,k

=k^ReQUKhQLfghTeT^tb2jd.i+R+\^eQa@yUKxJsMykh.M?>Z^KeQ0ZJK"+<

Try it Online

Answer 11

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

Answer 12

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"

Answer 13

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

Answer 14

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)

Answer 15

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