what is the smallest odd composite that cannot be written as the sum of a prime and twice a square? in matlab

Here's the Matlab code to find the smallest odd composite number that cannot be written as the sum of a prime and twice a square:

main.m
function result = smallest_odd_composite()
    n = 3; % start with the first odd composite number 
    primes = primes(n); % generate all primes less than or equal to n
    while true
        if isprime(n) % if n itself is prime, move to the next number
            n = n + 2;
            primes = primes(primes < n); % update the list of primes
            continue;
        end
        can_be_written = false; % assume that n cannot be written in the form p + 2k^2
        for p = primes
            k = sqrt((n - p) / 2);
            if k == floor(k) % check if (n - p)/2 is a perfect square
                can_be_written = true; % if so, n can be written in the form p + 2k^2
                break;
            end
        end
        if ~can_be_written % if n cannot be written in the form p + 2k^2, we have our answer
            result = n;
            return;
        end
        n = n + 2; % move to the next odd composite number
    end
end
952 chars
25 lines

The function primes(n) returns an array of all prime numbers less than or equal to n. We start with n = 3, the first odd composite number, and check if it can be written in the form p + 2k^2 for some prime p and integer k. We generate all primes less than or equal to n and loop over them to check if (n - p)/2 is a perfect square. If we find a prime p and integer k such that n = p + 2k^2, we move to the next odd composite number n and try again. If we exhaust all primes less than or equal to n without finding a way to write n in the desired form, we have found the smallest odd composite that cannot be written in that form. This is returned as result.

To run the function, simply call smallest_odd_composite() and it will return the answer.

related categories

gistlibby LogSnag