A high-performance Python package for number theory operations, optimized for Project Euler and computational mathematics problems. From prime factorization to generating arithmetic progressions, the num_theory package is a versatile tool for students, researchers, and enthusiasts alike. It can also serve as a utility for developing solutions to Project Euler problems.
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Although there are many other packages that share similar functionalities to ours, it can take considerable time and effort to find all the utilities you need to solve Project Euler problems. This creates a need for a package that consolidates those utilities conveniently in a simple, efficient, well documented, and easy to use package. num_theory fulfils this need.
- Fast prime number generation and primality testing
- Efficient prime factorization
- Arithmetic progression calculations
- Optimized for computational challenges and competitive programming
- Simple, intuitive API design (easy-to-use function calls with clear parameters and outputs)
pip install num_theory_euler_problemsfrom num_theory import get_primes, is_prime, prime_factorization
# Generate all primes under 100
primes = get_primes(100)
# Check if a number is prime
is_prime(997) # Returns True
# Get prime factorization
factors = prime_factorization(84) # Returns [(2, 2), (3, 1), (7, 1)]Real-Life Application: Saving Money with an Arithmetic Progression Imagine you want to save money using an increasing savings plan. You start with $50 in the first month, and you decide to increase your savings by $20 each month.
You can use the arithmetic_progression function to calculate:
The amount of money saved each month for 6 months The total amount saved after 6 months The exact amount saved in the 6th month
from num_theory import arithmetic_progression
# 1. Get the savings amount for each month
monthly_savings = arithmetic_progression(a=50, d=20, n=6)
print(monthly_savings)
# Output: [50, 70, 90, 110, 130, 150]
# 2. Calculate the total amount saved in 6 months
total_savings = arithmetic_progression(a=50, d=20, n=6, compute_sum=True)
print(total_savings)
# Output: 600.0
# 3. Find the savings amount in the 6th month
sixth_month_savings = arithmetic_progression(a=50, d=20, n=6, nth_term=True)
print(sixth_month_savings)
# Output: 150| Function | Description | Example |
|---|---|---|
get_primes(n) |
Generates all primes less than n | get_primes(10) returns [2, 3, 5, 7] |
prime_factorization(n) |
Returns prime factors with their powers | prime_factorization(12) returns [(2, 2), (3, 1)] |
arithmetic_progression(a, d, n, ...) |
Handles arithmetic progression operations | arithmetic_progression(a=2, d=3, n=5) returns [2, 5, 8, 11, 14] |
is_prime(n) |
Tests primality efficiently | is_prime(17) returns True |
The num_theory package is designed to efficiently tackle computational number theory problems, making it an ideal tool for solving Project Euler challenges.
Find the largest prime factor of 600851475143.
The problem requires prime factorization of a large number, which can be computed using prime_factorization().
from num_theory import prime_factorization
num = 600851475143
factors = prime_factorization(num)
largest_prime_factor = factors[-1][0] # Extract the largest prime
print(largest_prime_factor) # Output: 6857Using num_theory, we solve this problem in milliseconds.
Find the sum of all the primes below 2,000,000.
Efficient prime generation is crucial for solving this problem. The get_primes() function allows us to quickly generate all prime numbers up to a given limit.
from num_theory import get_primes
primes_below_2M = get_primes(2_000_000)
sum_of_primes = sum(primes_below_2M)
print(sum_of_primes) # Output: 142913828922Instead of iterating through numbers manually, get_primes() efficiently generates primes and allows quick summation.
✔ Optimized performance for large numbers
✔ Simple function calls for prime-related problems
✔ Built-in utility functions eliminate redundant coding
✔ Speeds up solving computational math problems
This package complements existing Python libraries by offering a targeted collection of number theory utilities specifically for solving Project Euler problems.
Although there are other packages that provide similar functionalities, our package is special in that it consolidates various utility functions in one place to target Project Euler problems specifically.
Related Packages:
- SymPy: This does provide some symbolic mathematics, including some number theory, but isn't optimized for the computational challenges of advanced number theory.
- NumPy: The general-purpose library for numerical computations, but not specialized in number theory.
- primesieve: A highly efficient library for prime generation. This package provides similar functionalities.
| Feature | num_theory | SymPy | NumPy | primesieve |
|---|---|---|---|---|
| Focus | Number Theory | Symbolic Math | Numerical Computing | Prime Generation |
| Optimization | Project Euler | General Math | General Purpose | Prime Numbers |
| Learning Curve | Simple | Steep | Moderate | Simple |
| Speed | Fast(10-100ms) | Moderate(>100ms) | Fast(10-100ms) | Very Fast(<10ms) |
Interested in contributing? Check out the contributing guidelines . Please note that this project is released with a Code of Conduct. By contributing to this project, you agree to abide by its terms.
- Dhruv Garg
- Dominic Lam
- Thamer Aldawood
- Tingting Chen
num_theory was created by Dhruv Garg, Dominic Lam, Thamer Aldawood, Tingting Chen. It is licensed under the terms of the MIT license.
num_theory was created with cookiecutter and the py-pkgs-cookiecutter template.