Project: Factorization#
In this project, we will factorize linear and quadratic expressions. First, we will write a function to find the greatest common divisor of two integers. For each linear and quadratic expression, we will write two functions:
To represent the expressions in a mathematical form using the coefficients.
To perform the factorization
Greatest Common Divisor#
Greatest common divisor (gcd) of two number is the largest number in absolute value that divides both numbers.
For the purpose of the factorization the sign of the gcd is the sign of the first number.
The absolute value of the GCD cannot be larger than either of the given two numbers.
gcd(0,0) = 0
gcd(m,0) = m
gcd(0,m) = m
def gcd(m, n):
if (m==0) & (n==0): # gcd(0,0) = 0
return 0
else:
mp, np = abs(m), abs(n) # absolute value of m and n
result = 1
for i in range(1, min(mp,np)+1):
if (mp%i==0) & (np%i==0): # common divisor
result = i
if m < 0: # gcd is negative if m is negative
result *= -1
return result
print(f'gcd( 0, 0) = {gcd(0,0)}')
print(f'gcd( 5, 0) = {gcd(5,0)}')
print(f'gcd( 0, 5) = {gcd(0,5)}')
print(f'gcd( 12,16) = {gcd(12,16)}')
print(f'gcd(-12,16) = {gcd(-12,16)}')
print(f'gcd( 3, 5) = {gcd(3,5)}')
print(f'gcd( -3, 5) = {gcd(-3,5)}')
gcd( 0, 0) = 0
gcd( 5, 0) = 1
gcd( 0, 5) = 1
gcd( 12,16) = 4
gcd(-12,16) = -4
gcd( 3, 5) = 1
gcd( -3, 5) = -1
Linear Expressions#
Linear expressions are in the form \(ax+b\).
Examples: \(2x+3, -5x+7\)
Display#
We will write a function that takes two parameters: the coefficients of the expression and returns a string.
The first parameter is the coefficient of the \(x\) term, and the second parameter is the constant term.
The parameters \(a\) and \(b\) represent the expression \(ax+b\).
Exclude the zero terms, such as \(0x\) and \(0\), from the expressions.
Represent
\(1x\) as \(x\).
\(0x+0\) as \(0\).
\(ax+0\) as \(ax\).
\(0x+b\) as \(b\).
def display_lin(a, b):
if (a==0) & (b==0): return '0'
if (a!=0) & (b==0): return f'{a}x'
if (a==0) & (b!=0): return f'{b}'
if b > 0: ps = '+' # add + sign for +b part of ax+b
else: ps = ''
if a == 1: return f'x{ps}{b}' # represent 1x as x
if a == -1: return f'-x{ps}{b}' # represent -1x as -x
return f'{a}x{ps}{b}'
print(f'a = 0 and b = 0 => 0x+0 => {display_lin(0, 0)}')
print(f'a = 5 and b = 0 => 5x+0 => {display_lin(5, 0)}')
print(f'a = -5 and b = 0 => -5x+0 => {display_lin(-5, 0)}')
print(f'a = 0 and b = 5 => 0x+5 => {display_lin(0, 5)}')
print(f'a = 0 and b = -5 => 0x-5 => {display_lin(0, -5)}')
print(f'a = 5 and b = 6 => 5x+6 => {display_lin(5, 6)}')
print(f'a = -5 and b = 6 => -5x+6 => {display_lin(-5, 6)}')
print(f'a = -5 and b = -6 => -5x-6 => {display_lin(-5, -6)}')
print(f'a = 1 and b = 2 => 1x+2 => {display_lin(1, 2)}')
print(f'a = -1 and b = 2 => -1x+2 => {display_lin(-1, 2)}')
a = 0 and b = 0 => 0x+0 => 0
a = 5 and b = 0 => 5x+0 => 5x
a = -5 and b = 0 => -5x+0 => -5x
a = 0 and b = 5 => 0x+5 => 5
a = 0 and b = -5 => 0x-5 => -5
a = 5 and b = 6 => 5x+6 => 5x+6
a = -5 and b = 6 => -5x+6 => -5x+6
a = -5 and b = -6 => -5x-6 => -5x-6
a = 1 and b = 2 => 1x+2 => x+2
a = -1 and b = 2 => -1x+2 => -x+2
Factorization#
If \(a\) and \(b\) are nonzero and \(g\) is the greatest common divisor (gcd) of \(a\) and $$ then
\(\displaystyle ax+b = g(\frac{a}{g}x+\frac{b}{g})\)
We will write a function that takes two parameters: the coefficients of the expression and returns the factorization of the given expression as a string, as shown in the equation above.
Do not forget to add paranthesis.
Represent \(1(3x+5)\) as \((3x+5)\)
Represent \(-1(3x-5)\) as \(-(3x-5)\)
Examples:
\(\,\,\,\,\,12x+20 = \,\,\,\, 4(3x+5)\)
\(-12x+20 = -4(3x-5)\)
\(3x+5 = (3x+5)\)
\(-3x+5 = -(3x-5)\)
def fact_lin(a, b):
if (a==0) & (b==0): return '0'
if (a!=0) & (b==0): return f'{a}x'
if (a==0) & (b!=0): return f'{b}'
GCD = gcd(a,b)
if GCD == 1: return '('+display_lin(a,b)+')'
if GCD == -1: return '-'+ f'({display_lin(a//GCD, b//GCD)})'
return f'{GCD}'+ f'({display_lin(a//GCD, b//GCD)})'
print(f'a = 5 and b = 0 => Expression: 5x => Factorization: {fact_lin(5, 0)}')
print(f'a = 0 and b = 0 => Expression: 0 => Factorization: {fact_lin(0, 0)}')
print(f'a = 0 and b = 0 => Expression: 0 => Factorization: {fact_lin(0, 0)}')
print(f'a = 12 and b = 20 => Expression: 12x+20 => Factorization: {fact_lin(12, 20)}')
print(f'a = -12 and b = 20 => Expression: -12x+20 => Factorization: {fact_lin(-12, 20)}')
print(f'a = 12 and b = -20 => Expression: 12x-20 => Factorization: {fact_lin(12, -20)}')
print(f'a = -12 and b = -20 => Expression: -12x-20 => Factorization: {fact_lin(-12, -20)}')
print(f'a = 3 and b = 5 => Expression: 3x+5 => Factorization: {fact_lin(3, 5)}')
print(f'a = -3 and b = 5 => Expression: -3x+5 => Factorization: {fact_lin(-3, 5)}')
print(f'a = 2 and b = 6 => Expression: 2x+6 => Factorization: {fact_lin(2, 6)}')
a = 5 and b = 0 => Expression: 5x => Factorization: 5x
a = 0 and b = 0 => Expression: 0 => Factorization: 0
a = 0 and b = 0 => Expression: 0 => Factorization: 0
a = 12 and b = 20 => Expression: 12x+20 => Factorization: 4(3x+5)
a = -12 and b = 20 => Expression: -12x+20 => Factorization: -4(3x-5)
a = 12 and b = -20 => Expression: 12x-20 => Factorization: 4(3x-5)
a = -12 and b = -20 => Expression: -12x-20 => Factorization: -4(3x+5)
a = 3 and b = 5 => Expression: 3x+5 => Factorization: (3x+5)
a = -3 and b = 5 => Expression: -3x+5 => Factorization: -(3x-5)
a = 2 and b = 6 => Expression: 2x+6 => Factorization: 2(x+3)
Quadratics#
Display#
We will write a function that takes three parameters: the coefficients of the expression and returns a string.
The first parameter is the coefficient of the \(x^2\) term, and the second parameter is the coefficient of the \(x\) term and the last one is the constant term.
The parameters \(a, b, c\) represent the expression \(ax^2+bx+c\).
Exclude the zero terms, such as \(0x^2\), \(0x\) and \(0\), from the expressions.
Represent
\(1x^2\) as \(x^2\)
\(-1x^2\) as \(-x^2\)
\(1x\) as \(x\)
\(-1x\) as \(-x\)
def display_quad(a, b, c):
if a==0 : return display_lin(b,c)
if (b==0) & (c==0): return f'{a}x^2'
if b > 0: pb = '+' # add + sign for +b part of ax^2+bx+c
else: pb = ''
if (c > 0) & (b==0): pc='+' # add + sign for +c part of ax^2+c
else: pc=''
if a == 1: return 'x^2'+pb+pc+display_lin(b,c) # display 1x^2 as x^2
if a == -1: return '-x^2'+pb+pc+display_lin(b,c) # display -1x^2 as -x^2
return f'{a}x^2'+pb+pc+display_lin(b,c)
print(f'a = 0, b = -5, c = -7 => 0x^2-5x-7 => {display_quad(0, -5, -7)}')
print(f'a = 3, b = -5, c = -7 => 3x^2-5x-7 => {display_quad(3, -5, -7)}')
print(f'a = 3, b = 5, c = -7 => 3x^2+5x-7 => {display_quad(3, 5, -7)}')
print(f'a = 3, b = 0, c = -7 => 3x^2+0x-7 => {display_quad(3, 0, -7)}')
print(f'a = 3, b = 0, c = 0 => 3x^2+0x+0 => {display_quad(3, 0, 0)}')
print(f'a = 1, b = 2, c = 3 => 1x^2+2x+3 => {display_quad(1, 2, 3)}')
print(f'a = -1, b = 2, c = 3 => -1x^2+2x+3 => {display_quad(-1, 2, 3)}')
print(f'a = 1, b = 0, c = 1 => 1x^2+0x+1 => {display_quad(1, 0, 1)}')
print(f'a = 1, b = 0, c = -1 => 1x^2+0x+1 => {display_quad(1, 0, -1)}')
a = 0, b = -5, c = -7 => 0x^2-5x-7 => -5x-7
a = 3, b = -5, c = -7 => 3x^2-5x-7 => 3x^2-5x-7
a = 3, b = 5, c = -7 => 3x^2+5x-7 => 3x^2+5x-7
a = 3, b = 0, c = -7 => 3x^2+0x-7 => 3x^2-7
a = 3, b = 0, c = 0 => 3x^2+0x+0 => 3x^2
a = 1, b = 2, c = 3 => 1x^2+2x+3 => x^2+2x+3
a = -1, b = 2, c = 3 => -1x^2+2x+3 => -x^2+2x+3
a = 1, b = 0, c = 1 => 1x^2+0x+1 => x^2+1
a = 1, b = 0, c = -1 => 1x^2+0x+1 => x^2-1
Factorization#
c is zero#
This is the simpler case since \(x\) is one of the factors, and the remaining part will be a linear expression.
The fact_lin function can then be used to factorize that linear expression.
\(\displaystyle ax^2+bx = x(ax+b) = g x (\frac{a}{g}x+\frac{b}{g})\)
Examples:
\(\,\,\,\,\,12x^2+20x = \,\,\,\, 4x(3x+5)\)
\(-12x^2+20x = -4x(3x-5)\)
def fact_quad1(a, b):
if (a==0) & (b==0): return '0'
if (a!=0) & (b==0): return f'{a}x^2'
if (a==0) & (b!=0): return f'{b}x'
GCD = gcd(a,b)
if GCD == 1: return 'x('+display_lin(a,b)+')' # remove 1 from 1x(...)
if GCD == -1: return '-x'+ f'({display_lin(a//GCD, b//GCD)})' # remove 1 from -1x(...)
return f'{GCD}x'+ f'({display_lin(a//GCD, b//GCD)})'
print(f'a = 0 and b = 0 => Expression: 0x^2 + 0x => Factorization: {fact_quad1(0, 0)}')
print(f'a = 5 and b = 0 => Expression: 5x^2 + 0x => Factorization: {fact_quad1(5, 0)}')
print(f'a = 12 and b = 20 => Expression: 12x^2 + 20x => Factorization: {fact_quad1(12, 20)}')
print(f'a = -12 and b = 20 => Expression: -12x^2 + 20x => Factorization: {fact_quad1(-12, 20)}')
print(f'a = 12 and b = -20 => Expression: 12x^2 - 20x => Factorization: {fact_quad1(12, -20)}')
print(f'a = -12 and b = -20 => Expression: -12x^2 - 20x => Factorization: {fact_quad1(-12, -20)}')
print(f'a = 3 and b = 5 => Expression: 3x^2 + 5x => Factorization: {fact_quad1(3, 5)}')
print(f'a = -3 and b = 5 => Expression: -3x^2 + 5x => Factorization: {fact_quad1(-3, 5)}')
print(f'a = 2 and b = 4 => Expression: 2x^2 + 4x => Factorization: {fact_quad1(2, 4)}')
print(f'a = -2 and b = 4 => Expression: -2x^2 + 4x => Factorization: {fact_quad1(-2, 4)}')
a = 0 and b = 0 => Expression: 0x^2 + 0x => Factorization: 0
a = 5 and b = 0 => Expression: 5x^2 + 0x => Factorization: 5x^2
a = 12 and b = 20 => Expression: 12x^2 + 20x => Factorization: 4x(3x+5)
a = -12 and b = 20 => Expression: -12x^2 + 20x => Factorization: -4x(3x-5)
a = 12 and b = -20 => Expression: 12x^2 - 20x => Factorization: 4x(3x-5)
a = -12 and b = -20 => Expression: -12x^2 - 20x => Factorization: -4x(3x+5)
a = 3 and b = 5 => Expression: 3x^2 + 5x => Factorization: x(3x+5)
a = -3 and b = 5 => Expression: -3x^2 + 5x => Factorization: -x(3x-5)
a = 2 and b = 4 => Expression: 2x^2 + 4x => Factorization: 2x(x+2)
a = -2 and b = 4 => Expression: -2x^2 + 4x => Factorization: -2x(x-2)
c is not zero#
Use the AC method. There are three main steps:
Find two integers (m, n) whose product is ac and whose sum is b. Use these two numbers to split the x term into two parts. If no such pair of integers exists, factorization by integers is impossible.
Group the terms by considering the first two and last two terms as separate groups, then factor out the GCD of each group.
Factor out the common factor from each group.
def fact_quad2(a, b, c):
print('Equation:', display_quad(a,b,c))
is_fact = '' # is it factorizable
# ac method: find m and n
p = a*c
for m in range(-abs(p), abs(p)+1):
if m != 0:
if (p%m == 0) & (m+p/m == b):
n = p//m
is_fact = True # factorization can be done
break
if is_fact == True:
if n > 0: pn = '+' # add + sign for +n part
else: pn = ''
# Step-1: split the x term into two parts.
print('Step-1 :', display_quad(a, m, 0) + pn + display_lin(n, c))
# Step-2: do factorization of each group
group1 = fact_quad1(a,m)
group2 = pn +fact_lin(n, c)
print('Step-2 :', group1+group2)
# Step-3: Factor out the common factor from each group.
first_factor_part1 = group1[:group1.find('(')]
first_factor_part2 = group2[:group2.find('(')]
if len(first_factor_part2) == 1: first_factor_part2 += '1' # add the invisible 1 in front of the second group
first_factor = '('+ first_factor_part1 + first_factor_part2 +')'
second_factor = group1[group1.find('('):]
print('Step-3 :', first_factor + second_factor)
else:
print('No factorization')
fact_quad2(2, -7, -15)
Equation: 2x^2-7x-15
Step-1 : 2x^2-10x+3x-15
Step-2 : 2x(x-5)+3(x-5)
Step-3 : (2x+3)(x-5)
fact_quad2(1, 2, 1)
Equation: x^2+2x+1
Step-1 : x^2+1x+x+1
Step-2 : x(x+1)+(x+1)
Step-3 : (x+1)(x+1)
fact_quad2(1, -2, 1)
Equation: x^2-2x+1
Step-1 : x^2-1x-x+1
Step-2 : x(x-1)-(x-1)
Step-3 : (x-1)(x-1)
fact_quad2(1, 0, 1)
Equation: x^2+1
No factorization
Future Work#
Factorize expressions in the form \(ax^3+bx^2+cx\)