This question is about counting functions.
With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than $+1$ from one integer imput to the next. Hence $0 \leq F(n+1)-F(n) < 2$. Also $F(1)<2$.
In particular I wonder about recursively defined counting functions in the following way: (some initial values needed sometimes and values are floored ( see floor function ) )
$P(x,n) = x - 1 - \sum _{j=1}^{n} (P(f(x,p_j),g(j)) - h(j))$
if $n > r(x)$ replace $n$ by $r(x)$.
Where $p_j$ stands for the jth value of $x$ where the function $P(x,r(x))$ rises.
As a clear example : the prime counting function.
$P(x,n) = x - 1 -\sum _{j=1}^{n}(P(x/p_j,j-1) - (j-1))$
if $n > \sqrt x$ replace $n$ by $\sqrt x$.
Where $p_j$ stands for the $j$-th values of $x$ where the function $P(x,\sqrt x)$ rises ; the primes.
$P(x,\sqrt x)$ is then the prime counting function.
And $P(x,n)$ counts all the composites till $x$ apart for the multiples of $n$.
I wonder if there are intresting cases for other kinds of $f,g,h,r$.
Also I noticed that my example is a sieve and I wonder if all intresting cases are sieves ?
It has been suggested to take the difference operator on $P$ for $x$ , for $n$ or even both. Perhaps it also of use to investigate $P(x,n)$ mod $q$ for some primes $q$.
ADDED:
Consider
$P(x,n) = x - 1 -\sum _{j=1}^{n}(P(x/p_j,j-1) - (j-1))$
if $n > x^{\frac{1}{3}}$ replace $n$ by $x^{\frac{1}{3}}$.
Where $p_j$ stands for the $j$-th values of $x$ where the function $P(x,x^{\frac{1}{3}})$ rises.
$P(x,x^{\frac{1}{3}})$ is then the counting function for the $p_j$.
Conjecture $1$ : Let $C_1,C_2$ be nonzero reals. $P(x,x^{\frac{1}{3}})$ grows like $C_1 \dfrac{x}{ln(x)-C_2}$ for sufficiently large values of $x$.
Conjecture $2$ : the sequence $p_i$ contains " twins " meaning $p_a-p_b=2$ for an infinite amount of integers $a,b$.
All this seems intuitively right but I do not know how to show it.
Another conjecture - although I think it is not true - is that lucky numbers (http://en.wikipedia.org/wiki/Lucky_number) also satisfy a recursion of the form
$P(x,n) = x - 1 - \sum _{j=1}^{n} (P(f(x,p_j),g(j)) - h(j))$
if $n > r(x)$ replace $n$ by $r(x)$.
Where $p_j$ stands for the jth value of $x$ where the function $P(x,r(x))$ rises.
I call this conjecture L.
I assume and hope this edit makes the question less general and more intresting and more likely solvable. Although I am still intrested in the general case.
I also have been considering even more general recursions but I think that is hopeless without understanding these things first.
mick