Project Euler Problem 234


For an integer n $\geq$ 4, we define the lower prime square root of n, denoted by lps(n), as the largest prime $\leq$ n and the upper prime square root of n, ups(n), as the smallest prime $\geq$ n.

So, for example, lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37.
Let us call an integer n 4 semidivisible, if one of lps(n) and ups(n) divides n, but not both.

The sum of the semidivisible numbers not exceeding 15 is 30, the numbers are 8, 10 and 12.
15 is not semidivisible because it is a multiple of both lps(15) = 3 and ups(15) = 5.
As a further example, the sum of the 92 semidivisible numbers up to 1000 is 34825.

What is the sum of all semidivisible numbers not exceeding 999966663333 ?


The key point to program the solution is realizing that for all i between the squares of two consecutive primes will have those primes as lower prime square root of n and upper prime square root of n respectively.

Knowing that, it is easy to determine the numbers in that range that are multiples of each prime. To only keep the semidivisble ones we just union both sets and remove the intersection.

Summing up the result of doing that for each pair of consecutive primes until the square of the lower one is higher than limit gives the correct result.

I had to do some "programming tricks" in order to get the range bound to the limit.

from itertools import takewhile, count
from CommonFunctions import find_primes_less_than
LIMIT = 999966663333
if __name__ == '__main__':
    primes = find_primes_less_than(1100000)
    result = 0
    for i in takewhile(lambda x: primes[x] ** 2 < LIMIT, count(0)):
        lower_bound = primes[i]
        lower_bound_2 = lower_bound ** 2
        upper_bound = primes[i + 1]
        upper_bound_2 = upper_bound ** 2
        set_mult_lower = set(range(lower_bound_2 + lower_bound, min(upper_bound_2 + 1, LIMIT + 1), lower_bound))
        set_mult_upper = set(range(min(upper_bound_2 - upper_bound, LIMIT - (LIMIT % upper_bound)), lower_bound_2 - 1, -upper_bound))
        result += sum((set_mult_lower | set_mult_upper) - (set_mult_lower & set_mult_upper))
    print("The result is:", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License