Note: This page is no longer being updated
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!
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
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
Continued Fraction Function
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:
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
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/