Essential Functions

This page has become very long, hence I decide to make my own package with all of my essential functions, some of which are not included on this page.

You may read the full documentation here:

View it on Github here:

Or download it from PyPi here:

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 - another inspiration, a lot of useful functions here to learn from

Sieve of Eratosthenes

Prime Factors Function

Is Prime Function

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

Source -

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

Continued Fraction Function

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.

  1. mobius_k_sieve returns an array where array[x] = Möbius(x)

  2. count_k_free returns the number of integers less than or equal to n which have no cubed factor

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:

Chinese Remainder Theorem

Implemented using the Wikipedia page

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

  1. x = a1 (mod n1)

  2. x = a2 (mod n2)

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:

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

Base changer Function

Sum of Digits Function

LCM Function

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