# Essential Functions

This page has become very long, hence I decide to make my own package with all of my essential functions. The package will contain all of the below functions and more with even more details!

View it on Github here: https://github.com/igorvanloo/mathslib

Some of these I have come up with myself, some I have copied and modified from other sources, but I make sure that I can understand the coding and logic before I use it.

For the full list of all the functions I use often you can see my Github Essential Functions

# Number Theory Functions

## Prime Related

### Prime Generator

Mabye the most important function you need for Project Euler?

Source - https://www.nayuki.io/page/project-euler-solutions another inspiration, a lot of useful functions here to learn from

Sieve of Eratosthenes

### Prime Counting Function

Returns an array where array[x] = number of primes ≤ x. See Problem 609 for a more in depth explanation. If you just want the primepi for a few numbers I recommend the SymPy primepi function

### Fermat Primality Test

Implementation of Fermat Primality Test. You can choose how many test's to use, from my experience 5 tests is usually enough for all the Project Euler problems i've done!

### Miller-Rabin/Miller Primality Test

Implementation of the Miller-Rabin Primality Test, It has the option of using the Miller-Rabin test with a set number of test cases, and also the Miller Primality test which is guaranteed to find a correct answer if n < 3,317,044,064,679,887,385,961,981

## Fibonacci Related

### Fibonacci numbers Generator

Please refer to Matrix Form of Fibonacci and Fast Exponentiation to understand whats going on

## Other topics

### Divisors Function

This function is quite fast but you can make it faster if you would like using this page

### Euler Totient Function

Euler's Totient Function counts the positive integers up to a given integer n that are relatively prime to n

### Möbius Function

Möbius function returns 0 if n is divisible by p^2, otherwise returns (-1)^k, where k is number of distinct prime factors

### Legendre's Formula

Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!

### Partition Function

See Problem 76 for a more in-depth explanation, returns number of ways to partition a number goal using alist elements

### Primitive Pythagorean Triplet Generator

See Problem 9 for a more in-depth explanation on the theory

### k-smooth numbers

Takes 2 inputs maxprime and limit and returns a sorted list of all k-smooth numbers less than the given limit where k = maxprime.

The algorithm is very simple just keep adding new numbers to a list by multiplying them with all the other numbers in the list.

### Generalized Mobius Sieve & count k power-free

I re-defined the Mobius function: Both takes 2 inputs n and k.

### k-powerful integers

Take 3 inputs k, upper_bound, count.

The function returns all k-powerful integers less than upper_bound if count = False or if count = True it returns the number of k-powerful integers less than upper_bound

It is inspired by: https://rosettacode.org/wiki/Powerful_numbers#Python

### Chinese Remainder Theorem

Takes 4 inputs a1, a2, n1, n2 and computes the unique solution to the system of equations

### Tonelli-Shanks Algorithm

Legendre Symbol and Tonelli–Shanks algorithm are implemented below.

These are used to solve for r in a congruence of the form r^2 ≡ n (mod p)

The source for the algorithm is here: https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/

# Graph Theory Algorithms

### Prims Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

Implemented directly from wikipedia, see Problem 107 for more in-depth explanation

### Dijkstra's algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph

# Simple Functions

### LCM Function

Basically continuously using the gcd method to find lcm between a list of numbers