How can I convert Meissel's/Lehmer's formula for prime counting to get sum of primes

Question

Legendre's formula can be very easily be generalised as mentioned here (visible after login) which is like this

${\pi}(v,p)={\pi}(v,p-1)-1.[{\pi}(v/p,p-1)-{\pi}(p-1,p-1)]$

${ \big\downarrow}$

$S(v,p)=S(v,p-1)-p[S(v/p,p-1)-S(p-1,p-1)]$

This is still $O(n^{3/4})$ algorithm

I have been trying to achieve the same with Lehmer's formula

$\pi(n)=φ(n, a)+\frac{1}{2}(b+a-2)(b-a+1)-\sum_{i=a}^{b}{\pi}(\frac{x}{p_i})-\sum_{i=a+1}^c \sum_{j=i}^{b_{i}}[{\pi}(\frac{x}{p_ip_j})-(j-1)]$

where $b = n^{1/2}, c = \pi(n^{1/3}), a = \pi(n^{1/4}), φ(n,a)-$ number of integers in [1;n] such that they are not divisible by any prime among first $a$ primes.

${ \big\downarrow}$

$S(n)=\Phi(n, a)+\frac{1}{2}(\sum b+\sum a-2)(\sum b-\sum a+1)-\sum_{i=a}^{b}p_i{S}(\frac{x}{p_i})-\sum_{i=a+1}^c \sum_{j=i}^{b_{i}}[p_ip_j{S}(\frac{x}{p_ip_j})-\sum(j-1)]$

The above expression works fine till $n=8$; after that it doesn't. I am not exactly sure what to do with $\frac{1}{2}(b+a-2)(b-a+1)$ It should not be left as is. Adding $\sum$ may not be the right way to go.

Then I realised $\frac{1}{2}(b+a-2)(b-a+1)=a+(a+1)+(a+2)+.......for (b-a) terms$

My required sum should be $\sum a+\sum (a+1)+\sum (a+2)+.......for (b-a) terms$ but even that gives an expression $(b-a)[(a^2+ab+b^2)-1]/6$ which is also giving the correct answer for $n \le 8$.

I have successfully transitioned to from $φ(n, a)$ to $\Phi(n, a)$ where $\Phi(n, a)$ - sum of integers in [1;n] such that they are not divisible by any prime among the first $a$ primes.

I guess the equivalent expression of $\frac{1}{2}(b+a-2)(b-a+1)$ should be $s'(a)+s'(a+1)+s'(a+2)+.......for (b-a)$

note: $s'(x)$ is the sum of first $x$ primes; $S(x)$ is the sum of all primes up to $x$.

PS: I am not looking for any suggestion of alternate $O(n^{2/3})$ or similar algos.
For that I have already gone through Fastest Algorithm to Compute the Sum of Primes? and more similar literature.
As a part of this question I am only looking to generalise the Meissel-Lehmer.

Answer 1

This might be a "shameless plug" but i did recently "generalize Meissel-Lehmer to count sum of the powers of primes". This was supposed to give an exposition, so it might be of help https://arxiv.org/abs/2111.15545

Answer 2

If you consult Lehmer's paper, the terms in question arise from $$P_2(x, a) = \sum_{p_a < p_i \le \frac x{p_i}} \sum_{p_i \le p_j \le \frac x{p_i}} 1 = \sum_{p_a < p_i \le b} \left\{ \pi\left(\frac x{p_i}\right) - (i-1) \right\}$$ counting semiprimes made up from primes in a certain range. The analogue would be

\begin{eqnarray*} \Phi_2(n, a) &=& \underset{p_a < p_i \le p_j \le \frac n{p_i}}{\sum\sum} p_i p_j \\ &=& \sum_{p_a < p_i \le b} p_i \left( S\left(\frac n{p_i}\right) - S(p_i - 1) \right) \\ &=& \sum_{p_a < p_i \le b} p_i \left( S\left(\frac n{p_i}\right) - S(p_i) + 1 \right) \\ &=& \sum_{p_a < p_i \le b} p_i - \sum_{p_a < p_i \le b} p_i S(p_i) + \sum_{p_a < p_i \le b} p_i S\left(\frac n{p_i}\right) \\ &=& S(b) - a - \sum_{p_a < p_i \le b} p_i S(p_i) + \sum_{p_a < p_i \le b} p_i S\left(\frac n{p_i}\right) \end{eqnarray*}