15
\$\begingroup\$

It's a well-known fact that Fermat's Last Theorem is true. More specifically, that for any integer \$n \gt 2\$, there are no three integers \$a, b, c\$ such that

$$a^n + b^n = c^n$$

However, there are a number of near misses. For example,

$$6^3 + 8^3 = 9^3 - 1$$

We'll call a triple of integers \$(a, b, c)\$ a "Fermat near-miss" if they satisfy

$$a^n + b^n = c^n \pm 1$$

for some integer \$n > 2\$. Note that this includes negative values for \$a, b, c\$, so \$(-1, 0, 0)\$ is an example of such a triple for any \$n\$.


Your task is to take an integer \$n > 2\$ as input, in any convenient method. You may then choose which of the following to do:

  • Take a positive integer \$m\$ and output the \$m\$-th Fermat near-miss for that specific \$n\$
  • Take a positive integer \$m\$ and output the first \$m\$ Fermat near-misses for that specific \$n\$
    • For either of these two, you may choose any ordering to define the "\$m\$th" or "first \$m\$" terms, so long as the ordering eventually includes all possible triples. For example, the test case generator program below orders them lexographically.
  • Output all Fermat near-misses for that specific \$n\$
    • The output may be in any order, so long as it can be shown that all such triples will eventually be included. The output does not have to be unique, so repeated triples are allowed.
    • You may output in any format that allows for infinite output, such as an infinite list or just infinite output. You may choose the delimiters both in each triple and between each triple, so long as they are distinct and non-digital.

This is so the shortest code in bytes wins


This program was helpfully provided by Razetime which outputs all solutions with \$|a|, |b|, |c| \le 50\$ for a given input \$n\$*.

This is a question asked over on MathOverflow about the existence of non-trivial solutions to

$$a^n + b^n = c^n \pm 1$$

Unfortunately, it appears (although is not proven, so you may not rely on this fact) that no non-trivial solutions exist for \$n \ge 4\$, so for most \$n\$, your output should be the same.

*Currently, this also returns exact matches, which your program shouldn’t do.

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – caird coinheringaahing Dec 17 '20 at 21:50
  • 13
    \$\begingroup\$ It's a well-known fact that Fermat's Last Theorem is true All theorems are true, otherwise they would not be theorems :-P \$\endgroup\$ – Luis Mendo Dec 17 '20 at 22:11
  • 9
    \$\begingroup\$ @LuisMendo Normally, I'd agree with you, but FLT is rather special, in that it's been referred to as a "theorem" long before Wiles' proof, so it just happens to be an edge case :P \$\endgroup\$ – caird coinheringaahing Dec 17 '20 at 22:13
  • 1
    \$\begingroup\$ I know, I know... :-) \$\endgroup\$ – Luis Mendo Dec 17 '20 at 22:16
  • \$\begingroup\$ Do you mean \$n \gt 2\$ not \$n \ge 2\$ \$\endgroup\$ – pxeger Dec 18 '20 at 9:09
5
\$\begingroup\$

R, 119 110 108 105 100 bytes

Edit: -2 bytes thanks to Giuseppe

n=scan();repeat for(b in -(F=-F+!(F>0)):F)for(i in (d=-(c=F^n+b^n):c)[abs(d^n-c)==1])cat(F,b,i,'\n')

Try it online!

Prints the infinite list of near-misses, without duplicates (this includes duplicates by re-ordering a and b, so the triples (a,b,c) and (b,a,c) are considered duplicates: add an extra ,b,F,i,'\n' (11 bytes) to print the list with duplicates).
Wastes a few bytes avoiding taking nth-roots, to prevent floating-point errors.

How?

function(n){
                            # note: F (false), which represents variable a, is initialized to zero;
repeat{                     # repeat for ever:
 for(b in -F:F){            # try all possible values of b from -a to a,
  c=F^n+b^n                 # calculate c as a^n+b^n,
  c=(-c:c)                  # now find value in the range -c to c
  [(-c:c)^n%in%(c+c(1,-1))] # that gives either c+1 or c-1 when raised to the n-th power
                            # replace c with this value (if there is one),
  for(i in c)               # now, if there were any:
   print(c(F,b,i))}         # print out the a,b,c combination
 F=-F+!(F>0)}}              # update F to the next value of variable a, in the sequence:
                            # 0, 1, -1, 2, -2, 3, -3 ... and so on
\$\endgroup\$
  • \$\begingroup\$ 106 \$\endgroup\$ – Giuseppe Dec 18 '20 at 17:06
  • \$\begingroup\$ @Giuseppe - Thanks (belatedly - my browser's stopped letting me add comments, so I have to wait to use a different computer...) \$\endgroup\$ – Dominic van Essen Dec 19 '20 at 23:47
4
\$\begingroup\$

Stax, 20 bytes

ÜTCÑ ¢@∙╡·Gò╝╠Δh÷╠╧m

Run and debug it

This uses the fact that results need not be unique.

As with most of caird's challenges, you get brownie points for finding/outgolfing my 16 byte Husk solution :P

Explanation

Wi:r3:${{x#mNs|+:-2<f|uP
W                        iterate forever
 i                       push current iteration index
  :r                     symmetric range (-n..n)
    3:$                  cartesian power of 3
       {            f    filter each triple by the following:
        {x#m             map each number to the power of input
            Ns           push the last element separately
              |+         sum the first two
                :-       absolute difference
                  1=     equals 1?
                     |u  stringify the result
                       P print with newline
\$\endgroup\$
  • 1
    \$\begingroup\$ Arnauld pointed out a bug in your Husk solution, that it returns exact solutions as well as near-misses, which it looks like this answer does as well. Changing 2< to 1= should fix it \$\endgroup\$ – caird coinheringaahing Dec 18 '20 at 10:33
  • \$\begingroup\$ cool, thanks a lot \$\endgroup\$ – Razetime Dec 18 '20 at 10:39
  • \$\begingroup\$ @cairdcoinheringaahing Isn't that fix unnecessary if \$n\$ is guaranteed to be above \$2\$? \$\endgroup\$ – Jonathan Allan Dec 18 '20 at 12:30
  • 1
    \$\begingroup\$ @JonathanAllan I don’t think so, as \$(0,0,0)\$ is an exact solution for all \$n\$, (in fact \$(a,0,a)\$ for any \$a\$ is an exact solution) \$\endgroup\$ – caird coinheringaahing Dec 18 '20 at 14:32
  • \$\begingroup\$ @cairdcoinheringaahing Ah, yes. \$\endgroup\$ – Jonathan Allan Dec 18 '20 at 19:03
3
\$\begingroup\$

JavaScript (ES7), 124 bytes

Expects (n)(m) and returns the \$m\$-th solution (1-indexed).

n=>(a=b=c=1,g=m=>(t=[A,B,C]=[a=a<c+2?a+1:b<c+2?++b/b:b=++c/c,b,c].map(v=>(v>>1)*(v&1||-1)),A**n+B**n-C**n)**2-1||--m?g(m):t)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 15 13 bytes

∞εD(Ÿ3ãʒIm`+α

Looks for \$\left\vert a^n+b^n−c^n\right\vert = 1\$ (near-misses).
Inspired by @Razetime's Stax answer. The program outputs an infinite list of lists of triplets in the order \$[c,b,a]\$ (including duplicated triplets) with only \$n\$ as input.

Try it online.

Explanation:

∞             # Push an infinite list of positive integers: [1,2,3,...]
 ε            # Map each integer y to:
  D(          #  Duplicate it, and negate the copy: -y
    Ÿ         #  Pop both, and push a list in that range: [y,...,-y]
     3ã       #  Create triplets of this list with the cartesian power
       ʒ      #  Filter this list of [c,b,a]-triplets by:
        Im    #   Take each value to the power of the input n: [c^n,b^n,a^n]
          `   #   Pop the list, and push the three values separated to the stack
           +  #   Add the top two together: b^n+a^n
            α #   Take the absolute difference: |c^n-a^n+b^n|
              #   (NOTE: only 1 is truthy in 05AB1E)
              # (after which the infinite list of lists of triplets is output implicitly)
\$\endgroup\$
  • 1
    \$\begingroup\$ The sample program is slightly buggy, as pointed out in the comments by Arnauld. You should just return near-misses, not exact solutions, so you can remove the trailing ! \$\endgroup\$ – caird coinheringaahing Dec 18 '20 at 10:24
  • \$\begingroup\$ @cairdcoinheringaahing Thanks for the heads up. :) \$\endgroup\$ – Kevin Cruijssen Dec 18 '20 at 10:31

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.