Semidivisible Numbers

For an integer $n \ge 4$, we define the lower prime square root of $n$, denoted by $\operatorname{lps}(n)$, as the largest prime $\le \sqrt n$ and the upper prime square root of $n$, $\operatorname{ups}(n)$, as the smallest prime $\ge \sqrt n$.
So, for example, $\operatorname{lps}(4) = 2 = \operatorname{ups}(4)$, $\operatorname{lps}(1000) = 31$, $\operatorname{ups}(1000) = 37$.
Let us call an integer $n \ge 4$ semidivisible, if one of $\operatorname{lps}(n)$ and $\operatorname{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 $\operatorname{lps}(15) = 3$ and $\operatorname{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 problem statement has defined two functions, lps(n) and ups(n), which represent the largest prime less than or equal to the square root of n and smallest prime greater than or equal to the square root of n, respectively. For a number to be seamless, it should be only divisible by one of the two defined functions, but not both.

This problem does not quite tackle itself to a closed-form solution and definitely needs computational assistance to get to the solution but we can discuss a strategy to handle a problem like this. Here’s a rough algorithm on how it could be computed:

– Iterate over all numbers n, from 4 to 999966663333.
– For each n, calculate lps(n) and ups(n). (Note: This would involve generating prime numbers up to √n).
– Check if n is divisible by lps(n) or ups(n), if it is divisible by only one of them, then add the number to a sum.

One may optimize this algorithm as follows:

Since LPS(n) and UPS(n) only change value when n is a perfect square, we can simply iterate through all perfect squares up to 999966663333. For each perfect square n², consider numbers from n² to (n+1)² exclusive for the LPS and UPS of n.

For each number, you have to reduce the number by the value of the relative prime (LPS or UPS) the maximum times you can, and check if it’s still divisible by the other relative prime. If that’s the case then it’s not a semidivisible number, otherwise it is a semidivisible number.

Bear in mind that you will have to handle edge cases properly, and the optimization is concerned with reducing the computation time, since even an optimized solution will take a significant amount of time, given the magnitude of the numbers. This is a computational number theory problem, which even though it has clear and natural pseudo-code, it may be hard to implement for those not familiar with competitive programming or similar fields.

This should be solved by using programming languages with appropriate data structures and algorithms designed for prime number calculations.

Please note some programming skills may be needed if you plan to solve this kind of problem. Without a programming approach, this problem would be almost impossible to solve within a reasonable amount of time.

More Answers: