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

23 Answers 23

8
\$\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\$ – ბიმო Jan 3 at 14:07
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\$

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

Excel, 33 bytes

=AND(A1+B1=C1,GCD(A1:C1)=1,A1<B1)
\$\endgroup\$
4
\$\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\$
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\$

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\$ – ბიმო 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
3
\$\begingroup\$

Wolfram Language 24 30 28 26 bytes

With 2 bytes shaved by Doorknob. A further 2 bytes shaved off by @jaeyong sung

#<#2&&GCD@##==1&&#+#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
  • \$\begingroup\$ I think GCD@##==1 would save 2 bytes \$\endgroup\$ – jaeyong sung Feb 6 at 14:24
2
\$\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\$
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\$
2
\$\begingroup\$

ECMAScript Regex, 34 bytes

Input is in unary, in the domain ^x*,x*,x*$ (repeated xs delimited by ,).

^(?!(xx+)\1*,\1+,)(x*)(,\2x+)\3\2$

Try it online! (.NET regex engine)
Try it online! (SpiderMonkey regex engine)

# see https://codegolf.stackexchange.com/questions/178303/find-if-a-list-is-an-abc-triple
^
(?!                # Verify that A and B are coprime. We don't need to include C in the
                   # test, because the requirement that A+B=C implies that A,B,C are
                   # mutually comprime if and only if A and B are coprime.
    (xx+)\1*,\1+,  # If this matches, A and B have a common factor \1 and aren't coprime.
)
(x*)(,\2x+)\3\2$   # Verify that A<B and A+B=C. The first comma is captured in \3 and
                   # reused to match the second comma, saving one byte.

The question does say "Three integers, decimal written", so this might not qualify (as it takes input in unary), but it makes for such an elegant pure regex that I hope it will at least be appreciated.

However, note that if the phrasing is to be literally interpreted, lambda and function submissions that take integer arguments are to be disqualified too, as to strictly adhere to the question's specification they would need to take the input in the form of a string.

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

J, 27 bytes

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

Try it online!

Inspired by Jo King's Perl solution

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

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\$
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\$
1
\$\begingroup\$

Mathematica 35 bytes

CoprimeQ @@ # && #[[1]] + #[[2]] == #[[3]] & 

if order is important:

CoprimeQ @@ # && Sort[#]==# && #[[1]] + #[[2]] == #[[3]] & 

or...

And[CoprimeQ @@ #, Sort@# == #, #[[1]] + #[[2]] == #[[3]]] &
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 42 41 bytes

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

Try it online! Link includes test cases. Edit: Saved 1 byte thanks to @Deadcode. Explanation:

\d+
$*

Convert to unary.

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

Check that A and B have no common factor.

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ There appears to be a bug in your program. [121, 48234375, 48234496] is returning false. \$\endgroup\$ – Deadcode Jan 22 at 13:44
  • 1
    \$\begingroup\$ @Deadcode Fixed, thanks for letting me know. \$\endgroup\$ – Neil Jan 22 at 18:07
  • \$\begingroup\$ As with my regex, you can drop 1 byte by changing ^(1+),(1+\1),\1\2$ to ^(1+)(,1+\1)\2\1$. \$\endgroup\$ – Deadcode Jan 22 at 18:14
  • 1
    \$\begingroup\$ @Deadcode Thanks! It's a shame that my use of Retina's A operation doesn't actually save me any bytes. \$\endgroup\$ – Neil Jan 22 at 18:54
  • 1
    \$\begingroup\$ @Deadcode I'm using Retina's behaviour of turning the last regex into a positive assertion (actually a (count of) match stage) so moving the antigrep would cost me 5 bytes. \$\endgroup\$ – Neil Jan 24 at 10:50
1
\$\begingroup\$

Common Lisp, 51 bytes

(lambda(a b c)(and(< a b)(=(+ a b)c)(=(gcd a c)1)))

Try it online!

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