10. Math as code

• variable name conventions

• equals = ≈ ≠ :=

• square root and complex numbers √ i

• dot & cross · × ∘

  • scalar multiplication

  • vector multiplication

  • dot product

  • cross product

• sigma Σ - summation

• capital Pi Π - products of sequences

• pipes ||

  • absolute value

  • Euclidean norm

  • determinant

• hat â - unit vector

• “element of” ∈ ∉

• common number sets ℝ ℤ ℚ ℕ

• function ƒ

  • piecewise function

  • common functions

  • function notation ↦ →

• prime ′

• floor & ceiling ⌊ ⌉

• arrows

  • material implication ⇒ →

  • equality < ≥ ≫

  • conjunction & disjunction ∧ ∨

• logical negation ¬ ~ !

• intervals

10.1. variable name conventions

• s - italic lowercase letters for scalars (e.g. a number)

• x - bold lowercase letters for vectors (e.g. a 2D point)

• A - bold uppercase letters for matrices (e.g. a 3D transformation)

• θ - italic lowercase Greek letters for constants and special variables (e.g. polar angle θ, theta)

10.2. equals symbols

There are a number of symbols resembling the equals sign =. Here are a few common examples:

• = is for equality (values are the same)

• ≠ is for inequality (value are not the same)

• ≈ is for approximately equal to (π ≈ 3.14159)

• := is for definition (A is defined as B)

In Python:

## equality
2 == 3

## inequality
2 != 3

## approximately equal
import math
math.isclose(math.pi, 3.14159) # math.isclose doesn't have a third argument for tolerance, so this is false

from numpy.testing import assert_almost_equal
assert_almost_equal(math.pi, 3.14159, 1e-5) # we gave it a the tolerance we want, 5 decimal places. 
# This is actually a unit test, equivalent to "assert isclose(x,y)", read on for more. 

def almost_equal(x, y, epsilon=7): 
  ''' you can make your own! 
  in numpy, 1e-7 is the default epsilon
  '''
  return abs(x - y) < 10 ** -epsilon

Read more: programmers got this idea from the [epsilon-delta definition of limit][1]

Note: subclasses of unittest.TestCase come with their own assertAlmostEqual.

Warning: please don’t use exact == equality on floats!

In mathematical notation, you might see the :=, =: and = symbols being used for definition.^[2]

For example, the following defines x to be another name for 2kj.

In python, we define our variables and provide aliases with =.

x = 2 * k * j

Assignment in python is generally mutable besides special cases like Tuple.

Note: Some languages have pre-processor #define statements, which are closer to a mathematical define.

Notice that def is a form of := as well.

def plus(x, y): 
  return x + y

The following, on the other hand, represents equality:

Important: the difference between = and == can be more obvious in code than it is in math literature! In python, a = is an instruction. You’re telling the machine to interact with the namespace, add something to it or change something in it. In python, when you write == you’re asking the machine “may I have a bool?”. In math, the former case is either covered by := or =, while the latter case is usually =, and you might have to do some disambiguating in your reading.

In math, when I write 1 + 1 = 2 I’m making a judgment. It’s not that i’m asking the world (or the chalkboard) for a bool, it’s that I’m keeping track of my beliefs. This distinction is the foundation of unit tests or assertions.

# assert in python takes an expression that lands in bool and a string to be printed if it turns out false. 
assert plus(1, 1) == 2, "DANGER: PHYSICS IS BROKEN. PLEASE STAY INSIDE. "

10.3. square root and complex numbers

A square root operation is of the form:

In programming we use a sqrt function, like so:

import math
print(math.sqrt(2))
# Out: 1.4142135623730951

import numpy as np
print(np.sqrt(2))
# Out: 1.4142135623730951

Complex numbers are expressions of the form , where is the real part and is the imaginary part. The imaginary number is defined as:

.

Vanilla python has a complex constructor, and a standard module cmath for working with them.

complex(1,1)
# Out: (1+1j)s

math.sqrt(complex(1,1))
# TypeError: can't convert complex to float

import cmath
cmath.sqrt(complex(1,1))
# Out: (1.09868411346781+0.45508986056222733j)

# you need numpy to get conjugate
np.conj(complex(0.5,0.5))
# Out: (0.5-0.5j)

# we can represent the basic meaning of the imaginary unit like so
assert cmath.sqrt(complex(-1, 0)) == complex(0,1)

As you can see, it uses j to denote the imaginary unit, instead of i.

The conjugate of a complex number is flipping the sign of the imaginary part.

If z is a python complex number, z.real gets the real part (exactly as an object attribute) and z.imag gets the imaginary part.

Just as complex numbers can be interpreted as a sort of wrapper around tuples of reals, a complex number data type wraps two floats. Numpy uses this to implement complex numbers of different sizes/precisions.

The syntax is close enough to cmath, but it comes with the power and convenience of numpy. Importantly, other numpy methods are better at casting to and from complex.

observe the following cube roots of unity

z1 = 0.5 * np.complex(-1, math.sqrt(3)) # Numpy's constructor is basically the same.  
z2 = np.conj(z1) # but numpy gives us a conjugation function, while the standard module does not. 

assert math.isclose(z1**3, z2**3)
# TypeError: can't convert complex to float

np.testing.assert_almost_equal(z1**3, z2**3)

Read on about numpy’s complex numbers

10.4. dot & cross

The dot · and cross × symbols have different uses depending on context.

They might seem obvious, but it’s important to understand the subtle differences before we continue into other sections.

10.4.1. scalar multiplication

Both symbols can represent simple multiplication of scalars. The following are equivalent:

In programming languages we tend to use asterisk for multiplication:

result = 5 * 4

Often, the multiplication sign is only used to avoid ambiguity (e.g. between two numbers). Here, we can omit it entirely:

If these variables represent scalars, the code would be:

result = 3 * k * j

10.4.2. vector multiplication

To denote multiplication of one vector with a scalar, or element-wise multiplication of a vector with another vector, we typically do not use the dot · or cross × symbols. These have different meanings in linear algebra, discussed shortly.

Let’s take our earlier example but apply it to vectors. For element-wise vector multiplication, you might see an open dot ∘ to represent the Hadamard product.^[2]

In other instances, the author might explicitly define a different notation, such as a circled dot ⊙ or a filled circle ●.^[3]

Here is how it would look in code, using arrays [x, y] to represent the 2D vectors.

s = 3
k = [1, 2]
j = [2, 3]

tmp = multiply(k, j)
result = multiply_scalar(tmp, s)
# Out: [6, 18]

Our multiply and multiply_scalar functions look like this:

def multiply(a, b):
  return [aa * bb for aa,bb in zip(a,b)


def multiply_scalar(scalar, a):
  return [scalar * aa for aa in a]

Similarly, matrix multiplication typically does not use the dot · or cross symbol ×.

Numpy’s broadcasted syntax for scaling looks like this:

def multiply_scalar(scalar, a): 
  return scalar * np.array(a)

10.4.3. dot product

The dot symbol · can be used to denote the dot product of two vectors. Sometimes this is called the scalar product since it evaluates to a scalar.

It is a very common feature of linear algebra, and with a 3D vector it might look like this:

k = [0, 1, 0]
j = [1, 0, 0]

d = np.dot(k, j)
# Out: 0

The result 0 tells us our vectors are perpendicular. Here is a dot function for 3-component vectors:

def dot(a, b):
  return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]

10.4.4. cross product

The cross symbol × can be used to denote the cross product of two vectors.

In code, it would look like this:

k = [0, 1, 0]
j = [1, 0, 0]

result = cross(k, j)
# Out: [ 0, 0, -1 ]

Here, we get [0, 0, -1], which is perpendicular to both k and j.

Our cross function:

def cross(a, b): 
  ''' take two 3D vectors and return their cross product. '''
  rx = a[1] * b[2] - a[2] * b[1]
  ry = a[2] * b[0] - a[0] * b[2]
  rz = a[0] * b[1] - a[1] * b[0]
  return rx, ry, rz

It’s good to practice and grok these operations, but in real life you’ll use Numpy.

10.5. sigma

The big Greek Σ (Sigma) is for Summation. In other words: summing up some numbers.

Here, i=1 says to start at 1 and end at the number above the Sigma, 100. These are the lower and upper bounds, respectively. The i to the right of the “E” tells us what we are summing. In code:

Hence, the big sigma is the for keyword.

sum([k for k in range(100)])
# Out: 5050

Tip: With whole numbers, this particular pattern can be optimized to the following (and try to grok the proof. The legend of how Gauss discovered I can only describe as “typical programmer antics”):

def sum_to_n(n):
  ''' return the sum of integers from 0 to n'''
  return 0.5 * n * (n + 1)

Here is another example where the i, or the “what to sum,” is different:

In code:

sum([2*k + 1 for k in range(100)])
# Out: 10000

important: range in python has an inclusive lower bound and exclusive upper bound, meaning that ... for k in range(100) is equivalent to the sum of ... for k=0 to k=n.

If you’re still not absolutely fluent in indexing for these applications, spend some time with Trev Tutor on youtube.

The notation can be nested, which is much like nesting a for loop. You should evaluate the right-most sigma first, unless the author has enclosed them in parentheses to alter the order. However, in the following case, since we are dealing with finite sums, the order does not matter.

In code:

sum(
  [sum([3*i*j 
        for j 
        in range(4,7)]) 
   for i 
   in range(1,3)])
# Out: 135

10.6. capital Pi

The capital Pi or “Big Pi” is very similar to Sigma, except we are using multiplication to find the product of a sequence of values.

Take the following:

This was removed from vanilla python for python 3, but it’s easy to recover with a generalization of the list accumulator.

def times(x, y): 
  ''' first, give a name to the multiplication operator '''
  return x * y

from functools import reduce

reduce(times, range(1,7))
# Out: 720

With reduce, you can actually repeatedly apply a binary function to items of a list and accumulate the value for any binary operator. Python gives and and or out of the box like sum, but keep reduce in mind if you encounter a less common binary operator out in the wild.

Note that in Numpy arrays, the syntax is different (and product is given out of the box)

import numpy as np

xs = np.array([2*k + 1 for k in range(100)])
ys = np.array(range(1,7))

xs.sum()
# Out: 10000

ys.prod()
# Out: 720

which is better on larger input, but you’re always welcome to use functions for ordinary lists as you please.

10.7. pipes

Pipe symbols, known as bars, can mean different things depending on the context. Below are three common uses: absolute value, Euclidean norm, and determinant.

These three features all describe the length of an object.

10.7.1. absolute value

For a number x, |x| means the absolute value of x. In code:

x = -5
abs(x)
# Out: 5

10.7.2. Euclidean norm

For a vector v, ‖v‖ is the Euclidean norm of v. It is also referred to as the “magnitude” or “length” of a vector.

Often this is represented by double-bars to avoid ambiguity with the absolute value notation, but sometimes you may see it with single bars:

Here is an example using an array [x, y, z] to represent a 3D vector.

v = [0, 4, -3]
length(v)
# Out: 5.0

The `length** function:

def length(vec):
  x = vec[0]
  y = vec[1]
  z = vec[2]
  return math.sqrt(x**2 + y**2 + z**2)

The implementation for arbitrary length’d vectors is left as an exercise for the reader.

In practice, you’ll probably use the following numpy call

np.linalg.norm([0, 4, -3])
# Out: 5.0

Resources:

• [numpy.linalg docs](get link to numpy.linalg docs)

10.7.3. determinant

[determinant](https://en.wikipedia.org/wiki/Determinant) of matrix **A**.

Here is an example computing the determinant of a 2x2 identity matrix

ident_2 = [[1, 0], 
           [0, 1]]

np.linalg.det(ident_2)
# Out: 1

You should watch 3blue1brown, but in short if a matrix (list of list of numbers) is interpreted as hitting a coordinate system with a squisher-stretcher-rotater, the determinant of that matrix is the measure of how much the unit area/volume of the coordinate system got squished-stretched-rotated.

np.linalg.det(np.identity(100)) # the determinant of the 100 x 100 identity matrix is still one, because the identity matrix doesn't squish, stretch, or rotate at all. 
# Out: 1.0

np.linalg.det(np.array([[0, -1], [1, 0]])) # 90 degree rotation. 
# Out: 1.0

The second matrix was the 2D rotation at 90 degrees.

10.8. hat

In geometry, the “hat” symbol above a character is used to represent a unit vector. For example, here is the unit vector of a:

In Cartesian space, a unit vector is typically length 1. That means each part of the vector will be in the range of -1.0 to 1.0. Here we normalize a 3D vector into a unit vector:

a = [ 0, 4, -3 ]
normalize(a)
# Out: [ 0, 0.8, -0.6 ]

If a vector is that which has magnitude and direction, normalization of a vector is the operation that deletes magnitude and preserves direction.

Here is the normalize function, operating on 3D vectors:

def normalize(vec):
  x = vec[0]
  y = vec[1]
  z = vec[2]
  squaredLength = x * x + y * y + z * z

  if (squaredLength > 0):
    length = math.sqrt(squaredLength)
    vec[0] = x / length
    vec[1] = y / length
    vec[2] = z / length
  
  return vec

Which Numpy’s broadcasting syntax sugar can do in fewer lines

You should try to generalize this to vectors of arbitrary length yourself, before reading this…

Go, I mean it!

def normalize(vec):
  ''' *sigh* if you don't do it yourself you'll never learn! '''
  vec = np.array(vec) # ensure that input is casted to numpy
  length = np.linalg.norm(vec)
  if length > 0:
    return vec / length

Notice that broadcasting here is just short for [x / length for x in vec]. But it’s actually faster on large input, because arrays.

Read the Numpy docs. BE the Numpy docs

10.9. element

In set theory, the “element of” symbol ∈ and ∋ can be used to describe whether something is an element of a set. For example:

Here we have a set of numbers A = { 3, 9, 14 } and we are saying 3 is an “element of” that set.

The in keyword plays the role of the elementhood function, giving a bool.

A = [ 3, 9, 14 ]

3 in A
# Out: True

Python also has set. You can wrap any iterable or generator with the set keyword to delete repeats.

set([3,3,3,2,4,3,3,3,1,2,4,5,3])
# Out: {1, 2, 3, 4, 5}

3 in set(range(1, 20, 4))
# Out: False

The backwards ∋ is the same, but the order changes:

You can also use the “not an element of” symbols ∉ and ∌ like so:

Which you know is represented by the convenient not keyword in python.

10.10. common number sets

You may see some some large Blackboard letters among equations. Often, these are used to describe sets.

For example, we might describe k to be an element of the set ℝ.

Listed below are a few common sets and their symbols.

10.10.1. ℝ real numbers

The large ℝ describes the set of real numbers. These include integers, as well as rational and irrational numbers.

Computers approximate ℝ with float.

You can use isinstance to check “k ∈ ℝ”, where float and ℝ aren’t really the same thing but the intuition is close enough.

isinstance(np.pi, float)
# Out: True

Again, you may elevate that bool to an assertion that makes-or-breaks the whole program with the assert keyword when you see fit.

Excellent resource on floats in python

10.10.2. ℚ rational numbers

Rational numbers are real numbers that can be expressed as a fraction, or ratio. Rational numbers cannot have zero as a denominator.

Imagine taking ℝ and removing radicals (like np.sqrt) and logarithms (in a family called transcendentals), that’s basically what ℚ is, at least enough for a rough first approximation.

This also means that all integers are rational numbers, since the denominator can be expressed as 1.

An irrational number, on the other hand, is one that cannot be expressed as a ratio, like π (math.pi).

A reason a programmer might care about the difference between Q and R is in the design of unit tests— fractions are terminating decimals, and sometimes when you’re a 100% sure that a number will be a basic rational (like counting change, 0.25, 0.10, 0.05, etc.), you’re allowed to use == in unit tests rather than isclose or assert_almost_equal. The point is that you know not to use exact equality == when anything like sqrt or log is involved!

You can work with rationals without dividing them into floatiness with the fractions standard module

10.10.3. ℤ integers

An integer is a whole number. Just imagine starting from zero and one and building out an inventory with addition and subtraction.

An integer has no division, no decimals.

assert isinstance(8/7, int)

10.10.4. ℕ natural numbers

A natural number, a non-negative integer. Depending on the context and field of study, the set may or may not start with zero.

…ok but, between you and me, they 200% start with zero.

ℕ also happens to be the first inductive construction in the study of datatypes, consisting of a single axiom (“Zero is a ℕ”) and a single inference rule (“if n is a ℕ then n + 1 is also a ℕ”)

ℕ is not a datatype in python, we can’t use typechecking to disambiguate int from non-negative int, but in a pinch you could easily write up something that combines x >= 0 judgments with isinstance(x, int).

10.10.5. ℂ complex numbers

As we saw earlier, the complex numbers are a particular wrapper around tuples of reals.

A complex number is a combination of a real and imaginary number, viewed as a co-ordinate in the 2D plane. For more info, see A Visual, Intuitive Guide to Imaginary Numbers.

We can say ℂ = {a + b*i | a,b ∈ ℝ}, which is a notation called

10.11. Set builder notation

Pythoners have a name for set builder notation; and the name is comprehension

• { }: delimiter around iterable (curlybois for dict or set, [ for list)

• a + b * i: an expression (for instance, earlier when we made a list of odd numbers this expression was 2*k + 1) to be evaluated for each item in source list.

• |: for

• a,b ∈ ℝ: this just shows that a,b are drawn from a particular place, in this case the real numbers.

So if you’ve been writing Python listcomps, that definition of the complex numbers wasn’t so bad! Say it with me this time

`ℂ = {a + b*i | a,b ∈ ℝ}``

inhaaaaaaless unison “C IS THE SET OF a + b*i FOR REAL NUMBERS a AND b”

If you want, you can draw up a grainy picture of an interval of ℂ with zip and np.linspace, and of course list comprehension.

j = np.complex(0,1)

R = np.linspace(-2, 2, 100)

{a + b * j for a,b in zip(R, R)}
# too much to print but try it yourself. 

10.12. functions

A function transforms an input into an output value. For example, the following is a function:

We can give this function a name. Commonly, we use ƒ to describe a function, but it could be named A or anything else.

In code, we might name it square and write it like this:

def square(x): 
  return math.pow(x, 2)

Sometimes a function is not named, and instead the output is written.

In the above example, x is the input, the transformation is squaring, and y is the output. We can express this as an equation because, conventionally, we think of x as input and y as output.

But we have a stronger idea called anonymous functions to generalize this.

Just as we can name strings x = "Alonzo" then call them with their names or we can just pass string literals, we also have function literals.

Math first, then python:

x ↦ x^2 is equivalent to the equational description above.

Nearly identical, but very different to the untrained eye, is λx.x^2, hence the python keyword

lambda x: x**2

Functions can also have multiple parameters, like in a programming language. These are known as arguments in mathematics, and the number of arguments a function takes is known as the arity of the function.

10.12.1. dictionaries are functions

Sometimes mathematicians, like software developers, need to specify maps by enumerating each input-output pair* when there is no expression that computes output from input.

Note: formally, mathematicians require that functions not be ambiguous*, so when you have a function and you have an input, there can be no uncertainty as to what the output should be; you mustn’t be confused about whether an apple is red or purple (in introductory algebra courses this is called the “vertical line test”, but it applies to all maps). Notice that the implementation of hash maps already guarantees this in the case of dictionaries! Notice also that we make no such requirement on outputs, both an apple and a banana can land on purple! With caveats like these, we can study the properties of different kinds of functions into different kinds, important in compression and security engineering.

10.12.2. piecewise function

Some functions will use different relationships depending on the input value, x.

The following function ƒ chooses between two “sub functions” depending on the input value.

This is very similar to if / else in code. The right-side conditions are often written as “for x < 0” or “if x = 0”. If the condition is true, the function to the left is used.

In piecewise functions, “otherwise” and “elsewhere” are analogous to the else statement in code.

def f(x):
  if (x >= 1):
    return (math.pow(x, 2) - x) / x
  else:
    return 0

10.12.3. common functions

There are some function names that are ubiquitous in mathematics. For a programmer, these might be analogous to functions “built-in” to the language (like parseInt in JavaScript).

One such example is the sgn function. This is the signum or sign function. Let’s use piecewise function notation to describe it:

In code, it might look like this:

def signum(x):
  if (x < 0):
    return -1
  elif (x > 0):
    return 1
  else: 
    return 0

See signum for this function as a module.

Other examples of such functions: sin, cos, tan.

10.12.4. function notation

In some literature, functions may be defined with more explicit notation. For example, let’s go back to the square function we mentioned earlier:

It might also be written in the following form:

The arrow here with a tail typically means “maps to,” as in x maps to x².

Sometimes, when it isn’t obvious, the notation will also describe the domain and codomain of the function. A more formal definition of ƒ might be written as:

A function’s domain and codomain is a bit like its input and output types, respectively. Here’s another example, using our earlier sgn function, which outputs an integer:

The arrow here (without a tail) is used to map one set to another.

In Python and other dynamically typed languages, you might use documentation and/or runtime checks to explain and validate a function’s input/output. Example:

def square_ints(k): 
  ''' FEED ME INTEGER '''
  try: 
    assert isinstance(k, int), "I HUNGER FOR AN INTEGER! "
    return math.pow(k, 2)
  except AssertionError as e:
    raise e

The python of a more glorious future as described in pep484 proposes a static type checker for Python, but no one’s proposed anything shrewd enough to prevent code with type errors from compiling for Python yet.

As we will see in the following sample of pep484 Python, the set interpretation of domain and codomain makes way for a types interpretation of domain and codomain

def square(x: float) -> float: 
  ''' a pep484 annotation isn't that different from if i declared in the docstring; 
  
  input/domain: a float
  output/codomain: another float 
  '''
  return x**2

Other languages, like Java, allow for true method overloading based on the static types of a function’s input/output. This is closer to mathematics: two functions are not the same if they use a different domain. This is also called polymorphism and it explains why 'literally' + 'alonzo' concats two strings together but 1 + 1 is addition on numbers.

10.13. prime

The prime symbol (′) is often used in variable names to describe things which are similar, without giving it a different name altogether. It can describe the “next value” after some transformation.

For example, if we take a 2D point (x, y) and rotate it, you might name the result (x′, y′). Or, the transpose of matrix M might be named M′.

In code, we typically just assign the variable a more descriptive name, like transformedPosition.

For a mathematical function, the prime symbol often describes the derivative of that function. Derivatives will be explained in a future section. Let’s take our earlier function:

Its derivative could be written with a prime ′ symbol:

In code:

def f(x): 
  return Math.pow(x, 2)

def f_prime(x):
  return 2 * x

Multiple prime symbols can be used to describe the second derivative ƒ′′ and third derivative ƒ′′′. After this, authors typically express higher orders with roman numerals ƒ^IV or superscript numbers ƒ⁽ⁿ⁾.

10.14. floor & ceiling

The special brackets ⌊x⌋ and ⌈x⌉ represent the floor and ceil functions, respectively.

In code:

math.floor(4.8)
math.ceil(3.1)
np.floor(4.9)
np.ceil(3.001)

Note: the Numpy version returns a float, in the above example 4.0, rather than the int 4

When the two symbols are mixed ⌊x⌉, it typically represents a function that rounds to the nearest integer:

Python automatically gives you a keyword round to call on a number.

10.15. arrows

Arrows are often used in function notation. Here are a few other areas you might see them.

10.15.1. material implication

Arrows like ⇒ and → are sometimes used in logic for material implication. That is, if A is true, then B is also true.

Interpreting this as code might look like this:

def if_A_then_B:
  if A:
    assert B, "alas, not A!"
    return B

The arrows can go in either direction ⇐ ⇒, or both ⇔. When A ⇒ B and B ⇒ A, they are said to be equivalent:

10.15.2. inequality

In math, the < > ≤ and ≥ are typically used in the same way we use them in code: less than, greater than, less than or equal to and greater than or equal to, respectively.

assert 50 > 2
assert 2 < 10
assert 3 <= 4
assert 4 >= 4

On rare occasions you might see a slash through these symbols, to describe not. As in, k is “not greater than” j.

The ≪ and ≫ are sometimes used to represent significant inequality. That is, k is an order of magnitude larger than j. Sometimes read “beats”, when I say x^k ≫ log(x) what I’m really saying is that “polynomial functions grow an order of magnitude faster than logarithms; in a word, the polynomial beats the logarithm.”

10.15.3. conjunction & disjunction

Another use of arrows in logic is conjunction ∧ and disjunction ∨. They are analogous to a programmer’s AND and OR operators, respectively.

The following shows conjunction ∧, the logical AND.

In Python, we just say and. Assuming k is a natural number, the logic implies that k is 3:

lambda k: if (k > 2 and k < 4): assert k == 3, "Exercise: can this error ever be raised?"

Since both sides are equivalent ⇔, it also implies the following:

lambda k: if (k == 3): assert (k > 2 and k < 4), "I mean it, think through this exercise."

The down arrow ∨ is logical disjunction, like the OR operator.

In Python, we have the or keyword. Like and, it is a function that will trade you one bool for two bools.

10.16. logical negation

Occasionally, the ¬, ~ and ! symbols are used to represent logical NOT. For example, ¬A is only true if A is false.

Here is a simple example using the not symbol:

An example of how we might interpret this in code:

lambda x, y: if (x != y): assert not x == y, "arrr, buried treasure lost forever. "

Note: The tilde ~ has many different meanings depending on context. For example, row equivalence (matrix theory) or same order of magnitude (discussed in equality).

10.17. intervals

Sometimes a function deals with real numbers restricted to some range of values, such a constraint can be represented using an interval

For example we can represent the numbers between zero and one including/not including zero and/or one as:

• Not including zero or one:

• Including zero or but not one:

• Not including zero but including one:

• Including zero and one:

For example we to indicate that a point x is in the unit cube in 3D we say:

In Python, we have to be sensitive about inclusive vs. exclusive boundaries in generators like range, but you already know that.

if you want to play with infinite lists in Python, learn more about generators

Intervals are used in conjunction with set operations:

• intersection e.g.

• union e.g.

• difference e.g. and

Integer versions in basic python look like this

# intersection of two int intervals
[x for x in range(3,5) if x in range(4, 6+1)]
# Out: [4]

# Union of two int intervals
[x for x in range(20) if x in range(3, 5) or x in range(4, 6+1)]
# Out: [3, 4, 5, 6]

# Set difference
[x for x in range(3, 5) if x not in range(4, 6+1)]
# Out: [3]

[x for x in range(4, 6+1) if x not in range(3, 5)]
# Out: [5, 6]

Using np.linspace, we can approximate what the real versions would look like.

R = np.linspace(-1, 9, 100)

# intersection of two float intervals
[x for x in R if 3 <= x < 5 and 4 <= x <= 6]

# Union of two float intervals
[x for x in R if 3 <= x < 5 or 4 <= x <= 6]

# set differences of two float intervals. 
[x for x in R if 3 <= x < 5 and not (4 <= x <= 6)]

[x for x in R if 4 <= x <= 6 and not (3 <= x < 5)]

https://blog.shahjalalshohag.com/equation-list/

10.18. Combinatorics

10.18.1. General

1. \(\displaystyle \displaystyle \sum \limits_{0\leq k \leq n} {n-k \choose k} = Fib_{n+1}\)

2. \(\displaystyle \displaystyle {n \choose k}={n \choose n-k}\)

3. \(\displaystyle \displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1}\)

4. \(\displaystyle \displaystyle k{n \choose k}=n{n-1 \choose k-1}\)

5. \(\displaystyle \displaystyle {n \choose k}=\frac{n}{k}{n-1 \choose k-1}\)

6. \(\displaystyle \sum \limits_{i=0}^n{n \choose i}=2^n\)

7. \(\displaystyle \sum \limits_{i\geq 0}{n \choose 2i}=2^{n-1}\)

8. \(\displaystyle \sum \limits_{i\geq 0}{n \choose 2i+1}=2^{n-1}\)

9. \(\displaystyle \sum \limits_{i= 0}^k \left( -1 \right) ^i{n \choose i}=\left( -1 \right) ^k{n-1 \choose k}\)

10. \(\displaystyle \sum \limits_{i= 0}^k{n+i \choose i}= \sum \limits_{i= 0}^k{n+i \choose n} = {n+k+1 \choose k}\)

11. \(\displaystyle \displaystyle1{n \choose 1}+2{n \choose 2}+3{n \choose 3}+…+n{n \choose n}=n2^{n-1}\)

12. \(\displaystyle \displaystyle1^2{n \choose 1}+2^2{n \choose 2}+3^2{n \choose 3}+…+n^2{n \choose n}=(n+n^2)2^{n-2}\)

13. Vandermonde’s Identify: \(\displaystyle \sum \limits_{k=0}^r{m \choose k}{n \choose r-k}={m+n \choose r}\)

14. Hockey-Stick Identify: \(\displaystyle \ n,r \in N, n > r, \sum \limits_{i=r}^n{i \choose r}={n+1 \choose r+1}\)

15. \(\displaystyle \sum \limits_{i=0}^k{k \choose i}^2={2k \choose k}\)

16. \(\displaystyle \sum \limits_{k=0}^n{n \choose k}{n \choose n-k}={2n \choose n}\)

17. \(\displaystyle \sum \limits_{k=q}^n{n \choose k}{k \choose q}=2^{n-q}{n \choose q}\)

18. \(\displaystyle \sum \limits_{i=0}^nk^i{n \choose i}=(k+1)^n\)

19. \(\displaystyle \sum \limits_{i=0}^n{2n \choose i}=2^{2n-1}+\frac{1}{2}{2n \choose n}\)

20. \(\displaystyle \sum \limits_{i=1}^n{n \choose i}{n-1 \choose i-1}={2n-1 \choose n-1}\)

21. \(\displaystyle \sum \limits_{i=0}^n{2n \choose i}^2=\frac{1}{2} \left( {4n \choose 2n}+{2n \choose n}^2 \right)\)

22. Highest Power of \(\displaystyle 2\) that divides \(^{2n}C_n\): Let \(\displaystyle x\) be the number of \(1s\) in the binary representation. Then the number of odd terms will be \(\displaystyle 2^x\). Let it form a sequence. The \(n\)-th value in the sequence (starting from \(n\) = 0) gives the highest power of \(\displaystyle 2\) that divides \(^{2n}C_n\).

23. Pascal Triangle

    1. In a row \(\displaystyle p\) where \(\displaystyle p\) is a prime number, all the terms in that row except the \(1s\) are multiples of \(\displaystyle p\).

    2. Parity: To count odd terms in row \(n\), convert \(n\) to binary. Let \(\displaystyle x\) be the number of \(1s\) in the binary representation. Then the number of odd terms will be \(\displaystyle 2^x\).

    3. Every entry in row \(\displaystyle 2^n-1, n\geq 0,\) is odd.

24. An integer \(n\geq 2\) is prime if and only if all the intermediate binomial coefficients \(\displaystyle \displaystyle {n \choose 1},{n \choose 2},…, {n \choose n-1}\) are divisible by \(n\).

25. Kummer’s Theorem: For given integers \(n\geq m\geq 0\) and a prime number \(\displaystyle p\), the largest power of \(\displaystyle p\) dividing \(\displaystyle \displaystyle {n \choose m}\) is equal to the number of carries when \(m\) is added to \(n\)-\(m\) in base \(\displaystyle p\). For implementation take inspiration from lucas theorem.

26. Number of different binary sequences of length \(n\) such that no two \(0\)’s are adjacent=\(\displaystyle Fib_{n+1}\)

27. Combination with repetition: Let’s say we choose \(\displaystyle \displaystyle k\) elements from an \(n\)-element set, the order doesn’t matter and each element can be chosen more than once. In that case, the number of different combinations is: \(\displaystyle \displaystyle {n+k-1 \choose k}\)

28. Number of ways to divide \(n\) persons in \(\displaystyle \frac{n}{k}\) equal groups i.e. each having size \(\displaystyle \displaystyle k\) is $\(\displaystyle \frac{n!}{k!^{\frac{n}{k}} \left( \frac{n}{k} \right) !}= \prod \limits_{n \geq k}^{n-=k}{n-1 \choose k-1}\)$

29. The number non-negative solution of the equation: \(\displaystyle x_1+x_2+x_3+…+x_k=n \text{ is}{n+k-1 \choose n}\)

30. Number of ways to choose \(n\) ids from \(\displaystyle 1\) to b such that every id has distance at least k \(\displaystyle \displaystyle =\left( \frac{b-(n-1)(k-1)}{n} \right)\)

31. \(\displaystyle \displaystyle \sum \limits_{i=1,3,5,\dots}^{i\leq n} \binom{n}{i} a^{n-i}b^i = \frac{1}{2} ((a+b)^n-(a-b)^n)\)

32. \(\displaystyle \displaystyle \sum \limits_{i=0}^{n} \dfrac{\binom{k}{i}}{\binom{n}{i}} = \dfrac{\binom{n+1}{n-k+1}}{\binom{n}{k}}\)

33. Derangement: a permutation of the elements of a set, such that no element appears in its original position. Let \(d(n)\) be the number of derangements of the identity permutation fo size \(n\). $\(d(n)=(n-1) \cdot (d(n-1)+d(n-2)) \, \text{where}\;d(0)=1,d(1)=0\)$

34. Involutions: permutations such that \(\displaystyle p^2 =\) identity permutation. \(\displaystyle a_0 = a_1 = 1\) and \(\displaystyle a_n=a_{n-1} + (n-1)a_{n-2}\) for \(n>1\).

35. Let \(T(n,k)\) be the number of permutations of size \(n\) for which all cycles have length \(\displaystyle \leq k\). $\(T(n, k)= \begin{cases} n! & ; n \le k \\ n \cdot T(n-1, k) - F(n-1, k) \cdot T(n-k-1, k) & ; n > k \\ \end{cases} \)\( Here \)\displaystyle F(n, k) = n \cdot (n - 1) \cdot … \cdot (n - k + 1)$

36. Lucas Theorem

    1. If \(\displaystyle p\) is prime, then \(\displaystyle \left(\frac{p^{a}}{k}\right) \equiv 0 (\mod\; p)\)

    2. For non-negative integers \(m\) and \(n\) and a prime \(\displaystyle p\), the following congruence relation holds: $\(\displaystyle \left(\frac{m}{n}\right) \equiv \prod_{i=0}^{k} \left(\frac{m_{i}}{n_{i}}\right) (mod\; p),\)\( where, \)m=m_{k} p^{k} +m_{k-1} p^{k-1}+…+m_{1} p+m_{0}\(, and \)n=n_{k}p^{k}+n_{k-1}p^{k-1}+…+n_{1}p+n_{0}\( are the base \)\displaystyle p\( expansions of \)m\( and \)n\( respectively. This uses the convention that \)\displaystyle \left(\frac{m}{n}\right)=0\(,when \)m<n$.

37. \(\displaystyle \sum_{i=0}^{n} {n \choose i } \cdot i^{k}\)
    = \(\displaystyle \sum_{i=0}^{n} {n \choose i } \cdot \sum_{j=0}^{k}{ \left\{ \begin{matrix} k\cr j \end{matrix} \right\} \cdot i^{\underline{j}}}\)
    = \(\displaystyle \sum_{i=0}^{n} {n \choose i } \cdot \sum_{j=0}^{k} \left\{ \begin{matrix} k\cr j \end{matrix} \right\} \cdot j! {n \choose i }\)
    = \(\displaystyle \sum_{i=0}^{n} \frac{n!}{(n-i)!} \cdot \sum_{j=0}^{k} \left\{ \begin{matrix}k\cr j \end{matrix} \right\} \cdot \frac{1}{(i-j)!}\)
    = \(\displaystyle \sum_{i=0}^{n} \sum_{j=0}^{k} \frac{n!}{(n-i)!} \cdot \left\{\begin{matrix} k\cr j \end{matrix} \right\} \cdot \frac{1}{(i-j)!}\)
    = n!\(\displaystyle \sum_{i=0}^{n} \sum_{j=0}^{k} \left\{ \begin{matrix} k\cr j \end{matrix} \right\} \cdot \frac{1}{(n-i)!} \cdot \frac{1}{(i-j)!}\)
    = n!\(\displaystyle \sum_{i=0}^{n} \sum_{j=0}^{k} \left\{ \begin{matrix} k\cr j \end{matrix} \right\} \cdot { n-j \choose n-i} \cdot \frac{1}{(n-j)!}\)
    = n!\(\displaystyle \sum_{j=0}^{k} \left\{ \begin{matrix} k\cr j \end{matrix} \right\} \cdot \frac{1}{(n-j)!} \sum_{i=0}^{n} \cdot { n-j \choose n-i}\)
    = \(\displaystyle \sum_{j=0}^{k} \left\{\begin{matrix} k\cr j \end{matrix} \right\} \cdot n^{\underline{j}} \cdot 2^{n-j}\)
    Here \(n^{\underline{j}}=P(n,j)=\dfrac{n!}{(n-j)!}\) and \(\displaystyle \left\{ \begin{matrix} k\cr j \end{matrix} \right\}\) is stirling number of the second kind. So, instead of \(O(n)\), now you can calculate the original equation in \(O(k^2)\) or even in \(O(k \log^2 n)\) using NTT.

38. \(\displaystyle \displaystyle \sum \limits_{i=0}^{n-1} {i \choose j} x^i = x^j(1-x)^{-j-1}\left( 1- x^n \sum \limits_{i=0}^j {n \choose i} x^{j-i} (1-x)^i \right)\)

39. \(\displaystyle x_{0}, x_{1}, x_{2}, x_{3}, … , x_{n}\) \(\displaystyle x_{0} + x_{1}, x_{1} + x_{2}, x_{2}+x_{3}, … x_{n}\) … If we continuously do this \(n\) times then the polynomial of the first column of the \(n\)-th row will be \(\displaystyle p(n)=\sum_{k=0}^{n}{n \choose k} \cdot x(k)\)

40. If \(\displaystyle P(n)=\sum_{k=0}^{n}{n \choose k} \cdot Q(k)\), then, \(Q(n)=\sum_{k=0}^{n}(-1)^{n-k}{n \choose k} \cdot P(k)\)

41. If \(\displaystyle P(n)=\sum_{k=0}^{n}(-1)^{k}{n \choose k} \cdot Q(k)\) , then, \(Q(n)=\sum_{k=0}^{n}(-1)^{k}{n \choose k} \cdot P(k)\)

10.18.2. Catalan Numbers

42. \(\displaystyle C_n=\frac{1}{n+1}{2n \choose n}\)

43. \(\displaystyle C_0=1,C_1=1\text{ and }C_n=\sum \limits_{k=0}^{n-1}C_k C_{n-1-k}\)

44. Number of correct bracket sequence consisting of \(n\) opening and \(n\) closing brackets.

45. The number of ways to completely parenthesize \(n\)+\(\displaystyle 1\) factors.

46. The number of triangulations of a convex polygon with \(n\)+\(\displaystyle 2\) sides (i.e. the number of partitions of polygon into disjoint triangles by using the diagonals).

47. The number of ways to connect the \(\displaystyle 2n\) points on a circle to form \(n\) disjoint i.e. non-intersecting chords.

48. The number of monotonic lattice paths from point \(\displaystyle (0,0)\) to point \(\displaystyle (n,n)\) in a square lattice of size \(n\times n\), which do not pass above the main diagonal (i.e. connecting \(\displaystyle (0,0)\) to \(\displaystyle (n,n)\)).

49. The number of rooted full binary trees with \(n\)+\(\displaystyle 1\) leaves (vertices are not numbered). A rooted binary tree is full if every vertex has either two children or no children.

50. Number of permutations of \(\displaystyle {1, …, n}\) that avoid the pattern \(\displaystyle 123\) (or any of the other patterns of length \(3\)); that is, the number of permutations with no three-term increasing sub-sequence. For \(n = 3\), these permutations are \(\displaystyle 132,\ 213,\ 231,\ 312\) and \(321.\) For \(n = 4\), they are \(\displaystyle 1432,\ 2143,\ 2413,\ 2431,\ 3142,\ 3214,\ 3241,\ 3412,\ 3421,\ 4132,\ 4213,\ 4231,\ 4312\) and \(4321.\)

51. Balanced Parentheses count with prefix: The count of balanced parentheses sequences consisting of \(n+k\) pairs of parentheses where the first \(\displaystyle \displaystyle k\) symbols are open brackets. Let the number be \(\displaystyle C_n^{(k)}\), then $\(\displaystyle \displaystyle C_n^{(k)} = \frac{k+1}{n+k+1} \binom{2n+k}{n}\)$

10.18.3. Narayana numbers

52. \(N(n,k)=\frac{1}{n}\left(\frac{n}{k}\right)\left(\frac{n}{k-1}\right)\)

53. The number of expressions containing \(n\) pairs of parentheses, which are correctly matched and which contain \(\displaystyle \displaystyle k\) distinct nestings. For instance, \(N(4, 2) = 6\) as with four pairs of parentheses six sequences can be created which each contain two times the sub-pattern ‘()’.

10.18.4. Stirling numbers of the first kind

54. The Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one).

55. \(S(n,k)\) counts the number of permutations of \(n\) elements with \(\displaystyle \displaystyle k\) disjoint cycles.

56. \(S(n,k)=(n-1) \cdot S(n-1,k)+S(n-1,k-1),\) where \(S(0,0)=1,S(n,0)=S(0,n)=0\)

57. \(\displaystyle \displaystyle\sum_{k=0}^{n}S(n,k) = n!\)

58. The unsigned Stirling numbers may also be defined algebraically, as the coefficient of the rising factorial: $\(\displaystyle x^{\bar{n}} = x(x+1)...(x+n-1) = \sum_{k=0}^{n}{ S(n, k) x^k}\)$

59. Lets \([n, k]\) be the stirling number of the first kind, then $\(\displaystyle \bigl[\!\begin{smallmatrix} n \\ n\ -\ k \end{smallmatrix}\!\bigr] = \sum_{0 \leq i_1 < i_2 < i_k < n}{i_1i_2....i_k.}\)$

10.18.5. Stirling numbers of the second kind

60. Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets.

61. \(S(n,k)=k \cdot S(n-1,k)+S(n-1,k-1)\), (where ; S(0,0)=1,S(n,0)=S(0,n)=0)

62. \(S(n,2)=2^{n-1}-1\)

63. \(S(n,k) \cdot k!\) = number of ways to color \(n\) nodes using colors from \(\displaystyle 1\) to \(\displaystyle \displaystyle k\) such that each color is used at least once.

64. An \(r\)-associated Stirling number of the second kind is the number of ways to partition a set of \(n\) objects into \(\displaystyle \displaystyle k\) subsets, with each subset containing at least \(r\) elements. It is denoted by \(S_r( n , k )\) and obeys the recurrence relation. $\(\displaystyle \displaystyle S_r(n+1,k) = k S_r(n,k) + \binom{n}{r-1} S_r(n-r+1,k-1)\)$

65. Denote the n objects to partition by the integers \(\displaystyle 1, 2, …., n\). Define the reduced Stirling numbers of the second kind, denoted \(S^d(n, k)\), to be the number of ways to partition the integers \(\displaystyle 1, 2, …., n\) into k nonempty subsets such that all elements in each subset have pairwise distance at least d. That is, for any integers i and j in a given subset, it is required that \(|i - j| \geq d\). It has been shown that these numbers satisfy, $\(S^d(n, k) = S(n - d + 1, k - d + 1), n \geq k \geq d\)$

10.18.6. Bell number

66. Counts the number of partitions of a set.

67. \(B_{n+1}=\displaystyle\sum_{k=0}^{n}\left(\frac{n}{k}\right) \cdot B_{k}\)

68. \(B_{n}=\displaystyle\sum_{k=0}^{n}S(n,k)\) ,where \(S(n,k)\) is stirling number of second kind.

10.19. Discrete Math

10.19.1. General

69. \(\displaystyle ab \mod\ ac=a(b \mod\ c)\)

70. \(\displaystyle \sum_{i = 0}^n{i\cdot i!=(n + 1)! - 1}\).

71. \(\displaystyle a^k - b^k = (a - b) \cdot (a^{k - 1}b^0 + a^{k - 2}b^1 + … + a^0b^{k - 1})\)

72. \(\displaystyle \min(a + b, c) = a + \min(b, c - a)\)

73. \(|a - b| + |b - c| + |c - a| = 2 (\max (a, b, c) - \min (a, b, c))\)

74. \(\displaystyle a \cdot b \leq c \rightarrow a \leq \left \lfloor \dfrac{c}{b} \right \rfloor\) is correct

75. \(\displaystyle a \cdot b < c \rightarrow a < \left \lfloor \dfrac{c}{b} \right \rfloor\) is incorrect

76. \(\displaystyle a \cdot b \geq c \rightarrow a \geq \left \lfloor \dfrac{c}{b} \right \rfloor\) is correct

77. \(\displaystyle a \cdot b > c \rightarrow a > \left \lfloor \dfrac{c}{b} \right \rfloor\) is correct

78. For positive integer \(n\), and arbitrary real numbers \(m,x\), $\(\displaystyle \left \lfloor \dfrac{\left \lfloor x/m \right \rfloor}{n} \right \rfloor = \left \lfloor \dfrac{x}{mn} \right \rfloor\)\( \)\(\displaystyle \left \lceil \dfrac{\left \lceil x/m \right \rceil}{n} \right \rceil = \left \lceil \dfrac{x}{mn} \right \rceil\)$

79. Lagrange’s identity: $\(\displaystyle \displaystyle {\displaystyle {\begin{aligned}\left(\sum \limits_{k=1}^{n}a_{k}^{2}\right)\left(\sum \limits_{k=1}^{n}b_{k}^{2}\right)-\left(\sum\limits_{k=1}^{n}a_{k}b_{k}\right)^{2}&=\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^{n}\left(a_{i}b_{j}-a_{j}b_{i}\right)^{2}\\&={\frac {1}{2}}\sum \limits_{i=1}^{n}\sum \limits_{j=1,j\neq i}^{n}(a_{i}b_{j}-a_{j}b_{i})^{2}\end{aligned}}}\)$

80. \(\displaystyle \sum_{i = 1}^n{ia^i} = \frac{a(n a^{n + 1} - (n + 1) a^n + 1)}{(a - 1)^2}\)

81. Vieta’s formulas: Any general polynomial of degree \(n\) $\(\displaystyle p(x) = a_nx^n + a_{n - 1}x^{n - 1} + ... + a_1x + a_0\)\( (with the coefficients being real or complex numbers and \)\displaystyle a_n \neq 0\() is known by the fundamental theorem of algebra to have \)n\( (not necessarily distinct) complex roots \)r_1, r_2,…, r_n\(. \)\(\begin{cases} \text{\)r_1 + r_2 + … + r_{n - 1} + r_n = - \frac{a_{n - 1}}{a_n}\(} \\ \text{\)\displaystyle (r_1r_2 + r_1r_3 + … + r_1r_n) + (r_2r_3 + r_2r_4 + … + r_2r_n) + … + r_{n - 1}r_n = \frac{a_{n - 2}}{a_n}\(} \\\vdots\\ \text{\)r_1r_2…r_n = (-1)^n\frac{a_0}{a_n}.\(} \end{cases}\)\( Vieta’s formulas can equivalently be written as \)\(\displaystyle \sum_{1 \leq i_1 < i_2 < ...<i_k \leq n} \Bigg(\prod_{j = 1}^k{r_{i_j}}\Bigg) = (-1)^k\frac{a_{n - k}}{a_n} \)$

82. We are given n numbers \(\displaystyle a_1,a_2,…,a_n\) and our task is to find a value \(\displaystyle x\) that minimizes the sum, $\(|a_1 - x| + |a_2 - x| + ... + |a_n - x|\)\( optimal \)\displaystyle x=\( median of the array. if \)n\( is even \)x =\( [left median,right median] i.e. every number in this range will work. For minimizing \)\(\displaystyle (a_1 - x)^2 + (a_2 - x)^2 + ... + (a_n - x)^2\)\( optimal \)\displaystyle x = \dfrac{(a_1 + a_2 + … + a_n)}{ n}$

83. Given an array a of n non-negative integers. The task is to find the sum of the product of elements of all the possible subsets. It is equal to the product of \(\displaystyle (a_i + 1)\) for all \(\displaystyle a_i\)

84. Pentagonal number theorem: In mathematics, the pentagonal number theorem states that $\(\displaystyle \prod_{n = 1}^{\infty}\left ( 1 - x^n \right ) = \prod_{k = -\infty}^{\infty} \left ( -1 \right )^kx^{\frac{k(3k - 1)}{2}} = 1 + \prod_{k = 1}^{\infty}\left (-1\right )^k\left ( x^{\frac{k(3k + 1)}{2}} + x^{\frac{k(3k - 1)}{2}}\right ).\)\( In other words, \)\(\displaystyle (1 - x)(1 - x ^ 2)(1 - x^3)\cdots =1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots.\)\( The exponents \)\displaystyle 1, 2, 5, 7, 12,\cdots\( on the right hand side are given by the formula \)g_k = \frac{k(3k - 1)}{2}\( for \)\displaystyle \displaystyle k = 1, -1, 2, -2, 3, \cdots\( and are called (generalized) pentagonal numbers. It is useful to find the [partition number](https://en.wikipedia.org/wiki/Partition_(number_theory)) in \)O(n \sqrt{n})$

10.19.2. Fibonacci Number

85. \(\displaystyle F_0=0, F_1=1\) and \(\displaystyle F_n=F_{n-1}+F_{n-2}\)

86. \(\displaystyle F_n=\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-k-1}{k}\)

87. \(\displaystyle F_n=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n\)

88. \(\displaystyle \sum\limits_{i=1}^{n}F_i=F_{n+2}-1\)

89. \(\displaystyle \sum\limits_{i=0}^{n-1}F_{2i+1}=F_{2n}\)

90. \(\displaystyle \sum\limits_{i=1}^{n}F_{2i}=F_{2n+1}-1\)

91. \(\displaystyle \sum\limits_{i=1}^{n}F_{i}^{2}=F_nF_{n+1}\)

92. \(\displaystyle F_mF_{n+1}-F_{m-1}F_{n}=(-1)^nF_{m-n}\) \(\displaystyle F_{2n}=F_{n+1}^2-F_{n-1}^2=F_n(F_{n+1}+F_{n-1})\)

93. \(\displaystyle F_mF_n+F_{m-1}F_{n-1}=F_{m+n-1}\) \(\displaystyle F_mF_{n+1}+F_{m-1}F_{n}=F_{m+n}\)

94. A number is Fibonacci if and only if one or both of \(\displaystyle (5 \cdot n^2 + 4)\) or \(\displaystyle (5 \cdot n^2 - 4)\) is a perfect square

95. Every third number of the sequence is even and more generally, every \(\displaystyle \displaystyle k^{th}\) number of the sequence is a multiple of \(\displaystyle F_k\)

96. \(gcd(F_m, F_n)=F_{gcd(m, n)}\)

97. Any three consecutive Fibonacci numbers are pairwise coprime, which means that, for every n, \(gcd(F_n, F_{n+1})=gcd(F_n, F_{n+2}), gcd(F_{n+1}, F_{n+2})=1\)

98. If the members of the Fibonacci sequence are taken \(mod\) \(n\), the resulting sequence is periodic with period at most \(6n\).

10.19.3. Pythagorean Triples

99. A Pythagorean triple consists of three positive integers \(\displaystyle a, b,\) and \(\displaystyle C\), such that \(\displaystyle a^{2}+b^{2}=c^{2}\). Such a triple is commonly written \(\displaystyle (a, b, c)\)

100. Euclid’s formula is a fundamental formula for generating Pythagorean triples given an arbitrary pair of integers \(m\) and \(n\) with \(m > n > 0\). The formula states that the integers $\( a = m^{2}-n^{2}, \quad b = 2mn, \quad c = m^{2}+n^{2}\)\( form a Pythagorean triple. The triple generated by Euclid’s formula is primitive if and only if \)m\( and \)n\( are coprime and not both odd. When both \)m\( and \)n\( are odd, then \)a\(, \)b\(, and \)c\( will be even, and the triple will not be primitive; however, dividing \)a\(, \)b\(, and \)c\( by 2 will yield a primitive triple when \)m\( and \)n$ are coprime and both odd.

101. The following will generate all Pythagorean triples uniquely: $\(\displaystyle a = k\cdot \left( m^{2}-n^{2}\right), b = k\cdot\left(2mn\right), c = k\cdot \left(m^{2}+n^{2}\right)\)\( where m, n, and k are positive integers with \)m > n$, and with m and n coprime and not both odd.

102. Theorem: The number of Pythagorean triples {a,b,n} with \(max{a,b,n} = n\) is given by $\(\displaystyle \dfrac{1}{2}\left( \displaystyle\prod _{ p^{\alpha} || n}\left(2\alpha +1\right) -1\right)\)\( where the product is over all prime divisors p of the form \)4k+1\(. The notation \)\displaystyle p^{\alpha} || n\( stands for the highest exponent \)\displaystyle \alpha\( for which \)\displaystyle p^{\alpha}\( divides \)n$

Example: For \(n = 2\cdot3^{2}\cdot5^{3}\cdot7^{4}\cdot11^{5}\cdot13^{6},\) the number of Pythagorean triples with hypotenuse n is \(\displaystyle \dfrac{1}{2}\left( 7.13-1\right) =45\).

• To obtain a formula for the number of Pythagorean triples with hypotenuse less than a specific positive integer N, we may add the numbers corresponding to each \(n < N\) given by the Theorem. There is no simple way to compute this as a function of N.

10.19.4. Sum of Squares Function

103. The function is defined as \(r_{k}\left(n\right) = \left|{\left(a_{1},a_{2},…,a_{k} \right) \in \mathbf{Z^{k}} : n=a_{1}^{2}+a_{2}^{2}+…+a_{k}^{2}}\right|\)

104. The number of ways to write a natural number as sum of two squares is given by \(r_2(n)\). It is given explicitly by \(r_{2}\left(n\right) = 4\left(d_{1}\left(n\right) - d_{3}\left(n\right)\right)\) where d1(n) is the number of divisors of n which are congruent with 1 modulo 4 and d3(n) is the number of divisors of n which are congruent with 3 modulo 4.

• The prime factorization \(n = 2^{g}p_{1}^{f_{1}}p_{2}^{f_{2}}. . .q_{1}^{h_{1}}q_{2}^{h_{2}}. . . ,\) where \(\displaystyle p_{i}\) are the prime factors of the form \(\displaystyle p_{i} \equiv 1\) (mod 4), and \(q_{i}\) are the prime factors of the form \(q_{i} \equiv 3\) (mod 4) gives another formula \(r_{2}\left(n\right) = 4\left(f_{1}+1\right)\left(f_{2}+1\right)…,\) if all exponents \(h_{1}\),\(h_{2}\),… are even. If one or more \(h_{i}\) are odd, then \(r_{2}\left(n\right) = 0.\)

105. The number of ways to represent n as the sum of four squares is eight times the sum of all its divisors which are not divisible by 4, i.e. \(r_{4}\left( n \right) = 8 \displaystyle\sum _{d| n;4 \nmid d}d\) \(r{8}\left(n\right) = 16 \displaystyle\sum {d|n} \left(-1\right)^{n+d}d^{3}\)

10.20. Number Theory

10.20.1. General

106. for \(i > j\), \(\displaystyle \gcd(i, j)\) \( = \) \(\displaystyle \gcd(i -j, j)\) \(\displaystyle \leq (i -j)\)

107. \(\displaystyle \sum_{x = 1}^n \left[ d | x^k \right] = \left \lfloor\dfrac{n}{\prod_{i = 0}{p_i^{\left \lceil \dfrac{e_i}{k}\right \rceil}}}\right \rfloor\), where \(d = \prod_{i = 0}{p_i^{e_i}}\). Here, \([a | b]\) means if \(\displaystyle a\) divides \(b\) then it is \(\displaystyle 1\), otherwise it is \(0\).

108. The number of lattice points on segment \(\displaystyle (x_1,y_1)\) to \(\displaystyle (x_2,y_2)\) is \(\displaystyle \gcd(abs(x_1-x_2),abs(y_1-y_2)) + 1\)

109. \(\displaystyle (n-1)! \mod n = n -1\) if n is prime, 2 if \(n = 4\), \(0\) otherwise.

110. A number has odd number of divisors if it is perfect square

111. The sum of all divisors of a natural number n is odd if and only if \(n=2^r\cdot k^2\) where \(r\) is non-negative and \(\displaystyle \displaystyle k\) is positive integer.

112. Let \(\displaystyle a\) and \(b\) be coprime positive integers, and find integers \(\displaystyle a{\prime}\) and \(b{\prime}\) such that \(\displaystyle aa{\prime} \equiv 1 \mod b\) and \(bb{\prime} \equiv 1 \mod a\). Then the number of representations of a positive integers (n) as a non negative linear combination of \(\displaystyle a\) and \(b\) is
     \(\displaystyle \frac{n}{ab}-\Big\{\frac{b{\prime} n}{a}\Big\}-\Big\{\frac{a{\prime} n}{b}\Big\} + 1\)
     Here, \(\displaystyle {x}\) denotes the fractional part of \(\displaystyle x\).

113. \(\displaystyle \displaystyle \sum \limits_{i=1}^{a}\sum \limits_{j=1}^{b}\sum \limits_{k=1}^{c} d(i \cdot j \cdot k) = \sum \limits_{\gcd (i,j)=\gcd (j,k) = \gcd (k,i) =1} \left \lfloor \dfrac{a}{i}\right \rfloor \left \lfloor \dfrac{b}{j}\right \rfloor \left \lfloor \dfrac{c}{k} \right \rfloor\)
     Here, \(d(x) =\) number of divisors of \(\displaystyle x\).

114. Gauss’s generalization of Wilson’s theorem: Gauss proved that,
     \(\displaystyle \displaystyle \prod \limits_{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}\)
     where \(\displaystyle p\) represents an odd prime and \(\displaystyle \alpha\) a positive integer. The values of \(m\) for which the product is \(-1\) are precisely the ones where there is a primitive root modulo \(m\).

10.20.2. Divisor Function

115. \(\displaystyle \sigma_x(n)=\sum\limits_{d\vert n}^{}d^x\)

116. It is multiplicative i.e if \(\displaystyle \gcd(a, b)=1\to \sigma_x(ab)=\sigma_x(a)\sigma_x(b)\).

117. \(\displaystyle \sigma_x(n)=\prod\limits_{i=1}^{\tau}\frac{p_i^{(a_i+1)x}-1}{p_i^x-1}\)

118. Divisor Summatory Function
     - Let \(\displaystyle \sigma_0(k)\) be the number of divisors of \(\displaystyle \displaystyle k\).
     - \(D(x)=\sum\limits_{n\leq{x}}{\sigma_0(n)}\)
     - \(D(x)=\sum\limits_{k=1}^{x}\lfloor\frac{x}{k}\rfloor=2\sum\limits_{k=1}^{u}\lfloor\frac{x}{k}\rfloor-u^2\), where \(u=\sqrt{x}\)
     - \(D(n)=\) Number of increasing arithmetic progressions where \(n+1\) is the second or later term. (i.e. The last term, starting term can be any positive integer \(\displaystyle \le n\). For example, \(D(3)=5\) and there are 5 such arithmetic progressions: \(\displaystyle (1, 2, 3, 4); (2, 3, 4); (1, 4); (2, 4); (3, 4).\)

119. Let \(\displaystyle \sigma_1(k)\) be the sum of divisors of k. Then, \(\displaystyle \sum\limits_{k=1}^{n}\sigma_1(k)=\sum\limits_{k=1}^{n}{k \left\lfloor \frac{n}{k} \right\rfloor}\)

120. \(\displaystyle \prod\limits_{d\vert n}^{}d={n^{\frac{\sigma_0}{2}}}\) if \(n\) is not a perfect square, and \(=\sqrt{n} \cdot n^{\frac{\sigma_0-1}{2}}\) if \(n \) is a perfect square.

10.20.3. Euler’s Totient function

121. The function is multiplicative. This means that if \(\displaystyle \gcd(m, n) = 1\), \(\displaystyle \phi(m \cdot n) = \phi(m) \cdot \phi(n)\).

122. \(\displaystyle \phi(n) = n\prod_{p |n}(1 - \frac{1}{p} )\)

123. If p is prime and (\(k \geq 1\)), then, \(\displaystyle \phi(p^k) = p^{k - 1}(p - 1) = p^k(1 - \frac{1}{p})\)

124. \(J_k(n)\), the Jordan totient function, is the number of \(\displaystyle \displaystyle k\)-tuples of positive integers all less than or equal to n that form a coprime \(\displaystyle (k + 1)\)-tuple together with \(n\). It is a generalization of Euler’s totient, \(\displaystyle \phi(n) = J_1(n)\). and \(J_k(n) = n^k\prod_{p |n}(1 - \frac{1}{p^k})\)

125. \(\displaystyle \sum_{d|n}J_k(d) = n^k\)

126. \(\displaystyle \sum_{d|n}\phi(d) = n\)

127. \(\displaystyle \phi(n) = \sum_{d|n}\mu(d)\cdot\frac{n}{d} = n\sum_{d|n}\frac{\mu(d)}{d}\)

128. \(\displaystyle \phi(n) = \sum_{d|n}d\cdot\mu(\frac{n}{d})\)

129. \(\displaystyle \displaystyle {a}\vert{b} \to \varphi(a)\vert{\varphi(b)}\)

130. \(n\vert{\varphi(a^n - 1)}\) for \(\displaystyle a, n > 1\)

131. \(\displaystyle \varphi(mn)=\varphi(m)\varphi(n)\cdot\frac{d}{\varphi(d)}\) where \(d=gcd(m, n)\). Note the special cases \(\varphi(2m)= \begin{cases} 2\varphi(m) & ; if \, m \ even\\ \varphi(m) & ; if \, m \ odd\\ \end{cases}\)

• \(\displaystyle \varphi(n^m)=n^{m-1}\varphi(n)\)

132. \(\displaystyle \varphi(lcm(m, n)) \cdot \varphi(gcd(m, n))=\varphi(m) \cdot \varphi(n)\)
     .VS. \(lcm(m, n)\cdot gcd(m,n)=m\cdot n\)

133. \(\displaystyle \varphi(n)\) is even for \(n\geq3\). Moreover, if if \(n\) has \(r\) distinct odd prime factors, \(\displaystyle 2^r \vert \varphi(n)\)

134. \(\displaystyle \sum\limits_{d\vert{n}}^{} \frac{\mu^2(d)}{\varphi(d)}=\frac{n}{\varphi(n)}\)

135. \(\displaystyle \sum\limits_{1\leq k \leq n, \gcd(k, n)=1}k=\frac{1}{2}n\varphi(n)\) for \(n > 1\)

136. \(\displaystyle \frac{\varphi(n)}{n}=\frac{\varphi(rad(n))}{rad(n)}\) where \(rad(n)=\) \(\displaystyle \prod\limits_{p\vert n, p \, prime} p\)

137. \(\displaystyle \phi(m) \geq \log_2{m}\)

138. \(\displaystyle \phi(\phi(m))\leq\frac{m}{2}\)

139. When \(\displaystyle x \geq \log_2m\), then \(n^x\mod m=n^{\phi(m) + x\mod \phi(m)}\mod m\)

140. \(\displaystyle \sum\limits_{1\leq k\leq n, \gcd(k, n)=1}\gcd(k-1, n)=\varphi(n)d(n)\) where \(d(n)\) is number of divisors. Same equation for \(\displaystyle \gcd(a \cdot k-1, n)\) where \(\displaystyle a\) and \(n\) are coprime.

141. For every \(n\) there is at least one other integer \(m\ne n\) such that \(\displaystyle \varphi(m)=\varphi(n).\)

142. \(\displaystyle \sum\limits_{i=1}^{n} {\varphi(i) \cdot \lfloor\frac{n}{i}\rfloor=\frac{n*(n+1)}{2}}\)

143. \(\displaystyle \sum\limits_{i=1, i \% 2 \ne 0 }^{n} \varphi(i) \cdot \lfloor\frac{n}{i}\rfloor=\sum\limits_{k\geq 1}[\frac{n}{2^k}]^2\). Note that \([\, ]\) is used here to denote round operator not floor or ceil

144. \(\displaystyle \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}ij[\gcd(i, j)=1]=\sum\limits_{i=1}^{n}\varphi(i)i^2\)

145. Average of coprimes of \(n\) which are less than \(n\) is \(\displaystyle \dfrac{n}{2}\).

10.20.4. Mobius Function and Inversion

146. For any positive integer \(n\), define \(\displaystyle \mu(n)\) as the sum of the primitive \(n^{th}\) roots of unity. It has values in \(\displaystyle {-1, 0, 1}\) depending on the factorization of \(n\) into prime factors:
     - \(\displaystyle \mu(n)=1\) if \(n\) is a square-free positive integer with an even number of prime factors.
     - \(\displaystyle \mu(n)=-1\) if \(n\) is a square-free positive integer with an odd number of prime factors.
     - \(\displaystyle \mu(n)=0\) if \(n\) has a squared prime factor.

147. It is a multiplicative function.

148. \(\sum_{d|n}\mu(d) = \begin{cases} 1 & ; n=1\\ 0 & ; n > 0 \end{cases}\)

149. \(\displaystyle \displaystyle \sum\limits_{n=1}^N {\mu}^2(n) = \displaystyle \sum\limits_{n=1}^{\sqrt{N}} \mu(k) \cdot \left \lfloor \dfrac{N}{k^2} \right\rfloor\) This is also the number of square-free numbers \(\displaystyle \le n\)

150. Mobius inversion theorem: The classic version states that if g and f are arithmetic functions satisfying \(g(n) = \displaystyle \sum_{d|n}f(d) \) for every integer \(n \ge 1\) then \(g(n) = \displaystyle \sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)\) for every integer \(n \ge 1\)

151. If \(\displaystyle F(n) = \displaystyle \prod_{d|n} f(d)\), then \(\displaystyle F(n) = \displaystyle \prod_{d|n} F\left(\frac{n}{d}\right)^{\mu(d)}\)

152. \(\displaystyle \displaystyle \sum_{d|n}\mu(d)\phi(d) = \displaystyle \prod_{j=1}^K (2 - P_j)\) where \(\displaystyle p_j\) is the primes factorization of \(d\)

153. If \(\displaystyle F(n)\) is multiplicative, \(\displaystyle F \not\equiv 0\), then \(\displaystyle \displaystyle \sum_{d|n} \mu(d) f(d) = \displaystyle \prod_{i=1} (1 - f(P_i)) \cdot\) where \(\displaystyle p_i\) are primes of \(n\).

10.20.5. GCD and LCM

154. \(\displaystyle \gcd(a, 0) = a\)

155. \(\displaystyle \gcd(a, b) = \gcd(b, a \mod b)\)

156. Every common divisor of \(\displaystyle a\) and \(b\) is a divisor of \(\displaystyle \gcd(a,b)\).

157. if \(m\) is any integer, then \(\displaystyle \gcd(a + m {\cdot} b, b) = \gcd(a, b)\)

158. The gcd is a multiplicative function in the following sense: if \(\displaystyle a_1\) and \(\displaystyle a_2\) are relatively prime, then \(\displaystyle \gcd(a_1 \cdot a_2, b) = \gcd(a_1, b) \cdot \gcd(a_2,b )\).

159. \(\displaystyle \gcd(a, b){\cdot} \operatorname{lcm}(a, b) = |a{\cdot}b|\)

160. \(\displaystyle \gcd(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(a, c))\).

161. \(\displaystyle \operatorname{lcm}(a, \gcd(b, c)) = \gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(a, c))\).

162. For non-negative integers \(\displaystyle a\) and \(b\), where \(\displaystyle a\) and \(b\) are not both zero, \(\displaystyle \gcd({n^a} - 1, {n^b} - 1) = n^{\gcd(a,b)} - 1\)

163. \(\displaystyle \gcd(a, b) = \displaystyle \sum_{k|a \, \text{and} \, k|b} {\phi(k)}\)

164. \(\displaystyle \displaystyle \sum_{i=1}^n [\gcd(i, n) = k] = { \phi{\left(\frac{n}{k}\right)}}\)

165. \(\displaystyle \displaystyle \sum_{k=1}^n \gcd(k, n) = \displaystyle \sum_{d|n} d \cdot {\phi{\left(\frac{n}{d}\right)}}\)

166. \(\displaystyle \displaystyle \sum_{k=1}^n x^{\gcd(k,n)} = \displaystyle \sum_{d|n} x^d \cdot {\phi{\left(\frac{n}{d}\right)}}\)

167. \(\displaystyle \displaystyle \sum_{k=1}^n \frac{1}{\gcd(k, n)} = \displaystyle \sum_{d|n} \frac{1}{d} \cdot {\phi{\left(\frac{n}{d}\right)}} = \frac{1}{n} \displaystyle \sum_{d|n} d \cdot \phi(d)\)

168. \(\displaystyle \displaystyle \sum_{k=1}^n \frac{k}{\gcd(k, n)} = \frac{n}{2} \cdot \displaystyle \sum_{d|n} \frac{1}{d} \cdot {\phi{\left(\frac{n}{d}\right)}} = \frac{n}{2} \cdot \frac{1}{n} \cdot \displaystyle \sum_{d|n} d \cdot \phi(d)\)

169. \(\displaystyle \displaystyle \sum_{k=1}^n \frac{n}{\gcd(k, n)} = 2 * \displaystyle \sum_{k=1}^n \frac{k}{\gcd(k, n)} - 1\), for \(n > 1\)

170. \(\displaystyle \displaystyle \sum_{i=1}^n \sum_{j=1}^n [\gcd(i, j) = 1] = \displaystyle \sum_{d=1}^n \mu(d) \lfloor {\frac{n}{d} \rfloor}^2\)

171. \(\displaystyle \displaystyle \sum_{i=1}^n \displaystyle\sum_{j=1}^n \gcd(i, j) = \displaystyle \sum_{d=1}^n \phi(d) \lfloor {\frac{n}{d} \rfloor}^2\)

172. \(\displaystyle \sum_{i=1}^n \sum_{j=1}^n i \cdot j[\gcd(i, j) = 1] = \sum_{i=1}^n \phi(i)i^2\)

173. \(\displaystyle F(n) = \displaystyle \sum_{i=1}^n \displaystyle \sum_{j=1}^n \operatorname{lcm}(i, j) = \displaystyle \sum_{l=1}^n {\left(\frac{\left( 1 + \lfloor{\frac{n}{l} \rfloor} \right) \left( \lfloor{\frac{n}{l} \rfloor} \right)} {2} \right)}^2 \displaystyle \sum_{d|l} \mu(d)ld\)

174. \(\displaystyle \gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(b, c), \operatorname{lcm}(a, c)) = \operatorname{lcm}(\gcd(a, b), \gcd(b, c), \gcd(a, c))\)

175. \(\displaystyle \gcd(A_L, A_{L+1}, …, A_R) = \gcd(A_L, A_{L+1} - A_L, …, A_R - A_{R-1})\).’

176. Given n, If \(SUM = LCM(1,n) + LCM(2,n) + … + LCM(n,n)\) then SUM = \(\displaystyle \dfrac{n}{2}( \displaystyle\sum _{ d| n}\left( \phi \left( d\right) \times d\right) +1\)

10.20.6. Legendre Symbol

177. Let \(\displaystyle p\) be an odd prime number. An integer \(\displaystyle a\) is a quadratic residue modulo \(\displaystyle p\) if it is congruent to a perfect square modulo \(\displaystyle p\) and is a quadratic nonresidue modulo \(\displaystyle p\) otherwise. The Legendre symbol is a function of \(\displaystyle a\) and \(\displaystyle p\) defined as \(\displaystyle \displaystyle \left( \frac{a}{p} \right)= {\begin{cases} \,1&{\text{if }}a\ {\text{is a quadatric residue modulo }}p\ {\text{and }}\ a\ \not\equiv\ 0 {\pmod{p}},\\\;\;\,-1&{\text{if }}a\ {\text{is a non-quadaratic residue modulo }}p,\\\;\;\,0&{\text{if }}a \equiv\ 0 {\pmod{p}} \end{cases}}\)

178. Legenres’s original definition was by means of explicit formula \(\displaystyle \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \pmod{p} \ and \ \left(\frac{a}{p}\right)\in{-1,0,1}.\)

179. The Legendre symbol is periodic in its first (or top) argument: if\ \(\displaystyle a \equiv b \pmod{p}\), then \(\displaystyle \displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).\)

180. The Legendre symbol is a completely multiplicative function of its top argument: \(\displaystyle \displaystyle \left(\frac{ab}{p} \right) = \left(\frac{a}{p} \right) \left(\frac{b}{p} \right)\)

181. The Fibonacci numbers \(\displaystyle 1,1,2,3,5,8,13,21,34,55,…\) are defined by the recurrence \(\displaystyle F_1 = F_2 = 1,F_{n+1} = F_n + F_{n-1}.\) If \(p\) is a prime number then
     \(\displaystyle F_{p-\left(\frac{p}{5}\right)} \equiv 0 {\pmod{p}}, \;\;F_p \equiv \left(\frac{p}{5}\right) {\pmod{p}}.\)
     For example,
     \(\displaystyle \displaystyle\left(\frac{2}{5}\right)=-1,\;\;\;F_3=2,\;\;\;F_2=1,\)
     \(\displaystyle \displaystyle\left(\frac{3}{5}\right)=-1,\;\;\; F_4=3,\;\;\;F_3=2,\)
     \(\displaystyle \displaystyle\left(\frac{5}{5}\right)=\;\;\;0,\;\;\; F_5=5,\)
     \(\displaystyle \displaystyle\left(\frac{7}{5}\right)=-1,\;\; F_8=21,\;\;F_7=13,\)
     \(\displaystyle \displaystyle\left(\frac{11}{5}\right)=\;\;1,\;\; F_{10}=55,\;\;F_{11}=89,\)

182. Continuing from previous point, \(\displaystyle \displaystyle \left(\frac{p}{5}\right)={\text{infinite concatenation of the sequence}}\left(1,-1,-1,1,0\right) {\text{from }}p \geq 1\).

183. If \(n\) = \(\displaystyle \displaystyle k^2\) is perfect square then \(\displaystyle \left(\frac{n}{p}\right)=1\) for every odd prime except \(\displaystyle \left(\frac{n}{k}\right)=0\) if k is an odd prime.

10.21. Miscellaneous

184. \( \displaystyle a+b = a \oplus b +2(a \& b)\).

185. \( \displaystyle a + b = a \mid b + a \& b\)

186. \( \displaystyle a \oplus b = a\mid b - a \& b\)

187. \( \displaystyle k_{th}\) bit is set in \(\displaystyle x\) iff \(\displaystyle x \mod 2^{k - 1}\geq 2^k\). It comes handy when you need to look at the bits of the numbers which are pair sums or subset sums etc.

188. \(\displaystyle \displaystyle k_{th}\) bit is set in \(\displaystyle x\) iff
     \(\displaystyle x \mod 2^{k - 1} - x \mod 2^k \neq\ 0\) (\( = 2^k\) to be exact). It comes handy when you need to look at the bits of the numbers which are pair sums or subset sums etc.

189. \(n \mod 2^i = n \& (2^i - 1)\)

190. \(\displaystyle 1\oplus 2 \oplus 3 \oplus \cdots \oplus (4k - 1) = 0\) for any \(\displaystyle \displaystyle k \ge 0\)

191. Erdos Gallai Theorem: The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees
     A sequence of non-negative integers \(d_1 \geq d_2 \geq \cdots \geq d_n\) can be represented as the degree sequence of finite simple graph on \(n\) vertices if and only if \(d_1 + d_2 + \cdots + d_n\) is even and
     \(\displaystyle \sum_{i = 1}^k {d_i \leq k(k - 1)} + \sum_{i = k + 1}^n \min(d_i, k)\)
     holds for every \(\displaystyle \displaystyle k\) in \(\displaystyle 1 \leq k \leq n\).