Inverse modulo p (Python)

2013-01-31T23:41:21-08:00

Python recipe 576737 by Justin Shaw (mod, modulo, number, prime, theory). Revision 4.

Very rarely it is necessary to find the multiplicative inverse of a number in the ring of integers modulo p. Thie recipe handles those rare cases. That is, given x, an integer, and p the modulus, we seek a integer x^-1 such that x * x^-1 = 1 mod p. For example 38 is the inverse of 8 modulo 101 since 38 * 8 = 304 = 1 mod 101. The inverse only exists when a and p are relatively prime.

Simple graph algorithms with a modular design (Python)

2011-04-21T13:40:32-07:00

Python recipe 577668 by jimmy2times (algorithms, breadth, depth, directed, first, graph, object, oriented, python, search, theory, undirected, visit). Revision 7.

The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.

A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex. This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).

Any valid class of graph must implement the interface defined by AbstractGraph.

A generic search algorithm takes as input a graph, source and target vertices and a queue. A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.

Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).

primeList (Python)

2011-11-05T23:42:37-07:00

Python recipe 577935 by Alexander James Wallar (list, numbers, prime, primelist, primes, theory). Revision 3.

This module returns all the prime numbers strictly less than n. For this code to print out all of the primes n inclusive, in the range, n+1 must be substituted for n.

Evolutionary Algorithm (Generation of Prime Numbers) (Python)

2011-11-27T06:45:00-08:00

Python recipe 577964 by Alexander James Wallar (algorithm, example, genetic, genetic_algorithm, genetic_algorithms, list, number, of, prime, primelist, primes, theory).

This is an evolutionary algorithm that returns a random list of prime numbers. This code is highly inefficient for a reason. This algorithm is more of a proof of concept that if a prime was a heritable trait, it would not be a desired one.

Parameters:

isPrime --> n: number to check if it is prime allPrimes --> n: size of list of random primes, m: the primes in the list will be between 0 and m

Most viewed recipes tagged "theory"

Inverse modulo p (Python)

Simple graph algorithms with a modular design (Python)

primeList (Python)

Evolutionary Algorithm (Generation of Prime Numbers) (Python)