problem 46 https projecteuler netproblem46 it was proposed by christian goldbach that every odd composite number can be written as the sum of a prime and twice a square 9 7 2 12 15 7 2 22 21 3 2 32 25 7 2 32 27 19 2 22 33 31 2 12 it turns out that the conjecture was false what is the smallest odd composite that cannot be written as the sum of a prime and twice a square checks to see if a number is a prime in osqrtn a number is prime if it has exactly two factors 1 and itself isprime0 false isprime1 false isprime2 true isprime3 true isprime27 false isprime87 false isprime563 true isprime2999 true isprime67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 returns a list of first n odd composite numbers which do not follow the conjecture computenums1 5777 computenums2 5777 5993 computenums0 traceback most recent call last valueerror n must be 0 computenumsa traceback most recent call last valueerror n must be an integer computenums1 1 traceback most recent call last valueerror n must be an integer return the solution to the problem return computenums10 if name main printfsolution checks to see if a number is a prime in o sqrt n a number is prime if it has exactly two factors 1 and itself is_prime 0 false is_prime 1 false is_prime 2 true is_prime 3 true is_prime 27 false is_prime 87 false is_prime 563 true is_prime 2999 true is_prime 67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 returns a list of first n odd composite numbers which do not follow the conjecture compute_nums 1 5777 compute_nums 2 5777 5993 compute_nums 0 traceback most recent call last valueerror n must be 0 compute_nums a traceback most recent call last valueerror n must be an integer compute_nums 1 1 traceback most recent call last valueerror n must be an integer return the solution to the problem
from __future__ import annotations

import math


def is_prime(number: int) -> bool:
    

    if 1 < number < 4:
        
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        
        return False

    
    for i in range(5, int(math.sqrt(number) + 1), 6):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True


odd_composites = [num for num in range(3, 100001, 2) if not is_prime(num)]


def compute_nums(n: int) -> list[int]:
    
    if not isinstance(n, int):
        raise ValueError("n must be an integer")
    if n <= 0:
        raise ValueError("n must be >= 0")

    list_nums = []
    for num in range(len(odd_composites)):
        i = 0
        while 2 * i * i <= odd_composites[num]:
            rem = odd_composites[num] - 2 * i * i
            if is_prime(rem):
                break
            i += 1
        else:
            list_nums.append(odd_composites[num])
            if len(list_nums) == n:
                return list_nums

    return []


def solution() -> int:
    
    return compute_nums(1)[0]


if __name__ == "__main__":
    print(f"{solution() = }")