search

Post

Modular Arithmetic Mon, May 11, 2020 02:00 CEST

Positional notation. An arbitrary precision integer on a computer is represented as a list of digits (limbs). They are just bigger. Today’s computers can hold 64 bits per limb. Modular arithmetic consists in applying addition and multiplication to integers modulo a certain number \(n\). Given an implementation of addition, multiplication, and division over the integers, we can emulate addition or multiplication modulo \(n\) by performing the corresponding operation on integers then taking the result modulo \(n\).

The Drunkard's Pilgrimage
The Drunkard's Walk Wed, Oct 17, 2018 02:00 CEST

A drunkard is zigzagging home. At every steps forward (or backward) he is making, he also moves \(1\) step to the left with probability \(p\) and \(1\) step to the right otherwise. He starts \(i\) steps to the right of a river. What is the expected number of steps forward before he falls into the river?

Two
Sums of geometric series Sun, Jul 23, 2017 02:00 CEST

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for \(n\) hyperplanes in \(d\) dimensions only need space proportional to \(n^d\).

\[ \sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1). \]

Ulam's Spiral
Infinite Number of Primes Sat, Jul 22, 2017 02:00 CEST

The erroneous proof I hear most often is: Suppose \(P\) is a finite set that contains all the primes, then \(p^* = 1 + \prod_{p \in P} p\) is prime. Indeed, the flaw is that \(p^*\) is not necessarily prime but rather must be a multiple of some prime not in \(P\).

Recurrences Sat, Apr 22, 2017 02:00 CEST

Theorem

Let \(a \in \mathbb{N} \), \(t < a \in \mathbb{N} \), and \(b \in \mathbb{R}\). Defining \(A_t\)to be some real number and

$$ A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N}, $$

then

$$ A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}. $$

Converging series Fri, Apr 21, 2017 02:00 CEST

Let \(-1 < x < 1\),

$$ 1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}. $$

Polynomial-time approximation schemes Wed, May 4, 2016 02:00 CEST

PTAS

\((1\pm\varepsilon)\)-approximation with complexity \(O(n^{f(\varepsilon)})\).

Equivalence of 3SUM problems Wed, Apr 27, 2016 02:00 CEST

Are different versions of the 3SUM problem equivalent?

Log Log Log Thu, Apr 14, 2016 02:00 CEST

Theorem

$$ \frac{\log n}{\log \log n}! = \Theta(n) $$