Fermat Near Misses

31

El último teorema de Fermat dice que no existen soluciones integrales positivas a la ecuación a^n + b^n = c^npara ninguna n>2. Andrew Wiles demostró que esto era cierto en 1994.

Sin embargo, hay muchos "casi errores" que casi satisfacen la ecuación diofantina, pero la pierden por uno. Precisamente, son todos mayores que 1 y son soluciones integrales de a^3 + b^3 = c^3 + 1(la secuencia es el valor de cada lado de la ecuación, en orden creciente).

Su tarea está dada n, imprimir los primeros nvalores de esta secuencia.

Aquí están los primeros valores de la secuencia:

1729, 1092728, 3375001, 15438250, 121287376, 401947273, 3680797185, 6352182209, 7856862273, 12422690497, 73244501505, 145697644729, 179406144001, 648787169394, 938601300672, 985966166178, 1594232306569, 2898516861513, 9635042700640, 10119744747001, 31599452533376, 49108313528001, 50194406979073, 57507986235800, 58515008947768, 65753372717929, 71395901759126, 107741456072705, 194890060205353, 206173690790977, 251072400480057, 404682117722064, 498168062719418, 586607471154432, 588522607645609, 639746322022297, 729729243027001

Este es el , por lo que gana el código más corto en bytes .

Maltysen
fuente
66
oeis.org/A050794
Peter Taylor
1
El primero es en.wikipedia.org/wiki/Taxicab_number de Ramanujan . La secuencia de c, oeis.org/A050791 puede ser útil.
JollyJoker

Respuestas:

14

Jalea , 16 bytes

*3‘
ḊŒc*3S€ċǵ#Ç

Solución de fuerza bruta. Pruébalo en línea!

*3‘           Helper link. Maps r to r³+1.

ḊŒc*3S€ċǵ#Ç  Main link. No arguments.

         µ    Combine the links to the left into a chain.
          #   Read an integer n from STDIN and execute the chain to the left for
              k = 0, 1, 2, ... until n matches were found. Yield the matches.
Ḋ             Dequeue; yield [2, ..., k].
 Œc           Yield all 2-combinations of elements of that range.
   *3         Elevate the integers in each pair to the third power.
     S€       Compute the sum of each pair.
        Ç     Call the helper link, yielding k³+1.
       ċ      Count how many times k³+1 appears in the sums. This yields a truthy 
              (i.e., non-zero) integer if and only if k is a match.
           Ç  Map the helper link over the array of matches.
Dennis
fuente
8

Brachylog , 31 bytes

:{#T#>>:{:3^}aLhH,Lb+.-H,#T=,}y

Pruébalo en línea!

Esta no es una fuerza bruta completa, ya que utiliza restricciones. Esto es un poco lento en TIO (aproximadamente 20 segundos para N = 5). Toma alrededor de 5 segundos N = 5y 13 segundos N = 6en mi máquina.

Explicación

:{                           }y    Return the first Input outputs of that predicate
  #T                               #T is a built-in list of 3 variables
    #>                             #T must contain strictly positive values
      >                            #T must be a strictly decreasing list of integers
       :{:3^}aL                    L is the list of cubes of the integers in #T
              LhH,                 H is the first element of L (the biggest)
                  Lb+.             Output is the sum of the last two elements of L
                     .-H,          Output - 1 = H
                         #T=,      Find values for #T that satisfy those constaints
Fatalizar
fuente
8

Perl, 78 bytes

#!perl -nl
grep$_<(($_+2)**(1/3)|0)**3,map$i**3-$_**3,2..$i++and$_-=print$i**3+1while$_

Enfoque de fuerza bruta. Enrutando el shebang como dos, la entrada se toma de stdin.

Uso de muestra

$ echo 10 | perl fermat-near-miss.pl
1729
1092728
3375001
15438250
121287376
401947273
3680797185
6352182209
7856862273
12422690497

Pruébalo en línea!

primo
fuente
7

Mathematica, 95 bytes

(b=9;While[Length[a=Select[Union@@Array[#^3+#2^3&,{b,b},2],IntegerQ[(#-1)^3^-1]&,#]]<#,b++];a)&

Función sin nombre que toma un único argumento entero positivo #y devuelve una lista de los #enteros deseados . Espaciado para la legibilidad humana:

1  (b = 9; While[
2    Length[ a =
3      Select[
4        Union @@ Array[#^3 + #2^3 &, {b, b}, 2],
5        IntegerQ[(# - 1)^3^-1] &
6      , #]
7    ] < #, b++
8  ]; a) &

La línea 4 calcula todas las sumas posibles de cubos de enteros entre 2 y b+1 (con la inicialización b=9en la línea 1) en orden ordenado. Las líneas 3-5 seleccionan de esas sumas solo aquellas que también son uno más que un cubo perfecto; la línea 6 limita esa lista a la mayoría de los #valores, que se almacenan en a. Pero si esta lista tiene de hecho menos que #valores, el Whilebucle en las líneas 1-7 se incrementa be intenta nuevamente. Finalmente, la línea 8 sale auna vez que tiene la longitud correcta.

¡Santo cielo, esta versión es lenta! Para un byte adicional, podemos cambiar b++en la línea 7 b*=9y hacer que el código realmente se ejecute en un tiempo razonable (de hecho, así es como lo probé).

Greg Martin
fuente
6

Raqueta 166 bytes

(let((c 0)(g(λ(x)(* x x x))))(for*((i(in-naturals))(j(range 1 i))(k(range j i))#:final(= c n))
(when(=(+(g j)(g k))(+ 1(g i)))(displayln(+ 1(g i)))(set! c(+ 1 c)))))

Sin golf:

(define (f n)
  (let ((c 0)
        (g (λ (x) (* x x x))))
    (for* ((i (in-naturals))
           (j (range 1 i))
           (k (range j i))
           #:final (= c n))
      (when (= (+ (g j) (g k))
               (+ 1 (g i)))
        (displayln (+ 1(g i)))
        (set! c (add1 c))))))

Pruebas:

(f 5)

Salida:

1729
1092728
3375001
15438250
121287376
rnso
fuente
5

Pari / GP, 107 bytes

F(n)=c=2;while(n>0,c++;C=c^3+1;a=2;b=c-1;while(a<b,K=a^3+b^3;if(K==C,print(C);n--;break);if(K>C, b--,a++)))

Encuentra las primeras 10 soluciones en 10 segundos.

Objetivo: a ^ 3 + b ^ 3 = c ^ 3 + 1

  1. Obtiene el número de soluciones requeridas por función-argumento n

  2. Aumenta c de 3 y para cada c ^ 3 + 1 busca a y b con 1 <a <= b <c de modo que a ^ 3 + b ^ 3 = c ^ 3 + 1 . Si se encuentra, disminuya el número requerido de almas adicionales n en 1 y repita

  3. Termina, cuando el número de soluciones adicionales requeridas (en n ) es igual a 0

Llámalo para obtener las primeras diez soluciones:

F(10)

Código legible (requiere llaves iniciales y finales como indicadores para la notación de bloque de la función. También, por conveniencia, imprime todas las variables de una solución):

{F(m) = c=2;
   while(m>0,        
     c++;C=c^3+1;             
     a=2;b=c-1;                
     while(a<b,                
           K=a^3+b^3;               
            if(K==C,print([a,b,c,C]);m--;break);
            if(K>C, b--,a++);
          );
    );}

Pari / GP, 93 bytes

(Mejora por Dennis)

F(n)=c=2;while(n,C=c^3+1;a=2;b=c++;while(a<b,if(K=a^3+b^3-C,b-=K>0;a+=K<0,print(C);n--;b=a)))              
Yelmos de Gottfried
fuente
Bienvenido a PPCG! Me tomé la libertad de darle el formato habitual (algunos guiones de usuario y fragmentos de pila dependen de eso). Esto parece ahorrar unos pocos bytes.
Dennis
Ja, Dennis, gracias por el formato. ¡Y la reducción es realmente genial! Nunca he visto esos ajustes específicos ... Lo tomaré en la respuesta como versión.
Gottfried Helms
5

Python 2, 122 119 Bytes

¿Por qué sigues votando? Dennis aplastó esta respuesta;)

Bienvenido a la solución más larga a esta pregunta: / Me las arreglé para eliminar un byte completo creando condiciones más largas y eliminando la mayor sangría posible.

x,y,z=2,3,4
n=input()
while n:
 if y**3+x**3-z**3==1and x<y<z:print z**3+1;n-=1
 x+=1
 if y<x:y+=1;x=2
 if z<y:z+=1;y=3

Salida para n = 5:

1729
1092728
3375001
15438250
121287376
Kade
fuente
4

TI-Basic, 90 bytes

Debe haber un camino más corto ...

Prompt N
2->X
3->Y
4->Z
While N
If 1=X³+Y³-Z³ and X<Y and Y<Z
Then
DS<(N,0
X+1->X
If Y<X
Then
2->X
Y+1->Y
End
If Z<Y
Then
3->Y
Z+1->Z
End
End
Timtech
fuente
2

MATLAB, 94 bytes

Otra solución de fuerza bruta:

for z=4:inf,for y=3:z,for x=2:y,c=z^3+1;if x^3+y^3==c,n=n-1;c,if~n,return,end,end,end,end,end

Salida para n=4:

>> n=4; fermat_near_misses    
c =
        1729
c =
     1092728
c =
     3375001
c =
    15438250

Suprimir la c=parte de la pantalla aumenta el código a 100 bytes

for z=4:inf,for y=3:z,for x=2:y,c=z^3+1;if x^3+y^3==c,n=n-1;disp(c),if~n,return,end,end,end,end,end

>> n=4; fermat_near_misses_cleandisp    
        1729
     1092728
     3375001
    15438250
Rody Oldenhuis
fuente
¿Por qué hay 5 "finales" s? Lo siento, soy terrible en matlab
ev3commander
@ ev3commander es el símbolo de cierre de la declaración de MATLAB, el "paréntesis de cierre"
decirlo
2

C #, 188 174 187 136 bytes

Versión de golf gracias a TheLethalCoder por su gran código de golf y consejos (¡ Pruébelo en línea! ):

n=>{for(long a,b,c=3;n>0;c++)for(a=2;a<c;a++)for(b=a;b<c;b++)if(a*a*a+b‌​*b*b==c*c*c+1)System‌​.Console.WriteLin‌e(‌​c*c*(a=c)+n/n--);};

Tiempo de ejecución para encontrar los primeros 10 números: 33,370842 segundos en mi computadora portátil i7 (la versión original a continuación fue de 9,618127 segundos para la misma tarea).

Versión sin golf:

using System;

public class Program
{
    public static void Main()
    {
        Action<int> action = n =>
        {
            for (long a, b, d, c = 3; n > 0; c++)
                for (a = 2; a < c; a++)
                    for (b = a; b < c; b++)
                        if (a * a * a + b‌ * b * b == c * c * c + 1)
                            System‌.Console.WriteLin‌e( c * c * (a = c) + n / n--);
        };

        //Called like
        action(5);
    }
}

Versión anterior de 187 bytes de golf incluida using System;

using System;static void Main(){for(long a,b,c=3,n=int.Parse(Console.ReadLine());n>0;c++)for(a=2;a<c;a++)for(b=a;b<c;b++)if(a*a*a+b*b*b==c*c*c+1)Console.WriteLin‌​e(c*c*(a=c)+n/n--);}

Versión anterior de 174 bytes con golf (gracias a Peter Taylor):

static void Main(){for(long a,b,c=3,n=int.Parse(Console.ReadLine());n>0;c++)for(a=2;a<c;a++)for(b=a;b<c;b++)if(a*a*a+b*b*b==c*c*c+1)Console.WriteLin‌​e(c*c*(a=c)+n/n--);}

Versión anterior (original) de 188 bytes de golf (¡ Prueba en línea! ):

static void Main(){double a,b,c,d;int t=0,n=Convert.ToInt32(Console.ReadLine());for(c=3;t<n;c++)for(a=2;a<c;a++)for(b=a;b<c;b++){d=(c*c*c)+1;if(a*a*a+b*b*b==d){Console.WriteLine(d);t++;}}}

Tiempo de ejecución para encontrar los primeros 10 números: 9.618127 segundos en mi computadora portátil i7.

Este es mi primer intento en la codificación de C # ... Un poco detallado en comparación con otros lenguajes ...

Mario
fuente
3
1. Puede declarar variables en la primera cláusula del forbucle. 2. int.Parsees más corto que Convert.ToInt32. 3. longes más corto doubley más preciso para esta tarea. 4. tes innecesario: puede realizar una cuenta nregresiva en su 0lugar. 5. Técnicamente, creo que necesita romper dos bucles después de imprimir, en caso de que haya una triple coincidencia.
Peter Taylor
2
No probado:static void Main(){for(long a,b,c=3,n=int.Parse(Console.ReadLine());n>0;c++)for(a=2;a<c;a++)for(b=a;b<c;b++)if(a*a*a+b*b*b==c*c*c+1)Console.WriteLine(c*c*(a=c)+n/n--);}
Peter Taylor
También puede compilar a uno Actionque guardará los bytes utilizados en la firma del método, es decir()=>{/*code here*/};
TheLethalCoder
También necesitaría calificar completamente los nombres o agregarlos using System;al recuento de bytes
TheLethalCoder el
@PeterTaylor ¡Gracias por los buenos consejos! Soy totalmente nuevo en C #
Mario
0

Lenguaje GameMaker, 119 bytes

¿Por qué es show_message()tan largo :(

x=2y=3z=4w=argument0 while n>0{if x*x*x+y*y*y-z*z*z=1&x<y&y<z{show_message(z*z*z+1)n--}x++if y<x{x=2y++}if z<y{y=3z++}}

x, y, z = 2,3,4 n = input () mientras n: si y 3 + x 3-z3 == 1 y x3 + 1; n- = 1 x + = 1 si y

Timtech
fuente
0

Axioma, 246 bytes

h(x:PI):List INT==(r:List INT:=[];i:=0;a:=1;repeat(a:=a+1;b:=1;t:=a^3;repeat(b:=b+1;b>=a=>break;q:=t+b^3;l:=gcd(q-1,223092870);l~=1 and(q-1)rem(l^3)~=0=>0;c:=round((q-1)^(1./3))::INT;if c^3=q-1 then(r:=cons(q,r);i:=i+1;i>=x=>return reverse(r)))))

ungof y resultado

-- hh returns x in 1.. numbers in a INT list [y_1,...y_x] such that 
-- for every y_k exist a,b,c in N with y_k=a^3+b^3=c^3+1 
hh(x:PI):List INT==
   r:List INT:=[]
   i:=0;a:=1
   repeat
      a:=a+1
      b:=1
      t:=a^3
      repeat
          b:=b+1
          b>=a=>break
          q:=t+b^3
          l:=gcd(q-1,223092870);l~=1 and (q-1)rem(l^3)~=0 =>0 -- if l|(q-1)=> l^3|(q-1)
          c:=round((q-1.)^(1./3.))::INT
          if c^3=q-1 then(r:=cons(q,r);i:=i+1;output[i,a,b,c];i>=x=>return reverse(r))

(3) -> h 12
   (3)
   [1729, 1092728, 3375001, 15438250, 121287376, 401947273, 3680797185,
    6352182209, 7856862273, 12422690497, 73244501505, 145697644729]
                                                       Type: List Integer             
RosLuP
fuente