# Solve quadratic equations when 1+1=0

There already have been multiple challenges about carryless multiplication, this challenge will work with the same calculation rules.

You task is given a quadratic polynomial ax²+bx+c, to find an integer r such that a*r*r+b*r+c is zero, with + meaning exclusive or and * being carryless multiplication (use xor to add up the numbers in binary long multiplication).

Input: Polynomial ax²+bx+c for instance given as an coefficient vector

Goal: find a number r such that a*r*r+b*r+c=0 with * being multiplication without carry and + being exclusive or.

Rules:

• You may assume there is an integral solution
• You only need to return a single solution of the equation
• The returned solution may be different if the program is called multiple times
• This is the shortest solution (per language) wins

Examples:

x²+x         -> x=0 or x=1
x²+3x+2      -> x=1 or x=2
x²+5         -> x=3
x²+7x+12     -> x=3 or x=4
5x²+116x+209 -> x=25
x²+12x+45    -> x=5 or x=9
• Suggested test case with a>1: 5x²+116x+209 -> x=25 Commented Jul 28, 2023 at 16:19
• I'm from a math background, and is this not equivalent to factoring in F2 after a reduction map? Commented Jul 29, 2023 at 0:48
• math.stackexchange.com/questions/877682/… @bsoelch, a reduction map is basically the concept of "taking mod 2" Commented Jul 29, 2023 at 8:52
• @user118161 It seems like taking everything "mod 2" preserves the solutions, but considering that the reduction maps different polynomials to the same value (e.g. (x+2)(x+2) and ) I doubt it is an equivalence. Note that the "numbers" in this problem are just a shorthand notation for polynomials in F2[y] (2 means y not 1+1) Commented Jul 29, 2023 at 9:43

# 05AB1E, 30 28 bytes

àÝʒUεXN.DNFV0sbv·yY*^}}}.«^_

Takes a reversed polynomial triplet as input (if this is not allowed, a single R can be added between the ).

Explanation:

0sbv·yY*^} is taken from my answer for one of the resulted challenges.

à               # Push the maximum of the (implicit) input-list
Ý              # Pop and push a list in the range [1,max]
ʒ             # Filter this list by:
U            #  Pop and store the current value in variable X
ε            #  Map over the (implicit) input-list of the reversed polynomial
#   (implicitly push the current polynomial integer of the map)
XN.D        #   Push the 0-based map-index amount of copies of value X
NF          #   Loop the 0-based map-index amount of times:
V         #    Pop and store the current top value in variable Y
0         #    Push a 0
s        #    Swap so the next value is at the top of the stack
b       #    Convert it to a binary-string
v      #    Pop and loop over each of its bits y:
·     #     Double the current value
y    #     Push the current bit y
Y*  #     Multiply it to value Y
^ #     Bitwise-XOR the two together
}      #    Close the foreach-loop
}          #   Close the ranged loop
}            #  Close the map
.«          #  Reduce the list by:
^         #   Bitwise-XOR
_        #  Check if the final result is 0
# (after which the filtered list is output implicitly as result)

import Data.Bits
a%b=xor a b
0!_=0
a!b=(2*div a 2!b)%(mod a 2*b)

Try it online!

• Welcome to Code Golf, and nice answer! Commented Jul 29, 2023 at 19:19
• I don't know Haskell but I think you might be able to write (a!x!x)%(b!x)%c as a!x%b!x%c which would save you 7 bytes.
– Neil
Commented Jul 30, 2023 at 7:13
• @Neil I don't think so. a!x isn't equal to a!x!x, and it needs the parentheses. But now I'm thinking x!(a!x%b)%c would work and save 4 bytes. Commented Jul 30, 2023 at 7:42
• But x!(...) equals (...)!x, and then I think you can remove the ()s, giving my original expression.
– Neil
Commented Jul 30, 2023 at 7:46
• (Also I've obviously miscounted and it's only a total of 6 bytes saved.)
– Neil
Commented Jul 30, 2023 at 7:47

# PARI/GP, 90 bytes

a->[subst(lift(t-x),y,2)|t<-factor(Pol([Pol(Mod(binary(i),2),y)|i<-a]))[,1],deriv(t,x)==1]

Attempt This Online!

Coverts the input to a polynomial in $$\\mathbb{F}_2[y][x]\$$, and then factors it to find the roots.

# Python3, 338 bytes:

E=enumerate
def C(a,b):
d={}
for x,A in E(a[::-1]):
for y,B in E(b[::-1]):
if'11'==A+B:d[x+y]=int(d.get(x+y,0)==0)
return''.join(str(d.get(i,0))for i in range(0,max(d or[0])+1))[::-1]
def f(p):
r=0;A,B=bin(p[0])[2:],bin(p[1])[2:]
while 1:
if p[2]==int(''.join(C(C(A,J:=bin(r)[2:]),J)),2)^int(''.join(C(B,J)),2):return r
r+=1

Try it online!

# Charcoal, 57 bytes

Ｆ³⊞υ⌕Ａ⮌⍘Ｎ²1Ｗ⊙Ｅ⟦⌕Ａ⮌⍘ⅈ²1⟧⁺§υ²∧κΣＥκ⁺μ⁺§υ¹ΣＥκ⁺ξ§υ⁰⊙κ﹪№κμ²Ｍ→Ｉⅈ

Attempt This Online! Link is to verbose version of code. Explanation:

Ｆ³⊞υ⌕Ａ⮌⍘Ｎ²1

Read in the three coefficients, then decompose them as a sum of powers of 2.

⌕Ａ⮌⍘ⅈ²1

Decomposing the trial result as a sum of powers of 2, ...

Ｅ⟦...⟧⁺§υ²∧κΣＥκ⁺μ⁺§υ¹ΣＥκ⁺ξ§υ⁰

... compose the decomposed values together by matrix sum, then flatten and join the matrices together, ...

Ｗ⊙...⊙κ﹪№κμ²

... and while any power of two appears an odd number of times, ...

Ｍ→

... increment the trial result.

Ｉⅈ

Output the final result.

By representing an integer as a list of powers of 2, the sum of integers is equivalent to the concatenation of the lists with duplicates removed, while the product of integers is equivalent to the Cartesian product of the lists, where each entry is reduced by sum, and then duplicates removed (note that in both cases triplicates become single entries). However it's not actually necessary to remove the duplicates, merely to check that there would be no left over entries.

I don't know whether there's a mathematical or computing term for creating an N-dimensional matrix where each entry is the sum of the relevant entries of N vectors, but numpy.add.outer performs the equivalent operation when N=2.

# JavaScript (ES6), 63 bytes

-3 bytes thanks to @Neil

(a,b,c)=>(g=r=>(m=n=>n&&n%2*r^2*m(n>>1))(m(a)^b)^c?g(r+1):r)(0)

Try it online!

### Commented

(a, b, c) =>  // input triplet (a, b, c)
( g = r => (  // g is a recursive function taking r
m = n =>    // m is a recursive function taking n and
// computing the carryless multiplication n * r
n &&        //   stop if n = 0
n % 2 * r ^ //   otherwise XOR the LSB of n multiplied by r
2 *         //   with twice the result of
m(n >> 1)   //   a recursive call with floor(n / 2)
)(m(a) ^ b)   // compute ((a * r) XOR b) * r
^ c           // XOR it with c
?             // if the result is not 0:
g(r + 1)    //   try again with r + 1
:             // else:
r           //   stop and return r
)(0)          // initial call to g with r = 0
• m(m(a))^m(b)^c can be written m(m(a)^b)^c to save 3 bytes.
– Neil
Commented Jul 30, 2023 at 7:09

# Ruby, 68 65 bytes

Utilizes the multiplication function from Arnauld's JavaScript answer. -3 bytes from @Neil.

->a,b,c{(0..).find{|x|m=->a{a>0?a%2*x^2*m[a/2]:0}
m[m[a]^b]^c<1}}

Attempt This Online!

• m[m[a]]^m[b]^c can be written m[m[a]^b]^c to save 3 bytes.
– Neil
Commented Jul 30, 2023 at 7:10