{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "\n",
                "# Number Theory Package Documentation\n",
                "\n",
                "Welcome to the documentation for the `num_theory` package! This package provides essential number theory functions designed for educational and analytical purposes. 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.\n",
                "\n",
                "## Installation\n",
                "\n",
                "To begin using the `num_theory` package, you can install it using the following pip command in your bash terminal:\n",
                "\n",
                "```bash\n",
                "pip install num_theory\n",
                "```\n",
                "\n",
                "Once installed, you can import the package in your Python project:\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 1,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "0.1.0\n"
                    ]
                }
            ],
            "source": [
                "import num_theory\n",
                "\n",
                "print(num_theory.__version__)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "You may also choose to import num_theory functions individually:"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 2,
            "metadata": {},
            "outputs": [],
            "source": [
                "from num_theory import prime_factorization\n",
                "from num_theory import arithmetic_progression\n",
                "from num_theory import get_primes\n",
                "from num_theory import is_prime\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## **Prime Factorization**\n",
                "\n",
                "The `prime_factorization` function breaks down a number into its prime components, which is especially useful for understanding number properties, simplifying fractions, and studying cryptographic algorithms.\n",
                "\n",
                "---\n",
                "### How It Works\n",
                "\n",
                "The function determines prime factors using the following steps:\n",
                "1. Start by dividing the number by 2 (the smallest prime) and record how many times it divides evenly.\n",
                "2. Proceed to odd numbers (3, 5, etc.) and repeat the division process, recording the results.\n",
                "3. Stop when the divisor squared exceeds the given number. If a remainder greater than 1 remains, it is also a prime factor.\n",
                "\n",
                "---\n",
                "### Parameters\n",
                "\n",
                "**n : int**  \n",
                "The integer to factorize. Must be a positive integer greater than 1.\n",
                "\n",
                "---\n",
                "### Example Usage\n",
                "\n",
                "Here are some examples to demonstrate the `prime_factorization` function:\n",
                "\n",
                "```python\n",
                "from num_theory.prime_factorization import prime_factorization\n",
                "\n",
                "# Factorizing 28\n",
                "print(prime_factorization(28))  \n",
                "# Output: [(2, 2), (7, 1)] which is equal to (2^2 + 7^1 = 28)\n",
                "\n",
                "# Factorizing 100\n",
                "print(prime_factorization(100)) \n",
                "# Output: [(2, 2), (5, 2)] which is equal to (2^2 + 5^2 = 100)\n",
                "```\n",
                "\n",
                "---\n",
                "\n",
                "### Real-Life Applications\n",
                "\n",
                "#### Application 1: Simplifying Fractions\n",
                "A student learning fractions wants to simplify the fraction `28/35`. Using the `prime_factorization` function, they can find the prime factors of both the numerator and denominator, then divide by their greatest common divisor (GCD):\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 3,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "(4, 5)\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.prime_factorization import prime_factorization\n",
                "\n",
                "def simplify_fraction(numerator, denominator):\n",
                "    num_factors = prime_factorization(numerator)\n",
                "    den_factors = prime_factorization(denominator)\n",
                "    gcd = 1\n",
                "    for factor, _ in num_factors:\n",
                "        if factor in dict(den_factors):\n",
                "            gcd *= factor\n",
                "    return numerator // gcd, denominator // gcd\n",
                "\n",
                "# Simplify 28/35\n",
                "print(simplify_fraction(28, 35))  # Output: (4, 5)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### Application 2: Finding Multiples in a Classroom Activity\n",
                "A teacher wants to create a fun activity where students identify the prime factors of numbers between 2 and 10. The `prime_factorization` function can generate the factors for any number:"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 4,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "2: [(2, 1)]\n",
                        "3: [(3, 1)]\n",
                        "4: [(2, 2)]\n",
                        "5: [(5, 1)]\n",
                        "6: [(2, 1), (3, 1)]\n",
                        "7: [(7, 1)]\n",
                        "8: [(2, 3)]\n",
                        "9: [(3, 2)]\n",
                        "10: [(2, 1), (5, 1)]\n"
                    ]
                }
            ],
            "source": [
                "# Prime factors for classroom activity\n",
                "for num in range(2, 11):\n",
                "    print(f\"{num}: {prime_factorization(num)}\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "This activity helps students visually understand how numbers break down into prime components.\n",
                "\n",
                "#### Application 3: Cryptographic Key Analysis\n",
                "A cybersecurity researcher is investigating the factorization of large integers as part of a study on cryptographic algorithms, specifically RSA encryption. The security of RSA relies on the difficulty of factoring the product of two large prime numbers. To demonstrate this concept, the researcher uses the `prime_factorization` function to:\n",
                "\n",
                "1. Factorize smaller integers to explain the concept of prime factorization to a team of non-technical stakeholders.\n",
                "2. Test and validate a set of randomly generated composite numbers to confirm their factorization as part of the cryptographic key analysis process.\n",
                "3. Analyze the distribution of prime factors in datasets of composite numbers to study patterns or anomalies that may reveal vulnerabilities in certain key-generation techniques.\n",
                "\n",
                "This function serves as an educational tool and a basic analysis tool for smaller numbers, helping the researcher communicate and validate fundamental cryptographic concepts.\n",
                "\n",
                "### Example Usage"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 5,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "[(2, 2), (7, 1)]\n",
                        "[(2, 2), (5, 2)]\n",
                        "[(5, 1), (7, 1), (13, 1), (29, 1)]\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.prime_factorization import prime_factorization\n",
                "\n",
                "# Example 1: Factorizing 28\n",
                "print(prime_factorization(28))  # Output: [(2, 2), (7, 1)]\n",
                "\n",
                "# Example 2: Factorizing 100\n",
                "print(prime_factorization(100))  # Output: [(2, 2), (5, 2)]\n",
                "\n",
                "# Example 3: Factorizing 13195\n",
                "print(prime_factorization(13195))  # Output: [(5, 1), (7, 1), (13, 1), (29, 1)]"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "---\n",
                "### Additional Notes\n",
                "\n",
                "1. **Edge Cases**:\n",
                "   - Input validation ensures non-integers and integers <= 1 raise an error.\n",
                "\n",
                "2. **Performance**:\n",
                "   - Efficient for small numbers.\n",
                "   - May be slow for very large numbers due to the use of trial division.\n",
                "   - This algorithm has a time complexity of O(√n) and a space complexity of O(log(n)).\n",
                "\n",
                "\n",
                "3. **Future Improvements**:\n",
                "   - Implement more advanced factorization algorithms for better performance on large inputs."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## **Get Primes**\n",
                "\n",
                "The `get_primes` function generates a list of all prime numbers below a given integer. This is ideal for applications like solving Project Euler problems, creating hashing methods, and studying prime number distributions.\n",
                "\n",
                "---\n",
                "### How it works\n",
                "The get_primes() function uses a custom Sieve of Eratosthenes algorithm to retrieve the list of prime numbers. It does this in the following steps:\n",
                "1. Create a list of booleans of size n.\n",
                "2. Initialize all booleans in the list as True.\n",
                "3. Starting from 2, iterate in ascending order through all numbers under n.\n",
                "4. In our boolean list, assign the index corresponding to every number's multiples as False (non-prime).\n",
                "5. Return a list containing only prime numbers.\n",
                "\n",
                "![Sieve of Eratosthenes Animation](https://upload.wikimedia.org/wikipedia/commons/9/94/Animation_Sieve_of_Eratosth.gif \"Sieve of Eratosthenes Animation\")\n",
                "\n",
                "---\n",
                "\n",
                "### Parameters\n",
                "\n",
                "**n : int**  \n",
                "The number to find primes under. Can be any non-negative number.\n",
                "\n",
                "---\n",
                "### Real-World Applications\n",
                "\n",
                "#### Application 1: Generating Prime-Based Security Codes\n",
                "A small business wants to generate unique security codes using prime numbers for encrypting customer IDs. Using the `get_primes` function, they generate primes up to a certain number and select them as secure keys:\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 6,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.get_primes import get_primes\n",
                "\n",
                "# Generate prime-based security codes\n",
                "security_codes = get_primes(100)\n",
                "print(security_codes) "
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### Application 2: Project Euler's prime numbers sum.\n",
                "\n",
                "Project Euler's 10th problem states: \"Find the sum of all the primes below two million.\" Using our `get_primes()` function trivializes this problem, as we can simply use Python's built-in `sum()` function along with our function, passing 2,000,000 as the argument. Our function will retrieve the list of all primes under 2,000,000, and `sum()` will calculate their sum to obtain the answer."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 7,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "142913828922\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.get_primes import get_primes\n",
                "\n",
                "# Sum of all primes below 2,000,000\n",
                "print(sum(get_primes(2000000)))"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### Application 3: Hashing with Primes\n",
                "\n",
                "Suppose you want to create a simple hash function that converts a given number into a value within the range of 0 to 255. You can achieve this by using the modulo (`%`) operation along with the sum of the output from our `get_primes()` function to create a straightforward hashing algorithm. However, please note that this hashing function is extremely rudimentary and not suitable for most practical applications, it is used here solely as an easy-to-understand example."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 8,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "201\n",
                        "58\n"
                    ]
                }
            ],
            "source": [
                "def simple_hash(num: int) -> int:\n",
                "    from num_theory.get_primes import get_primes\n",
                "    return sum(get_primes(num)) % 256\n",
                "\n",
                "print(simple_hash(2025))\n",
                "print(simple_hash(1999))"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "---\n",
                "#### Additional notes\n",
                "\n",
                "1. Edge cases:\n",
                "    - This function will return an empty list for negative numbers, 0, and 1.\n",
                "    - This function accepts fractional numbers but floors them so `get_primes(10.8)` is equivalent to `get_primes(10)`\n",
                "2. Performance:\n",
                "   - This algorithm has a time complexity of O(n ⋅ log(log(n))) and a space complexity of O(n).\n",
                "   - The get_primes() function uses a custom Sieve of Eratosthenes algorithm to retrieve the list of prime numbers. It does this by initializing a list of all number under n, then it iterates through all of them from the bottom to the top and assigns their multiples as non-primes. Once done, it leaves you with a list containing only prime numbers under n. \n",
                "3. Future improvements:\n",
                "   - This function's utility could be improved through additional functionalities that can be selected through parameters (e.g., return the list reversed or return just the largest prime under n).\n",
                "   - The algorithm can be further optimized using Segmented sieve."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## **Arithmetic Progression**\n",
                "\n",
                "The `arithmetic_progression` function calculates terms, sums, or sequences of arithmetic progressions. This can model savings plans, salary increments, and more.\n",
                "\n",
                "---\n",
                "### How it works\n",
                "Default:\n",
                "1. Iterate through n steps.\n",
                "2. For each step, multiply the number of steps taken with the difference between terms and add it to the first term.\n",
                "3. Append each calculated term to a list and return the list when finished.\n",
                "\n",
                "Compute sum:\n",
                "1. Calculate the sum of n terms directly using the following formula: ![Compute Sum Formula](img/Compute_sum_formula.png)\n",
                "\n",
                "Nth term:\n",
                "1. Calculate the nth term directly using the following formula:   ![nth term Formula](img/nth_term_formula.png)\n",
                "\n",
                "---\n",
                "### Parameters\n",
                "\n",
                "**a : float**  \n",
                "    The first term of the AP.  \n",
                "**d : float**  \n",
                "    The common difference between consecutive terms.  \n",
                "**n : int**  \n",
                "    The number of terms, the term to compute, or the term index.  \n",
                "**compute_sum : bool, optional**  \n",
                "    If True, computes the sum of the first n terms. Default is False.  \n",
                "**nth_term : bool, optional**   \n",
                "    If True, computes the nth term of the AP instead of generating terms. Default is False.  \n",
                "\n",
                "---\n",
                "### Example 1: Saving for a Vacation\n",
                "\n",
                "You start saving $100 in the first month, increasing by $10 each month. Let’s calculate:\n",
                "\n",
                "1. Total savings after 12 months.\n",
                "2. Amount saved in the 12th month.\n",
                "3. The savings progression."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 9,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "Total savings after 12 months: $1,860.0\n",
                        "Amount saved in the 12th month: $210\n",
                        "[100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210]\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.arithmetic_progression import arithmetic_progression\n",
                "\n",
                "# Total savings after 12 months\n",
                "print(f\"Total savings after 12 months: ${arithmetic_progression(a=100, d=10, n=12, compute_sum=True):,}\") \n",
                "\n",
                "# Amount saved in the 12th month\n",
                "print(f\"Amount saved in the 12th month: ${arithmetic_progression(a=100, d=10, n=12, nth_term=True):,}\") \n",
                "\n",
                "# Savings progression\n",
                "print(arithmetic_progression(a=100, d=10, n=12))"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### Example 2: Salary Increment\n",
                "\n",
                "Your starting salary is $50,000, with an annual increment of $3,000. Let’s calculate:\n",
                "\n",
                "1. Salary in the 5th year.\n",
                "2. Total earnings over 5 years.\n",
                "3. Salary progression over 5 years."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 10,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "Salary in the 5th year: $62,000\n",
                        "Total earnings over 5 years: $280,000.0\n",
                        "[50000, 53000, 56000, 59000, 62000]\n"
                    ]
                }
            ],
            "source": [
                "# Salary in the 5th year\n",
                "print(f\"Salary in the 5th year: ${arithmetic_progression(a=50000, d=3000, n=5, nth_term=True):,}\") \n",
                "\n",
                "# Total earnings over 5 years\n",
                "print(f\"Total earnings over 5 years: ${arithmetic_progression(a=50000, d=3000, n=5, compute_sum=True):,}\")\n",
                "\n",
                "# Salary progression over 5 years\n",
                "print(arithmetic_progression(a=50000, d=3000, n=5))  # Output: [50000, 53000, ..., 62000]"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### Additional notes\n",
                "\n",
                "1. Edge cases:\n",
                "    - This function will raise an error if any of its integer parameters are fed with non-integers.\n",
                "    - This function will also raise an error if the number of terms is a negative number.\n",
                "2. Performance:\n",
                "   - This function has a time complexity of O(n) and a space complexity of O(n).\n",
                "   - compute_sum has a time complexity of O(1) and a space complexity of O(1).\n",
                "   - nth_term has a time complexity of O(1) and a space complexity of O(1).\n",
                "3. Future improvements:\n",
                "   - This function's interpretability with large values of n can be enhanced using visualizations such as line charts.\n",
                "   - Additional options to calculate exponential growth and other non linear progressions (e.g., geometric, harmonic, etc.)."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## **Is Prime**\n",
                "\n",
                "The `is_prime` function provides a simple, efficient, and reliable way to determine whether a given integer is prime. This lightweight utility is perfect for educational purposes, mathematical explorations, and real-world applications requiring prime number checks.\n",
                "\n",
                "---\n",
                "### How it works\n",
                "1. Return True if n is 2, return False if n is an even number greater than 2.\n",
                "2. Check odd divisors from 3 to sqrt(n) for any that evenly divide n.\n",
                "3. Return True if no divisors are found.\n",
                "   \n",
                "---\n",
                "### Parameters\n",
                "\n",
                "**n : int**  \n",
                "    The number to check for primality. Must be a positive integer greater than 1.  \n",
                "    \n",
                "---\n",
                "\n",
                "### Example Usage\n",
                "```python\n",
                "from num_theory.is_prime import is_prime\n",
                "\n",
                "print(is_prime(7))  # True\n",
                "print(is_prime(10))  # False\n",
                "```\n",
                "\n",
                "---\n",
                "### Application 1:  Cryptography & Security PIN Validation\n",
                "\n",
                "In cryptography, prime numbers are widely used for secure encryption. A system might validate that a chosen PIN is prime before accepting it as secure.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 11,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "PIN 53 is accepted as it's a prime number—secure and unique!\n"
                    ]
                }
            ],
            "source": [
                "from num_theory.is_prime import is_prime\n",
                "pin = 53\n",
                "if is_prime(pin):\n",
                "    print(f\"PIN {pin} is accepted as it's a prime number—secure and unique!\")\n",
                "else:\n",
                "    print(f\"PIN {pin} is rejected. Please choose a prime number.\")\n",
                "# Output: PIN 53 is accepted as it's a prime number—secure and unique!\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### Application 2:  Unique Classroom Groups\n",
                "\n",
                "A teacher wants to divide students into groups of a size that is prime, ensuring groups are small and effective."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 12,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "Group size 7 works! It's prime, so students will interact uniquely.\n"
                    ]
                }
            ],
            "source": [
                "group_size = 7\n",
                "if is_prime(group_size):\n",
                "    print(f\"Group size {group_size} works! It's prime, so students will interact uniquely.\")\n",
                "else:\n",
                "    print(f\"Group size {group_size} isn't prime. Let's try a different size.\")\n",
                "# Output: Group size 7 works! It's prime, so students will interact uniquely."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### Application 3: Generate RSA Keys\n",
                "\n",
                "In encryption applications, generating an RSA key pair (public and private keys) requires two large prime numbers and modulus calculations. This code uses `is_prime` to verify the generated prime numbers and constructs the RSA public and private keys, showcasing a practical application in a real-world encryption system."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 13,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "RSA Keys:\n",
                        "Public Key: (14315, 62429)\n",
                        "Private Key: (40511, 62429)\n"
                    ]
                }
            ],
            "source": [
                "import random\n",
                "from math import gcd\n",
                "\n",
                "# Generate large primes\n",
                "def generate_large_prime(start, end):\n",
                "    while True:\n",
                "        n = random.randint(start, end)\n",
                "        if is_prime(n):\n",
                "            return n\n",
                "\n",
                "# Generate RSA keys\n",
                "def generate_rsa_keys():\n",
                "    p = generate_large_prime(100, 999)\n",
                "    q = generate_large_prime(100, 999)\n",
                "    n = p * q\n",
                "    phi = (p - 1) * (q - 1)\n",
                "\n",
                "    # Choose e such that 1 < e < phi and gcd(e, phi) = 1\n",
                "    e = random.choice([x for x in range(2, phi) if gcd(x, phi) == 1])\n",
                "\n",
                "    # Calculate d such that (d * e) % phi = 1\n",
                "    d = pow(e, -1, phi)\n",
                "    return {\"public_key\": (e, n), \"private_key\": (d, n)}\n",
                "\n",
                "# Generate and display RSA keys\n",
                "keys = generate_rsa_keys()\n",
                "print(\"RSA Keys:\")\n",
                "print(f\"Public Key: {keys['public_key']}\")\n",
                "print(f\"Private Key: {keys['private_key']}\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### Additional notes\n",
                "\n",
                "1. Edge cases:\n",
                "    - This function will raise an error if the input is not a positive integer greater than 1.\n",
                "2. Performance:\n",
                "   - This function has a time complexity of O(√n) and a space complexity of O(1).\n",
                "3. Future improvements:\n",
                "   - Potential to handle list inputs by applying the same function iteratively to each item and return a boolean list telling which numbers are prime.\n",
                "   - Cache results in case repeated inputs are given."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "---\n",
                "\n",
                "## Summary\n",
                "\n",
                "The `num_theory` package offers practical and educational tools for number theory applications. From analyzing cryptographic keys to modeling real-world scenarios like savings plans, this package provides:\n",
                "\n",
                "- **Prime factorization** for understanding number properties.\n",
                "- **Prime generation** for problem-solving and hashing.\n",
                "- **Prime checking** for quick validation of numbers.\n",
                "- **Arithmetic progressions** for financial and mathematical modeling.\n",
                "\n",
                "Explore the power of number theory with `num_theory`!"
            ]
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "test_env",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.13.1"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 4
}