13
\$\begingroup\$

Three positive integers A, B, C are ABC-triple if they are coprime, with A < B and satisfying the relation : A + B = C

Examples :

  • 1, 8, 9 is an ABC-triple since they are coprime, 1 < 8 and 1 + 8 = 9
  • 6, 8, 14 is not because they are not coprime
  • 7, 5, 12 is not because 7 > 5

You can see this Frits Beukers 2005 presentation for more details about ABC-triples.

Input/Output

Three integers, decimal written. May be separated values or list. Output had to be a truthy/falsy value whether the three integers are an ABC-triple.

Note: It is important to respect integers order in the list, for example: 1, 8, 9 is not considered as the same list as 9, 1, 8 or any other combination. So first is an ABC-triple and second is not.

Thus A is the first element of the list, B the second and C the third.

Test cases

Each of the following lists should output a truthy value

[1, 8, 9]
[2, 3, 5]
[2, 6436341, 6436343]
[4, 121, 125]
[121, 48234375, 48234496]

Each of the following lists should output a falsey value

[1, 1, 2]
[1, 2, 5]
[1, 9, 8]
[4, 12872682, 12872686]
[6, 8, 14]
[7, 5, 12]
\$\endgroup\$
  • \$\begingroup\$ Does the output have to be only one of two values, or can we output different truthy/falsy values for different inputs? \$\endgroup\$ – Luis Mendo Jan 3 at 12:04
  • \$\begingroup\$ I think it should be consistent: your code have to output one kind of truthy/falsy values whatever the input. But the truthy/falsy couple can be what you want as far as it does the job: differentiate lists. \$\endgroup\$ – david Jan 3 at 12:33
  • \$\begingroup\$ If we take the input as list of three values, does the input have to be in the order [A,B,C], or are we also allowed to take the input in the order [C,B,A] or [C,A,B]? \$\endgroup\$ – Kevin Cruijssen Jan 3 at 13:06
  • \$\begingroup\$ You have to respect order since A < B is a criteria in the challenge. \$\endgroup\$ – david Jan 3 at 13:08
  • 1
    \$\begingroup\$ I don't think requiring a particular list order is compatible with allowing input to be taken as separate values, as separate values are inherently unordered and may be taken as a list. \$\endgroup\$ – Dennis Jan 3 at 15:30

20 Answers 20

7
\$\begingroup\$

Jelly, 10 9 bytes

Ṫ=S×</=g/

Try it online!

How it works

Ṫ=S×</=g/  Main link. Argument: [a, b, c] (positive integers)

Ṫ          Tail; pop and yield c.
  S        Take the sum of [a, b], yielding (a + b).
 =         Yield t := (c == a + b).
    </     Reduce by less than, yielding (a < b).
   ×       Multiply, yielding t(a < b).
       g/  Reduce by GCD, yielding gcd(a, b).
      =    Check if t(a < b) == gcd(a, b).
\$\endgroup\$
7
\$\begingroup\$

Haskell, 48 38 29 bytes

-10 bytes due to TFeld's gcd trick!

-7 bytes thanks to HPWiz for improving the co-primality test and spotting a superfluous space!

-2 bytes thanks to nimi for suggesting an infix-operator!

(a!b)c=a<b&&a+b==c&&gcd a b<2

Try it online!

Explanation

The first two conditions a < b and a + b == c are fairly obvious, the third one uses that \$\gcd(a,b) = \gcd(a,c) = \gcd(b,c)\$:

Writing \$\gcd(a,c) = U \cdot a + V \cdot c\$ using Bézout's identity and substituting \$c = a + b\$ gives:

$$ U \cdot a + V \cdot (a + b) = (U + V) \cdot a + V \cdot b $$

Since the \$\gcd\$ is the minimal positive solution to that identity it follows that \$\gcd(a,b) = \gcd(a,c)\$. The other case is symmetric.

\$\endgroup\$
  • 1
    \$\begingroup\$ Also, I believe you only need that gcd a b==1. Since gcd a b divides a+b=c. i.e gcd(gcd a b)c=gcd a b \$\endgroup\$ – H.PWiz Jan 3 at 14:01
  • \$\begingroup\$ @HPWiz: Ah yes,of course, thanks! Will edit later when not on mobile.. \$\endgroup\$ – BMO Jan 3 at 14:07
7
\$\begingroup\$

Perl 6, 33 32 bytes

-1 byte thanks to nwellnhof

{(.sum/.[2]/2*[<] $_)==[gcd] $_}

Try it online!

Anonymous code block that takes a list of three numbers and returns True or False.

Explanation

{                              }  # Anonymous code block
                       [gcd] $_   # Is the gcd of all the numbers
 (                  )==           # Equal to
  .sum        # Whether the sum of numbes
      /       # Is equal to
       .[2]/2 # The last element doubled
             *[<] $_   # And elements are in ascending order
\$\endgroup\$
4
\$\begingroup\$

Java 10, 65 64 bytes

(a,b,c)->{var r=a<b&a+b==c;for(;b>0;a=b,b=c)c=a%b;return r&a<2;}

-1 byte thank to @Shaggy.

Try it online.

Explanation:

(a,b,c)->{        // Method with three integer parameters and boolean return-type
  var r=          //  Result-boolean, starting at:
        a<b       //   Check if `a` is smaller than `b`
        &a+b==c;  //   And if `a+b` is equal to `c`
  for(;b>0        //  Then loop as long as `b` is not 0 yet
      ;           //    After every iteration:
       a=b,       //     Set `a` to the current `b`
       b=c)       //     And set `b` to the temp value `c`
    c=a%b;        //   Set the temp value `c` to `a` modulo-`b`
                  //   (we no longer need `c` at this point)
  return r        //  Return if the boolean-result is true
         &a<2;}   //  And `a` is now smaller than 2
\$\endgroup\$
  • \$\begingroup\$ a==1 -> a<2 to save a byte. \$\endgroup\$ – Shaggy Jan 3 at 15:09
  • \$\begingroup\$ @Shaggy Thanks! \$\endgroup\$ – Kevin Cruijssen Jan 3 at 16:23
4
\$\begingroup\$

05AB1E, 12 11 10 bytes

Saved 1 byte thanks to Kevin Cruijssen

ÂÆ_*`\‹*¿Θ

Try it online! or as a Test Suite

Explanation

ÂÆ           # reduce a reversed copy of the input by subtraction
  _          # logically negate
   *         # multiply with input
    `        # push the values of the resulting list separately to stack
     \       # remove the top (last) value
      ‹      # is a < b ?
       *     # multiply by the input list
        ¿    # calculate the gcd of the result
         Θ   # is it true ?
\$\endgroup\$
  • \$\begingroup\$ Oops.. deleted my comment.. >.> So again: you can save a byte by using multiples instead of swaps with product: RÆ_*`\‹*¿Θ Test Suite. \$\endgroup\$ – Kevin Cruijssen Jan 3 at 14:30
  • \$\begingroup\$ @KevinCruijssen: Thanks! Yeah, usually when you have that many swaps, you're doing something wrong :P \$\endgroup\$ – Emigna Jan 3 at 16:45
3
\$\begingroup\$

Excel, 33 bytes

=AND(A1+B1=C1,GCD(A1:C1)=1,A1<B1)
\$\endgroup\$
3
\$\begingroup\$

Python 2, 69 67 63 62 55 bytes

lambda a,b,c:(c-b==a<b)/gcd(a,b)
from fractions import*

Try it online!


Python 3, 58 51 bytes

lambda a,b,c:(c-b==a<b)==gcd(a,b)
from math import*

Try it online!


-7 bytes, thanks to H.PWiz

\$\endgroup\$
  • \$\begingroup\$ is the gcd in gcd trick valid? What if a is not coprime with c? \$\endgroup\$ – Jo King Jan 3 at 12:31
  • 2
    \$\begingroup\$ @jo-king If p divides a and c, it should divide c-a so b. \$\endgroup\$ – david Jan 3 at 12:41
  • 2
    \$\begingroup\$ @JoKing: It is in this case, but not in general (you can prove it via Bezout's identity). \$\endgroup\$ – BMO Jan 3 at 12:42
  • \$\begingroup\$ You can take it one step further and use gcd(a,b), since gcd(a,b) divides a+b \$\endgroup\$ – H.PWiz Jan 3 at 14:04
  • \$\begingroup\$ @H.PWiz Thanks :) \$\endgroup\$ – TFeld Jan 3 at 14:37
3
\$\begingroup\$

Japt, 16 14 13 11 bytes

<V¥yU «NÔr-

Try it

                :Implicit input of integers U=A, V=B & W=C
<V              :Is U less than V?
  ¥             :Test that for equality with
   yU           :The GCD of V & U
      «         :Logical AND with the negation of
       N        :The array of inputs
        Ô       :Reversed
         r-     :Reduced by subtraction
\$\endgroup\$
  • \$\begingroup\$ Here is another 11 byte solution, though on closer inspection it isn't much different from yours in its actual logic. \$\endgroup\$ – Kamil Drakari Jan 3 at 15:13
  • \$\begingroup\$ @KamilDrakari, had a variation on that at one stage, too. It could be 10 bytes if variables were auto-inserted when > follows ©. \$\endgroup\$ – Shaggy Jan 3 at 18:05
3
\$\begingroup\$

JavaScript (ES6),  54 43 42  40 bytes

Thanks to @Shaggy for pointing out that we don't need to compute \$\gcd(a,c)\$. Saved 11 bytes by rewriting the code accordingly.

Takes input as 3 separate integers. Returns \$true\$ for an ABC-triple, or either \$0\$ or \$false\$ otherwise.

f=(a,b,c)=>c&&a/b|a+b-c?0:b?f(b,a%b):a<2

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you need to test gcd(c,a). \$\endgroup\$ – Shaggy Jan 3 at 15:13
  • \$\begingroup\$ @Shaggy Thanks! I've rewritten the code entirely. \$\endgroup\$ – Arnauld Jan 3 at 15:47
2
\$\begingroup\$

bash, 61 bytes

factor $@|grep -vzP '( .+\b).*\n.*\1\b'&&(($1<$2&&$1+$2==$3))

Try it online!

Input as command line arguments, output in the exit code (also produces output on stdout as a side effect, but this can be ignored).

The second part (starting from &&(() is pretty standard, but the interesting bit is the coprime test:

factor $@      # produces output of the form "6: 2 3\n8: 2 2 2\n14: 2 7\n"
|grep -        # regex search on the result
v              # invert the match (return truthy for strings that don't match)
z              # zero-terminated, allowing us to match newlines
P              # perl (extended) regex
'( .+\b)'      # match one or more full factors
'.*\n.*'       # and somewhere on the next line...
'\1\b'         # find the same full factors
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language 24 30 28 bytes

With 2 bytes saved by Doorknob,

#<#2&&CoprimeQ@##&&#+#2==#3&
\$\endgroup\$
  • \$\begingroup\$ I think you should also be able to use CoprimeQ@## to save 2 bytes. \$\endgroup\$ – Doorknob Jan 3 at 16:48
  • \$\begingroup\$ @Doorknob, If the first and second numbers are coprime, are they necessarily coprime with their sum? \$\endgroup\$ – DavidC Jan 3 at 17:27
  • \$\begingroup\$ They are, but the original definition actually states that A, B, and C should be coprime. Most answers check only A and B just because it's usually shorter. \$\endgroup\$ – Doorknob Jan 3 at 17:32
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 59 bytes

(a,b,c)=>Enumerable.Range(2,a).All(i=>a%i+b%i>0)&a<b&a+b==c

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 27 bytes

(+/=2*{:)*({.<1{])*1=+./ .*

Try it online!

Inspired by Jo King's Perl solution

\$\endgroup\$
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), 90 bytes

n=>new int[(int)1e8].Where((_,b)=>n[0]%++b<1&n[1]%b<1).Count()<2&n[0]+n[1]==n[2]&n[0]<n[1]

Runs for numbers up to 1e8, takes about 35 seconds on my machine. Instead of calculating the gcd like others, the function just instantiate a huge array and filter the indexes that aren't divisors of a or b, and check how many elements are left. Next it check if element one plus element two equals element three. Lastly, it checks if the first element is less than the second.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C# (.NET Core), 68 bytes

Without Linq.

(a,b,c)=>{var t=a<b&a+b==c;while(b>0){c=b;b=a%b;a=c;}return t&a<2;};

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Stax, 12 bytes

ü╡v╕7+Pü°╔|g

Run and debug it

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 30 bytes

Saved 2 bytes thanks to @Shaggy.

(a,b,c)->a<b==gcd(a,b)&&a+b==c

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 30 bytes(?) \$\endgroup\$ – Shaggy Jan 3 at 20:13
1
\$\begingroup\$

Befunge-98 (FBBI), 83 bytes

&:&:03p&:04pw>03g04g\:v_1w03g04g+w1.@
00:    7j@.0[^j7      _^;>0.@;j7;>0.@;:%g00\p

Try it online!

The input which is a triple of integers [A,B,C] is feeded into Befunge as space-separated integers C B A.

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

Clean, 43 bytes

import StdEnv
$a b c=a<b&&a+b==c&&gcd a b<2

Try it online!

Similar to basically everything else because the direct test is the same.

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

Retina 0.8.2, 40 bytes

\d+
$*
A`^(11+)+,\1+,
^(1+),(1+\1),\1\2$

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

A`^(11+)+,\1+,

Check that A and B have no common factor.

^(1+),(1+\1),\1\2$

Check that A < B and A + B = C.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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