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: https://mathslib.readthedocs.io/en/latest/readme.html
View it on Github here: https://github.com/igorvanloo/mathslib
Or download it from PyPi here: https://pypi.org/project/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
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
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
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 returns 0 if n is divisible by p^2, otherwise returns (-1)^k, where k is number of distinct prime factors
Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!
See Problem 76 for a more in-depth explanation, returns number of ways to partition a number goal using alist elements
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.
mobius_k_sieve returns an array where array[x] = Möbius(x)
count_k_free returns the number of integers less than or equal to n which have no cubed factor
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
Implemented using the Wikipedia page
Takes 4 inputs a1, a2, n1, n2 and computes the unique solution to the system of equations
x = a1 (mod n1)
x = a2 (mod n2)
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
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 is an algorithm for finding the shortest paths between nodes in a graph