Fermat Near Misses

31

Ostatnie twierdzenie Fermata mówi, że nie ma pozytywnych, integralnych rozwiązań równania a^n + b^n = c^ndla żadnegon>2 . To udowodnił Andrew Wiles w 1994 roku.

Istnieje jednak wiele „bliskich nieudanych prób”, które prawie spełniają równanie diofantyczne, ale pomijają je o jedno. Dokładnie, wszystkie są większe niż 1 i są integralnymi rozwiązaniami a^3 + b^3 = c^3 + 1(sekwencja jest wartością każdej strony równania, w porządku rosnącym).

Zadanie polega nna wydrukowaniu pierwszych nwartości z tej sekwencji.

Oto kilka pierwszych wartości sekwencji:

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

To jest , więc wygrywa najkrótszy kod w bajtach !

Maltysen
źródło
6
oeis.org/A050794
Peter Taylor
1
Pierwszym jest en.wikipedia.org/wiki/Taxicab_number Ramanujana . Pomocna może być sekwencja c, oeis.org/A050791 .
JollyJoker,

Odpowiedzi:

14

Galaretka , 16 bajtów

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

Rozwiązanie siłowe. Wypróbuj online!

*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
źródło
8

Brachylog , 31 bajtów

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

Wypróbuj online!

To nie jest pełna brutalna siła, ponieważ wykorzystuje ograniczenia. Jest to trochę wolne w przypadku TIO (około 20 sekund N = 5). Na mojej maszynie trwa około 5 sekund N = 5i 13 sekund N = 6.

Wyjaśnienie

:{                           }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
Fatalizować
źródło
8

Perl, 78 bajtów

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

Podejście brutalnej siły. Couting shebang jako dwa, dane wejściowe są pobierane ze standardowego wejścia.

Przykładowe użycie

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

Wypróbuj online!

primo
źródło
7

Mathematica, 95 bytes

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

Unnamed function taking a single positive integer argument # and returning a list of the desired # integers. Spaced for human readability:

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

Line 4 calculates all possible sums of cubes of integers between 2 and b+1 (with the initialization b=9 in line 1) in sorted order. Lines 3-5 select from those sums only those that are also one more than a perfect cube; line 6 limits that list to at most # values, which are stored in a. But if this list has in fact fewer than # values, the While loop in lines 1-7 increments b and tries again. Finally, line 8 outputs a once it's the right length.

Holy hell this version is slow! For one extra byte, we can change b++ in line 7 to b*=9 and make the code actually run in reasonable time (indeed, that's how I tested it).

Greg Martin
źródło
6

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

Ungolfed:

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

Testing:

(f 5)

Output:

1729
1092728
3375001
15438250
121287376
rnso
źródło
6

Python 2, 102 98 bytes

def f(n,c=2):z=c**3+1;t=z in[(k/c)**3+(k%c)**3for k in range(c*c)];return[z]*n and[z]*t+f(n-t,c+1)

Try it online!

Dennis
źródło
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++)))

Finds the first 10 solutions in 10 sec.

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

  1. Gets number of required solutions by function-argument n

  2. Increases c from 3 and for each c^3+1 searches a and b with 1 < a <= b < c such that a^3+b^3=c^3+1 . If found, decrease required number of further soulutions n by 1 and repeat

  3. Finishes, when number of furtherly required solutions (in n) equals 0

Call it to get the first ten solutions:

F(10)

Readable code (requires leading and trailing braces as indicators for block-notation of the function. Also for convenience prints all variables of a solution):

{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

(Improvement by 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)))              
Gottfried Helms
źródło
Welcome to PPCG! I took the liberty of giving you answer the usual format (some userscripts and Stack Snippets rely on that). This seems to save a few bytes.
Dennis
Hah, Dennis, thank you for the formatting. And the reduction is really cool! I've never seen that specific tweaks... I'll take it into the answer as version.
Gottfried Helms
5

Python 2, 122 119 Bytes

why are you still upvoting? Dennis crushed this answer ;)

Welcome to the longest solution to this question :/ I managed to shave off a whole byte by making longer conditions and removing as much indentation as possible.

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

Output for n = 5:

1729
1092728
3375001
15438250
121287376
Kade
źródło
4

TI-Basic, 90 bytes

There must be a shorter way...

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
źródło
2

MATLAB, 94 bytes

Another brute-force solution:

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

Output for n=4:

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

Suppressing the c= part of the display increases the code to 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
źródło
Why are there 5 "end"s? Sorry I'm terrible at matlab
ev3commander
@ev3commander it's MATLAB's statement closing symbol, the "closing parenthesis" if you will
Rody Oldenhuis
2

C#, 188 174 187 136 bytes

Golfed version thanks to TheLethalCoder for his great code golfing and tips (Try online!):

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

Execution time to find the first 10 numbers: 33,370842 seconds on my i7 laptop (original version below was 9,618127 seconds for the same task).

Ungolfed version:

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

Previous golfed 187 bytes version including 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--);}

Previous golfed 174 bytes version (thanks to 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--);}

Previous (original) golfed 188 bytes version (Try online!):

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

Execution time to find the first 10 numbers: 9,618127 seconds on my i7 laptop.

This is my first ever attempt in C# coding... A bit verbose compared to other languages...

Mario
źródło
3
1. You can declare variables in the first clause of the for loop. 2. int.Parse is shorter than Convert.ToInt32. 3. long is shorter than double and more accurate for this task. 4. t is unnecessary: you can count n down to 0 instead. 5. Technically I think you need to break two loops after printing, in case there's a triple coincidence.
Peter Taylor
2
Untested: 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
You can also compile to an Action which will save the bytes used in the method signature i.e. ()=>{/*code here*/};
TheLethalCoder
You would also need to fully qualify names or add using System; into the byte count
TheLethalCoder
@PeterTaylor Thanks for the great tips! I'm totally new to C#
Mario
0

GameMaker Language, 119 bytes

Why is show_message() so long :(

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() while n: if y3+x3-z3==1and x3+1;n-=1 x+=1 if y

Timtech
źródło
0

Axiom, 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 and result

-- 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
źródło