31
\$\begingroup\$

Fermat's last theorem says that there there are no positive, integral solutions to the equation a^n + b^n = c^n for any n>2. This was proven to be true by Andrew Wiles in 1994.

However, there are many "near misses" that almost satisfy the diophantine equation but miss it by one. Precisely, they are all the greater than 1 and are integral solutions of a^3 + b^3 = c^3 + 1 (the sequence is the value of each side of the equation, in increasing order).

Your task is given n, to print out the first n values of this sequence.

Here are the first few values of the sequence:

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

This is , so shortest code in bytes wins!

\$\endgroup\$

13 Answers 13

14
\$\begingroup\$

Jelly, 16 bytes

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

Brute-force solution. Try it 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.
\$\endgroup\$
8
\$\begingroup\$

Brachylog, 31 bytes

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

Try it online!

This is not complete brute force as this uses constraints. This is a bit slow on TIO (about 20 seconds for N = 5). Takes about 5 seconds for N = 5 and 13 seconds for N = 6 on my machine.

Explanation

:{                           }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
\$\endgroup\$
8
\$\begingroup\$

Perl, 78 bytes

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

Brute force approach. Couting the shebang as two, input is taken from stdin.

Sample Usage

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

Try it online!

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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)))              
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Dec 12 '16 at 21:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Gottfried Helms Dec 12 '16 at 23:14
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Why are there 5 "end"s? Sorry I'm terrible at matlab \$\endgroup\$ – ev3commander Dec 12 '16 at 23:28
  • \$\begingroup\$ @ev3commander it's MATLAB's statement closing symbol, the "closing parenthesis" if you will \$\endgroup\$ – Rody Oldenhuis Dec 13 '16 at 2:15
2
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Dec 13 '16 at 16:08
  • 2
    \$\begingroup\$ 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--);} \$\endgroup\$ – Peter Taylor Dec 13 '16 at 16:16
  • \$\begingroup\$ You can also compile to an Action which will save the bytes used in the method signature i.e. ()=>{/*code here*/}; \$\endgroup\$ – TheLethalCoder Dec 13 '16 at 17:14
  • \$\begingroup\$ You would also need to fully qualify names or add using System; into the byte count \$\endgroup\$ – TheLethalCoder Dec 13 '16 at 17:16
  • \$\begingroup\$ @PeterTaylor Thanks for the great tips! I'm totally new to C# \$\endgroup\$ – Mario Dec 14 '16 at 10:48
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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             
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.