A margem é muito estreita

30

Por volta do ano de 1637, Pierre de Fermat escreveu nas margens de sua cópia da Aritmética: 

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.

Infelizmente para nós, a margem ainda é muito estreita para conter a prova. Hoje, escreveremos nas margens um programa simples que confirma a prova de entradas arbitrárias.

O desafio

Queremos um programa para a função que recebe um poder, o separa em dois pares de dois poderes o mais próximo possível do poder. Queremos que o programa que faz isso seja o menor possível, para que ele caiba nas margens.

Entrada

O poder e o número de potência: c,x

Restrições: c > 2ex > 2

A entrada pode ser por meio de argumentos do programa, argumentos da função ou do usuário.

Saída

Essa seqüência exata: " a^x + b^x < c^x" com a, b, c, e xsubstituídas por seus valores inteiros literais. ae bdeve ser escolhido para que a^x + b^x < c^xnenhum outro valor aou bo aproxime c^x. Além disso:a>=b>0

A saída pode ser por meio do valor de retorno da função, stdout, salvo em um arquivo ou exibido na tela.

Exemplos:

> 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

Devido às habilidades médias de escrita de Fermat, caracteres não imprimíveis não são permitidos. O programa com o menor número de caracteres vence.

Classificação

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N characters

Como alternativa, você pode começar com:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

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

Você também pode transformar o nome do idioma em um link que será exibido no snippet do placar de líderes:

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

Mostrar snippet de código

code-golf number O número um
fonte
1
Eu acho que deveria ser a>=b>0ou o seu primeiro exemplo seria inválido. E por que precisamos mostrar <quando você quer que seja <=?
flawr
@flawr Fixed :)
TheNumberOne
Seria bom aceitar os argumentos na ordem oposta? Primeiro xentão c?
Reto Koradi 9/09/15
@RetoKoradi Sure :)
TheNumberOne

Respostas:

9

Pitão, 38 bytes

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

Recebe entrada neste formato:

x
c
orlp
fonte
8

Matlab, 169 153 bytes

A pontuação pode ser + -1, dependendo dos problemas não resolvidos nos comentários =) A pontuação permanece a mesma. Esta é apenas uma pesquisa bruteforce para o melhor (a,b)par.

Bastante decepcionante: eu tentei experimentar algumas coisas 'sofisticadas' e depois percebi que dois aninhamentos simples para loops são bem mais curtos ...

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)

Versão antiga:

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
fonte
Remover os espaços m = 0? Ainda assim, isso não vai te aproximar da minha resposta: -PP
Luis Mendo
Além disso, parece que você poderia remover q=a partir da definição de função
Luis Mendo
Não vejo a qvariável sendo usada em nenhum lugar. Você pode economizar alguns bytes simplesmente fazendo function f(c,x)e removendo o ponto-e-vírgula também.
rayryeng - Restabelece Monica
8

Mathematica, 79 95 80 bytes

Isso pode caber na margem.

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

Teste

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

saída

DavidC
fonte
7

CJam, 51 46 43 bytes

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

Este programa completo lê o poder, depois a base do STDIN.

Experimente online no intérprete CJam .

Dennis
fonte
6

Matlab, 141 140 bytes

Isso é codificado como função que exibe o resultado em 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])

Exemplo de uso:

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

Ou experimente online no Octave .

Obrigado a @flawr por remover um byte.

Luis Mendo
fonte
Eu sempre evitei sprintfporque parecia tão complicado enquanto na verdade não é! E eu esqueci mais bsxfunuma vez, então essa é uma solução muito elegante. Eu gosto especialmente do jeito que você abusou da dupla indexação single / no último argumento =) (Você pode remover um espaço lá também)!
flawr
Obrigado! Eu também costumo usar disp, exceto no Code Golf :-P
Luis Mendo
Se você usar em fprintfvez de sprintf, ele não exibirá "ans"
Jonas #
@ Jonas Mas ele imprime o resultado e, em seguida, o prompt >>na mesma linha, que é um pouco estranho
Luis Mendo
Você pode usar fprintf, mas teria que inserir um retorno de carro manual.
rayryeng - Restabelece Monica
5

CJam, 53 51 bytes

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

Experimente online

O formato de entrada é x c, que é o inverso da ordem usada nos exemplos.

Explicação:

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

R, 139 caracteres

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)})
modelo
fonte
4

Python 2, 182 161 157 bytes

Normalmente, respondo no MATLAB, mas como já existem duas soluções nesse idioma, acho que tentaria outro idioma :)

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]

Código ungolfed com explicações

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

Execuções de exemplo

Eu executei isso no 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

Experimente online!

http://ideone.com/tMjGdh

Se você deseja executar o código, clique no link editar próximo ao topo e modifique o parâmetro STDIN com dois números inteiros separados por um espaço. O primeiro número inteiro é ce o próximo é x. No momento, c=3e x=3seu resultado é exibido no momento.

rayryeng - Restabelecer Monica
fonte
3

Pitão, 53 52 50 bytes

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

Experimente online.

Toma como entrada c,xonde cestá o número de destino e xé a base.

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

Para ajustar o código à margem, inseri novas linhas e dividi uma string literal acima - o código golfado a ser contado / compilado é

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

A função fpega ce xcomo argumentos e produz o resultado em stdout.

Explicação

Esta é uma solução iterativa que ziguezagueia a linha definida por a^x + b^x = c^x. Começamos com a=ce b=1. Obviamente, isso nos coloca no lado errado da linha, porque c^x + 1 > c^x. Diminuímos aaté cruzar a linha. Quando estamos abaixo da linha, aumentamos baté cruzá-la na outra direção. Repita até bencontrar a, lembrando a melhor solução Ae à Bmedida que avançamos. Depois imprima.

p é uma implementação recursiva simples de a^x (for x>0), pois C não fornece operador para exponenciação.

No pseudo-código: 

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

Limitações

c^xdeve ser representável dentro do intervalo de int. Se essa limitação for muito restritiva, a assinatura de ppoderia ser modificada trivialmente para long p(long,int)ou double p(double,int), e me Mpara longou doublerespectivamente, sem nenhuma modificação emf() .

Programa de teste

Isso aceita ce xcomo argumentos de linha de comando e imprime o resultado.

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

Haskell, 120 bytes

Acho que joguei isso o máximo que posso:

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]

Uso:

Prelude> 30 % 11
"28^30 + 28^30 < 30^30"
CR Drost
fonte
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]

Exemplo de uso: 7 # 3retorna a string "6^3 + 5^3 < 7^3".

nimi
fonte
0

Perl 5, 119 bytes

Uma sub-rotina:

{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 como por exemplo:

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

Ruby, 125 bytes

Função anônima. Constrói uma lista de avalores, usa-a para construir a,bpares, depois encontra o máximo para os que se encaixam nos critérios e retorna uma sequência a partir daí.

->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}"}
Value Ink
fonte