23
\$\begingroup\$

When learning to factorise quadratics in the form \$x^2 + ax + b\$, a common technique is to find two numbers, \$p, q\$ such that

$$pq = b \\ p + q = a$$

as, for such numbers, \$x^2 + ax + b = (x + p)(x + q)\$

You are to take two integers \$a, b \in (-\infty, +\infty)\$ and output the two integers \$p, q\$ such that

$$pq = b \\ p + q = a$$

You may take input in any convenient method and you may assume that a solution always exists.

This is so the shortest code in bytes wins

Test cases

2, -15 -> 5, -3
-22, 85 -> -5, -17
6, -16 -> -2, 8
-8, -240 -> -20, 12
-1, -272 -> 16, -17
17, 16 -> 1, 16
-4, 0 -> 0, -4
3, -54 -> 9, -6
13, 40 -> 8, 5
-29, 198 -> -11, -18
11, -12 -> -1, 12
4, -320 -> 20, -16
4, 4 -> 2, 2
\$\endgroup\$
2

28 Answers 28

10
\$\begingroup\$

Scala 3, 49 44 bytes

a=>b=>(-b*b to b*b)map(p=>a-p->p)find(_*_==b)

Try it onlne!

Takes (a)(b) and returns an Option[(Int, Int)]. It's now a little more inefficient since it goes from \$-b^2\$ to \$b^2\$ instead of \$-|b|\$ to \$|b|\$, including values that \$p\$ and \$q\$ could never be, but it saves 4 bytes.

a => b =>
  (-b*b to b*b)              //Make a range of all possible q's and then some
    map(q => (a - q, q))     //Make a tuple of (p, q)
    find(_ * _ == b)         //Find a pair such that p * q = b
\$\endgroup\$
3
  • \$\begingroup\$ Why doesn't the range -b*b to b work (I tried it on your link and it failed, but without knowing Scala I'm puzzled what could be wrong...)? \$\endgroup\$ – Dominic van Essen Dec 13 '20 at 17:25
  • \$\begingroup\$ @DominicvanEssen -b*b is guaranteed to be negative, but b could be negative too (Scala doesn't adjust step automatically, it's +1 by default) \$\endgroup\$ – user Dec 13 '20 at 17:31
  • \$\begingroup\$ Ah, of course! Sorry for the stupid question! \$\endgroup\$ – Dominic van Essen Dec 13 '20 at 17:38
9
\$\begingroup\$

JavaScript (ES7),  37 36 34  31 bytes

Saved 3 bytes thanks to @tsh

Expects (a)(b).

a=>b=>[b=a/2+(a*a/4-b)**.5,a-b]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 31 bytes: a=>b=>[p=a/2+(a*a/4-b)**.5,a-p] \$\endgroup\$ – tsh Dec 13 '20 at 7:30
  • \$\begingroup\$ @tsh Simpler is better. :-) Thank you. \$\endgroup\$ – Arnauld Dec 13 '20 at 19:58
9
\$\begingroup\$

Wolfram Language (Mathematica), 23 21 18 bytes

Solve[x x+#2==x#]&

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The output format’s a little convoluted, but it looks like you can remove the x/. \$\endgroup\$ – caird coinheringaahing Dec 13 '20 at 7:06
  • \$\begingroup\$ In addition, since you can take the input in any convenient format, why not choose the input format [x^2-a x+b] instead of [a,b]? \$\endgroup\$ – Greg Martin Dec 13 '20 at 20:51
  • 4
    \$\begingroup\$ @GregMartin That's a bit too finicky for my liking. \$\endgroup\$ – att Dec 13 '20 at 20:54
  • \$\begingroup\$ I get that for sure ... it seems that people here say "any convenient format" but then are put off by formats like that ... would be nice to have it clarified (for that matter, the same issue for output already came up in earlier comments on this answer!) \$\endgroup\$ – Greg Martin Dec 13 '20 at 23:36
  • \$\begingroup\$ @GregMartin FWIW, I wouldn't consider it valid either; it's like saying "input is in format <full program>" and the solution is just eval. Note that "convenient format" is precisely specified as per the link... \$\endgroup\$ – ASCII-only Dec 14 '20 at 11:22
7
\$\begingroup\$

Jelly, 5 bytes

1ṭÆrN

Try it online!

Input as a list [b, a].

1ṭ       Append 1 to the input, (resulting in [b, a, 1])
  Ær     find roots of polynomial from little-endian coefficient list,
    N    negate each root.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Mine was the same, but with ;1 at the start instead \$\endgroup\$ – caird coinheringaahing Dec 12 '20 at 23:40
  • \$\begingroup\$ why 1 instead of 0? \$\endgroup\$ – Mad Physicist Dec 14 '20 at 15:02
  • \$\begingroup\$ @MadPhysicist The 1 is the coefficient of the \$x^2\$ term--if it was 0, I'd be left with just a linear function. \$\endgroup\$ – Unrelated String Dec 14 '20 at 18:34
  • 1
    \$\begingroup\$ OIC. I misread/didn't think it through \$\endgroup\$ – Mad Physicist Dec 14 '20 at 18:38
6
\$\begingroup\$

Retina 0.8.2, 94 bytes

\d+
$*
^(-?)(1*)(,(-)(?<2>\2(1(1)*))|(?<5>(?<6>1)*),)(?<-6>\2)*$(?(6)1)
$1$.2,$4$1$.5
--

-0
0

Try it online! Link includes test cases. Explanation: \$|p|\$ is captured in $2 and \$|q|\$ is captured in $5, with $6 being a helper balancing group used to verify the multiplication.

\d+
$*

Convert to unary.

^(-?)(1*)

Start by matching the sign of \$a\$, then initially assume \$|p|\$ is no greater than \$|a|\$.

(,(-)(?<2>\2(1(1)*))

If \$b\$ is negative, then we actually end up matching \$|a|\$, and choose \$|q|\$ and overwrite $2 with \$|p|=|a|+|q|\$, so \$|a|=|p|+|q|\operatorname{sgn}(b)\$.

|(?<5>(?<6>1)*),)

Otherwise \$b\$ is positive, so overwrite $5 with \$|q|\$ such that \$|a|=|p|+|q|\operatorname{sgn}(b)\$.

(?<-6>\2)*$(?(6)1)

Ensure \$|b|=|pq|\$.

$1$.2,$4$1$.5

Output \$p = |p|\operatorname{sgn}(a)\$ and \$q = |q|\operatorname{sgn}(ab)\$. We then have \$p+q=|p|\operatorname{sgn}(a)+|q|\operatorname{sgn}(ab)=(|p|+|q|\operatorname{sgn}(b))\operatorname{sgn}(a)=|a|\operatorname{sgn}(a)=a\$ while \$pq=|p|\operatorname{sgn}(a)|q|\operatorname{sgn}(ab)=|pq|\operatorname{sgn}(b)=|b|\operatorname{sgn}(b)=b\$ as desired (where \$\operatorname{sgn}(0)=1\$).

--

-0
0

Fix up extraneous -s.

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

Charcoal, 25 bytes

NθNηI⊟ΦE…·±↔η↔η⟦ι⁻θι⟧⁼ηΠι

Try it online! Link is to verbose version of code. Same idea as @user's Scala solution. Explanation:

NθNη

Input \$a\$ and \$b\$.

E…·±↔η↔η

Loop \$p\$ over \$[-|b|,|b|]\$.

⟦ι⁻θι⟧

For each \$p\$ create a list \$(p,q)\$ where \$q=a-p\$.

I⊟Φ...⁼ηΠι

Output the one with the highest \$p\$ where \$pq=b\$.

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

Octave, 17 bytes

@(x)-roots([1 x])

Try it online!

You simply need to solve \$x^2 + ax + b = (x + p)(x + q) = 0\$, and \$x_1=-p\$, \$x_2=-q\$.

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

Python 3.8, 42 39 37 bytes

Saved 2 bytes thanks to Danis!!!

lambda a,b:[c:=a/2+(a*a/4-b)**.5,a-c]

Try it online!

Port of Arnauld's JavaScript answer.

\$\endgroup\$
2
  • \$\begingroup\$ you can save two bytes by removing the parentheses 37 bytes \$\endgroup\$ – Danis Dec 13 '20 at 20:42
  • \$\begingroup\$ @Danis Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Dec 13 '20 at 23:22
5
\$\begingroup\$

05AB1E, 17 16 bytes

(Dn4I*-t‚DOsÆ);(

Try it online!

Why oh why aren't there any built-ins for this? This solves the quadratic equation to get the two roots. -1 thanks to @ovs

\$\endgroup\$
3
  • \$\begingroup\$ D(sn can be (Dn or (¹n for -1 byte. \$\endgroup\$ – ovs Dec 13 '20 at 9:41
  • 4
    \$\begingroup\$ Wow, there is a winking sad face at the end. \$\endgroup\$ – SunnyMoon Dec 13 '20 at 9:51
  • \$\begingroup\$ Alternative 17-byter. Maybe someone sees a way to golf it further. If outputting an infinite list of pairs is valid (which contains a single pair most likely), I guess it could be 16 bytes. \$\endgroup\$ – Kevin Cruijssen Dec 14 '20 at 8:47
4
\$\begingroup\$

Brachylog, 8 bytes

~+ʰ⟨≜×⟩Ċ

Try it online!

Takes input as a list [a,b].

  ʰ         For the first element of the input,
~+          get a list of integers which sum to it
    ≜       (in order of least absolute value of the first element).
   ⟨ ×⟩     Its product is the second element,
       Ċ    its length is 2,
            and it's the output.

I'm not entirely sure why this needs , but it comes at no cost because the "sandwich" construct ⟨~+×⟩ won't parse without braces around ~+ anyhow (and both ⟨{~+}×⟩Ċ and ~+ʰ⟨≡×⟩Ċ would still come out to 8).

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes 24 bytes

thanks to att

#&@@Solve[#-b==a==#2/b]&

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 24 bytes \$\endgroup\$ – att Dec 13 '20 at 1:39
4
\$\begingroup\$

dc, 24 bytes

Input is a line of two numbers from STDIN. Output is to STDOUT.

?rdsad*r4*-vla+2/dlar-rf

Try it online!

Explanation

?                        # Read a line of input
 r                       # Swap the two numbers
  dsa                    # Store to `a` w/o popping
     d*                  # Square the 1st input
       r                 # Swap up the second input
        4*               # Multiply by four
          -              # Second-to-top - TOS
           v             # Square root
            la+          # Add by `a`
               2/        # Halve
                 d       # Duplicate
                  lar-   # Push `a` - TOS
                      r  # Swap the top 2 items
                       f # Print entire stack
\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 37 bytes

lambda a,b:[p:=a/2+(a*a/4-b)**.5,a-p]

Try it online!

Python 2, 42 bytes

def f(a,b):p=a/2+(a*a/4-b)**.5;print p,a-p

Try it online!

Takes input as float, and prints the output.

\$\endgroup\$
4
\$\begingroup\$

Husk, 12 bytes

ḟo=¹ΠmSe`-²ṡ

Try it online!

Port of user's Scala answer.

           ṡ    # range of integers from -arg1 to +arg1
     m          # map over each of them
      S         # combining itself
       e        # into a 2-element list with
        `-²     # arg2 minus this;
ḟ               # now find the first element that satisfies
 o              # combine 2 functions:
    Π           # product
  =¹            # equals arg1
\$\endgroup\$
4
\$\begingroup\$

R, 36 35 bytes

function(b,c)b/2+-.5:1*(b^2-4*c)^.5

Try it online!

Uses the Quadratic formula with a=1.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ polyroot(c(b,a,1)) seems shorter. \$\endgroup\$ – Xi'an Dec 14 '20 at 10:32
  • 1
    \$\begingroup\$ @Xi'an - Really nice! Thanks for introducing me to polyroot and you should post this as your own answer! You can shorten it even more by taking input as a 2-element vector, too: try it... \$\endgroup\$ – Dominic van Essen Dec 14 '20 at 10:58
  • 2
    \$\begingroup\$ @Xi'an i don't think it's acceptable, since you still have to specify a=1 \$\endgroup\$ – ASCII-only Dec 14 '20 at 11:34
  • 1
    \$\begingroup\$ @Xi'an - I agree with ASCII-only. You need to be able to 'call' or run your answer using only the input specified in the question. \$\endgroup\$ – Dominic van Essen Dec 14 '20 at 12:31
  • 1
    \$\begingroup\$ R 4.1 (r-devel) would allow lambda syntax \(x) polyroot(c(1,x)) \$\endgroup\$ – AlexR Dec 15 '20 at 21:42
4
\$\begingroup\$

C (gcc) -lm, 45 bytes

f(int*a){*a-=a[1]=(*a+sqrt(*a**a-4*a[1]))/2;}

Try it online!

Modifies an input array of 2 ints.


C (gcc), 53 bytes

i;f(int*a){for(i=*a/2;(*a-i)*i-a[1];i--);*a-=a[1]=i;}

Try it online!

Doesn't use sqrt.

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 28 26 bytes

-2 thanks to Razetime.

{⍺-⎕←(⍺÷2)+.5*⍨⍵-⍨⍺×⍺÷4}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ -2 \$\endgroup\$ – Razetime Dec 14 '20 at 7:35
3
\$\begingroup\$

APL (Dyalog Extended), 19 bytes

-2 thanks to @Bubbler

÷∘2⍛{⍺(+,-)√⍵-⍨⍺*2}

Try it online!

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

Haskell, 46 39 bytes

a!b=[(k,b-k)|k<-[-a*a..],k*b-k*k==a]!!0

Try it online!

Kind of boring, but short.

\$\endgroup\$
3
  • \$\begingroup\$ a!b=[(x,b-x)|x<-[-aa..aa],x*(b-x)==a]!!0 is shorter \$\endgroup\$ – user100177 Jan 3 at 20:41
  • \$\begingroup\$ @user100177 a!b=[(k,b-k)|k<-[-a*a..],k*b-k*k==a]!!0 is even shorter. \$\endgroup\$ – Wheat Wizard Jan 4 at 0:09
  • \$\begingroup\$ Good find, I didn't think about an infinite list. It's just as short as mine now, actually. \$\endgroup\$ – user100177 Jan 7 at 15:16
2
\$\begingroup\$

Julia 1.0, 34 bytes

(a,b)->(d=(a*a-4b)^.5;[a+d,a-d]/2)

Try it online!

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

MathGolf, 13 bytes

_½\²¼k-√+`-αÞ

I/O as floats.

Port of @Arnauld's JavaScript answer.

Try it online.

I have the feeling this can be a byte shorter with some smart stack manipulations, but I've been unable to find anything yet. An equal-bytes alternative could be ²¼k-√`;½+`-αÞ.

Explanation:

_             # Duplicate the first (implicit) input-float
 ½            # Halve it
  \           # Swap so the first input is at the top of the stack again
   ²          # Square it
    ¼         # Divide it by 4
     k-       # Subtract the second input-float
       √      # Take the square-root of that
        +     # Add it to the halved first input that's still on the stack
         `    # Duplicate the top two values (since the stack only contains a single
              # item, this will first add the first input-float implicitly as leading
              # item, and then duplicate both items)
          -   # Subtract the top two items from one another
           α  # Pair the top two items
            Þ # Only leave the top item of the stack, and discard everything else
              # (after which the entire stack is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 41 37 35 bytes

A port of Arnauld's answer in Ruby!

->a,b{[b=a/2r+(a*a/4r-b)**0.5,a-b]}

Try it online!

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

05AB1E, 10 9 bytes

D(Ÿʒ-y*¹Q

Try it online!

Takes input as

b
a

In case \$p=q\$ it returns only a single value. In case that's not allowed, it's +5 bytes for appending }Ðgi«

Explanation:

D              duplicate
)              negate
Ÿ              range, so [-b,.. , b]
ʒ              filter
 -             minus the implicit a
  y            the current number
   *           multiply
    ¹          the first item from the input history - b
     Q         is equals
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 3 bytes

∆QN

Try it Online!

Solve for the roots and then negate

\$\endgroup\$
2
+50
\$\begingroup\$

Whispers v2, 110 92 bytes

Edit: -18 bytes (within less than 2 minutes of submission!) thanks to caird coinheringaahing and the ± operator

> Input
> Input
> 2
> 4
>> 1*3
>> 2⋅4
>> 5-6
>> √7
>> 8÷3
>> 1÷3
>> 10±9
>> Output 11

Try it online!

My first Whispers program.
Uses the Quadratic formula with a=1.

\$\endgroup\$
2
  • \$\begingroup\$ 92 bytes \$\endgroup\$ – caird coinheringaahing Feb 7 at 23:07
  • \$\begingroup\$ @cairdcoinheringaahing - Thanks! I should have guessed that ± would exist. That must be a contender for one of the fastest upgolfs yet... \$\endgroup\$ – Dominic van Essen Feb 7 at 23:12
2
\$\begingroup\$

convey, 113 bytes

v<1
>>>v 0
{?>*"-"v
4*  "vvv
 v  >*vv
v#<<<<vv
-<    vv
*%2   v>v
.1    v}>v
v     v%2v}%2
">>>>>-^>+>^
>>>>>>>>^

Try it online!

Ungolfed, mostly. Uses quadratic formula.

enter image description here

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

Pari/GP, 33 bytes

f(a,b)=round(polroots(x^2+a*x+b))

Try it online!

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

Haskell, 39 bytes

f a b=let c=a/2+(a*a/4-b)**0.5in[c,a-c]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Some simple improvements bring it down to 33: a!b|c<-a/2+(a*a/4-b)**0.5=[c,a-c] \$\endgroup\$ – Wheat Wizard Jan 7 at 23:29

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.