Solving a recurrence relation for the prime counting function?

Question

I have found some number sequence $c_n = 1+b_n$ for $n \ge 0$, where $b_n = $ A307977(n). I am trying to solve the following recurrence relation for the prime counting function:

$$\forall n \ge 3: \pi(n) = \frac{1}{n-2} \sum_{k=0}^{n-1} \pi(k) c_{n-1-k}$$

in terms of the sequence $c_n$, where $\pi(n)=0$ for $n<2$ and $\pi(2)=1$. (I can prove that the recurrence formula holds, but I can not solve the recurrence formula for $\pi(n)$ on the left and $c_k$-s only on the right as suggested in the SageMath code:

Here is for $n \ge 3$ the sequence $(n-2)! \cdot \pi(n)$ computed with SageMath:

3 c_0
4 c_0^2 + c_1
5 c_0^3 + 3*c_0*c_1 + 2*c_2
6 c_0^4 + 6*c_0^2*c_1 + 3*c_1^2 + 8*c_0*c_2 + 6*c_3
7 c_0^5 + 10*c_0^3*c_1 + 15*c_0*c_1^2 + 20*c_0^2*c_2 + 20*c_1*c_2 + 30*c_0*c_3 + 24*c_4
8 c_0^6 + 15*c_0^4*c_1 + 45*c_0^2*c_1^2 + 40*c_0^3*c_2 + 15*c_1^3 + 120*c_0*c_1*c_2 + 90*c_0^2*c_3 + 40*c_2^2 + 90*c_1*c_3 + 144*c_0*c_4 + 120*c_5
9 c_0^7 + 21*c_0^5*c_1 + 105*c_0^3*c_1^2 + 70*c_0^4*c_2 + 105*c_0*c_1^3 + 420*c_0^2*c_1*c_2 + 210*c_0^3*c_3 + 210*c_1^2*c_2 + 280*c_0*c_2^2 + 630*c_0*c_1*c_3 + 504*c_0^2*c_4 + 420*c_2*c_3 + 504*c_1*c_4 + 840*c_0*c_5 + 720*c_6

Q1) Is it possible to give an explicit formula for $\pi(n)$ in terms of $c_k$ only?

Q2) Are there other known recursive formulas for the prime counting function in the literature?

(I tried to search for some of these coefficients in OEIS but I can not see the general pattern, if there is one, for all coefficients of these polynomials in the $c_n$.)

Thanks for your help!

Answer 1

It turns out to be more straightforward than I expected.

Let $C(z) = \sum_{i \ge 0} c_i z^i$ be the g.f. for $c_i$, excluding $c_{-1}$ since that doesn't show up in your recurrence.

Starting with $$\forall n \ge 3: \pi(n) = \frac{1}{n-2} \sum_{k=0}^{n-1} \pi(k) c_{n-1-k}$$ we construct $\Pi(z)$, the g.f. of $\pi(n)$:

\begin{eqnarray*}\Pi(z) &=& z^2 + \sum_{n \ge 3}\pi(n)z^n \\ z^{-2} \Pi(z) &=& 1 + \sum_{n \ge 3}\pi(n)z^{n-2} \\ &=& 1 + \sum_{n \ge 3} \frac{z^{n-2}}{n-2} \sum_{k=0}^{n-1} \pi(k) c_{n-1-k} \\ &=& 1 + \sum_{n \ge 3} \frac{z^{n-2}}{n-2} [z^{n-1}] \left(\Pi(z) C(z)\right) \\ &=& 1 + \int z^{-2} \Pi(z) C(z) \textrm{d}z \\ \end{eqnarray*} where the constant of integration must be zero. Differentiate both sides and rearrange to get a logarithmic derivative:

\begin{eqnarray*} \frac{\frac{\textrm{d}}{\textrm{d}z} z^{-2} \Pi(z)}{z^{-2} \Pi(z)} &=& C(z) \\ \frac{\textrm{d}}{\textrm{d}z} \log \left(z^{-2} \Pi(z)\right) &=& C(z) \\ \Pi(z) &=& z^2 \exp \int C(z) \textrm{d}z \\ \end{eqnarray*} where again the constant of integration must be zero. If you prefer, you can make that explicit as $$\Pi(z) = z^2 \exp \sum_{i \ge 0} \frac{c_i z^{i+1}}{i+1}$$

Answer 2

Consider the following fairly simple Mathematica code

Block[{a={a1},n=3},
 While[n<=32,
  a=AppendTo[a,(PrimePi[n]-Sum[a[[k]] PrimePi[k],{k,1,n-2}])/PrimePi[n-1]];
  n++];
 a]

which generates the first few values of $a_k$ as follows

$$a=\left\{a_1,2,0,\frac{1}{2},0,\frac{1}{3},0,0,0,\frac{1}{4},0,\frac{1}{5},0,0,0,\frac{1}{6},0,\frac{1}{7},0,0,0,\frac{1}{8},0,0,0,0,0,\frac{1}{9},0,\frac{1}{10},0\right\}$$

starting at $a_1$ where

$$\pi(n)=\sum\limits_{k=1}^{n-1} \pi(k)\, a_k\,,\quad n>2\tag{1}.$$

---

For the recursive formula in the question above, the following slightly more complicated Mathematica code

Block[{c={},n=3},
 While[n<=32,
  c=AppendTo[c,(n-2) PrimePi[n]-Sum[PrimePi[k] c[[n-k]],{k,3,n-1}]];
  n++];
 c]

generates the first few values of $c_k$ as follows

$c=\{2,0,5,-4,12,-15,23,-36,68,-100,167,-259,405,-651,1050,-1652,2637,-4182,6633,-10564,16805,-26675,42391,-67371,107062,-170183,270473,-429783,683068,-1085560\}$

starting at $c_0=2$ where

$$\pi(n)=\frac{1}{n-2} \sum\limits_{k=0}^{n-1} \pi(k)\, c_{n-1-k}\,,\quad n>2\tag{2}.$$

---

Note that

$$c-1=\{1,-1,4,-5,11,-16,22,-37,67,-101,166,-260,404,-652,1049,-1653,2636,-4183,6632,-10565,16804,-26676,42390,-67372,107061,-170184,270472,-429784,683067,-1085561\}$$

corresponds to OEIS Entry A307977.

---

The two Mathematica programs above compensate for the fact that the first element of a Mathematica list has index $1$ instead of index $0$ which is more typical of programming languages.

---

I believe the formula

$$\pi(x)=\sum\limits_{k=1}^x \left(\left\{\begin{array}{cc} 1 & k=2+\sum\limits_{p<k} (c_{k-p-1}-1) \\ 0 & \text{Otherwise} \\ \end{array}\right.\right)\tag{3}$$

where $p$ is a prime is valid for all $x\in\mathbb{R}$.