Semidivisible number (source code)

= Semidivisible number

= Semidivisible
{synonym}

A <positive integer> $n$ is semidivisible when it lies strictly between the squares of consecutive <prime numbers> $p<q$,
$$
p^2<n<q^2,
$$
and is divisible by exactly one of $p$ and $q$. The strict inequalities exclude both endpoint squares. For example, $8$ is semidivisible because $2^2<8<3^2$ and only $2$ divides $8$. The <integer> $6$ lies in the same band but is divisible by both <prime numbers>, so it is excluded.

Within one band, a <divisibility> calculation can avoid testing every <integer>. Add the sums of <integer multiples> of $p$ and of $q$, then subtract twice the sum of <integer multiples> of $pq$. Each doubly divisible number was counted twice and should count zero times. Each sum is an <arithmetic progression>, and the same <inclusion-exclusion> bookkeeping works for counts instead of sums.