ubergarm

/

Hunyuan-A13B-Instruct-GGUF

like 12

Prompt

## Task
Write an efficient python program to search for perfect numbers.

## Background
In number theory, a perfect number is a positive integer that is equal
to the sum of its positive proper divisors, that is, divisors excluding
the number itself. For instance, 6 has proper divisors 1, 2 and 3,
and 1 + 2 + 3 = 6, so 6 is a perfect number. The next perfect number is
28, since 1 + 2 + 4 + 7 + 14 = 28.

The first four perfect numbers are 6, 28, 496 and 8128.

## Implmentation Details
Keep these implementation details in mind while developing the code:

1. Specify static types where applicable.
2. Use clear comments in a pythonic style.
3. Consider speed optimizations and use an efficient algorithm.
4. Use simple logging to display the results as they are discovered.
5. Finally, provide usage example for this CLI tool application.

Output code:

import logging
import sys

# Configure logging to display informational messages
logging.basicConfig(level=logging.INFO, format='%(levelname)s: %(message)s')

def is_prime(n: int) -> bool:
    """Check if a number is a prime using the Miller-Rabin primality test.

    This test is efficient and deterministic for numbers up to 2^64 when using the bases [2, 3, 5, 7].
    """
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False
    # Write n-1 as d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    # Witness loop using bases 2, 3, 5, 7 (sufficient for n < 2^64)
    for a in [2, 3, 5, 7]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def lucas_lehmer(p: int) -> bool:
    """Check if 2^p - 1 is a Mersenne prime using the Lucas-Lehmer primality test.

    Args:
        p: A prime number.

    Returns:
        True if 2^p - 1 is a Mersenne prime, False otherwise.
    """
    if p == 2:
        return True
    m = (1 << p) - 1  # Equivalent to 2^p - 1
    s = 4
    for _ in range(p - 2):
        s = (s * s - 2) % m
    return s == 0

def generate_primes():
    """Generator that yields prime numbers in ascending order."""
    candidate = 2
    while True:
        if is_prime(candidate):
            yield candidate
        # Increment by 1 for candidate=2, then by 2 for subsequent candidates (skip even numbers)
        candidate += 1 if candidate == 2 else 2

def find_perfect_numbers(limit: int) -> None:
    """Find the first 'limit' even perfect numbers using the Euclid-Euler theorem."""
    count = 0
    for p in generate_primes():
        logging.info(f"Checking exponent p={p}...")
        if lucas_lehmer(p):
            m = (1 << p) - 1
            perfect_number = (1 << (p - 1)) * m
            count += 1
            logging.info(f"Found perfect number: {perfect_number}")
            if count == limit:
                logging.info(f"Found the first {limit} perfect numbers.")
                return

def main():
    """Main function to handle user input and execute the perfect number search."""
    try:
        limit = int(input("Enter the number of perfect numbers to find: "))
        if limit <= 0:
            raise ValueError("Limit must be a positive integer.")
    except ValueError as e:
        logging.error(f"Invalid input: {e}")
        sys.exit(1)

    find_perfect_numbers(limit)

if __name__ == "__main__":
    main()

Output without any editing:

$ python perfect-hunyuan.py
Enter the number of perfect numbers to find: 10
INFO: Checking exponent p=2...
INFO: Found perfect number: 6
INFO: Checking exponent p=3...
INFO: Found perfect number: 28
INFO: Checking exponent p=5...
INFO: Found perfect number: 496
INFO: Checking exponent p=7...
INFO: Found perfect number: 8128
INFO: Checking exponent p=11...
INFO: Checking exponent p=13...
INFO: Found perfect number: 33550336
INFO: Checking exponent p=17...
INFO: Found perfect number: 8589869056
INFO: Checking exponent p=19...
INFO: Found perfect number: 137438691328
INFO: Checking exponent p=23...
INFO: Checking exponent p=29...
INFO: Checking exponent p=31...
INFO: Found perfect number: 2305843008139952128
INFO: Checking exponent p=37...
INFO: Checking exponent p=41...
INFO: Checking exponent p=43...
INFO: Checking exponent p=47...
INFO: Checking exponent p=53...
INFO: Checking exponent p=59...
INFO: Checking exponent p=61...
INFO: Found perfect number: 2658455991569831744654692615953842176
INFO: Checking exponent p=67...
INFO: Checking exponent p=71...
INFO: Checking exponent p=73...
INFO: Checking exponent p=79...
INFO: Checking exponent p=83...
INFO: Checking exponent p=89...
INFO: Found perfect number: 191561942608236107294793378084303638130997321548169216
INFO: Found the first 10 perfect numbers.