3
$\begingroup$

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

  • 0
    @GregMartin I believe this is the easiest way to state the recursion. You simply cannot make things simpler by trying hard alone. There are limits.2013-03-10

0 Answers 0