Number Theory – Factorization Trees and Continued Fractions

Question

This question is inspired by trying to understand the lexicographic sorting of the natural numbers in the fractal at this question:
Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , where $\pi$ denotes the prime counting function and $p_n$ denotes the $n$-th prime?

Let $P_1(n) := 1$ if $n=1$ and $\max_{q|n, \text{ }q\text{ prime}} q$ otherwise, denote the largest prime divisor of $n$.

Let us define some rooted trees $T_{n,m}$ for $1 \le m \le n$ by:

1. $T_{n,m}$ has as root the number $m$.
2. If there are primes $p$ such that $P_1(m) \le p \le \frac{n}{m}$, then the children of $m$ are $T_{n,mp}$, otherwise $m$ is a leaf.

We set $T_n := T_{n,1}$. Example of such trees for $n=1,\cdots,6$ are shown below:

We associate to this tree $T_{12}$:

the following functions, which are inspired by continued fractions:

$$e_{12}(x)= \frac{1}{11^{x} + 7^{x} + 5^{x} + \frac{3^{x}}{9^{x}} + \frac{2^{x}}{10^{x} + 6^{x} + \frac{4^{x}}{12^{x} + 8^{x}}}} $$
$$p_{12}(x)= \frac{x}{x^{11} + x^{7} + x^{5} + \frac{x^{2}}{x^{10} + x^{6} + \frac{x^{4}}{x^{12} + x^{8}}} + \frac{1}{x^{6}}} $$

We plot the function $p(T_{12},x)$ and see how it looks like around $x=1$, where $\pi(n)$ counts the number of primes $p,p \le n$:

The definition for $p(T_{n,m},x)$ is given here:

$$p(T_{n,m},x) := \frac{x^m}{\sum_{m \rightarrow v}p(T_{n,v},x)}, \text{ if }m\text{ is not a leaf}$$

and $p(T_{n,m},x) := x^m, \text{ if }m\text{ is a leaf}$.

Let $c(n):=\frac{1}{p(T_{n,1},1)}$. Then we observe and formulate the following conjecture:

1. $c(n) \le \pi(n) \forall n \ge 2$
2. $c(n) \approx \pi(n)$

Here is a plot for this conjecture $n=1000$, green = $\pi(x)$, red = $\operatorname{Li}(x)$, blue = $c(m)$:

Using induction on $n$ one can prove that $n \ge 2$:

$$p(T_{n+1},x) = \frac{x}{\frac{x}{p(T_n,x)}+x^{n+1}}, \text{ if } n+1 \text{ is prime}$$
and
$$p(T_{n+1},x) = \frac{x}{\frac{x}{p(T_n,x)}+p(T_{n+1,p_1(n+1)},x)-p(T_{n,p_1(n+1)},x)}, \text{ if } n+1 \text{ is not a prime}$$

where $p_1(m) := 1 $ if $m=1$ and $p_1(m):= \min_{q, q \text{ prime }} q$ is the smallest prime which divides $m$.

From this last observation it follows that:

$$c(n+1) = c(n) + p(T_{n+1,p_1(n+1)},1)-p(T_{n,p_1(n+1)},1),\text{ if } n+1 \text{ is not prime}$$
and
$$c(n+1) = c(n) + 1,\text{ if } n+1 \text{ is prime}$$
and so we get:

$$c(n) = \pi(n) + \sum_{1 \le k \le n , k \text{ is composite}} \left( p(T_{k,p_1(k)},1)-p(T_{k-1,p_1(k)},1) \right)$$

I am interested if the conjectures above are true and can be proven or if there exist counterexamples.

I am also interested in the sequence of rational functions $p(T_n,x)$ in the interval $(0,2)$, if it approaches the zero function and what can be said about the growths of these functions?

Thanks for your help.

Comment:

Having drawn such a tree $T_n$ we observe, that it is very easy to find the prime factorization of every number $1 \le m \le n$ in this tree, by starting at the node $m$ and then looking to the parent $v$ of $m$ to form the prime factor $p=\frac{v}{m}$ of $m$. We continue this way up the tree until the root $1$ and collect prime factors of $m$, which encode the factorization of $m$.
The tree can be filled inductively by putting $n+1$ in the tree of $T_n$. For this one needs to know the prime factorization of $n+1 = p_1 \cdot p_2 \cdots p_r$ where $p_i \le p_{i+1}$. One starts at $1$ and goes down the branch which has $p_1/1$ as the prime and removes $p_1$ from the list of prime factors. Then one choses $v$ such that $v/p_1=p_2$ and so on and puts the number $n+1$ if there is not such a $v$ any more or if there the prime factors list contains one last prime factor.

The method to associate a fraction to a tree is borrowed from continued fractions (with $b_0=0$) and generalised continued fractions (with $b_0=0$), where in case of continued fractions it has $1$ at the root, and $b_1$ at it's left child, while it has $1$ at the right child and this has $b_2$ as it's left child and $1$ as it's right child. So it is a possible infinte binary tree which is associated to a continued fraction. The idea is to reverse this process and to associate to a possibly infinte tree with natural numbers as nodes a fraction or a real number, provided it converges.

Second question:
Are there generalizations of continued fractions to arbitrary trees in the literature, the way I described it above? (I found Is there any pattern to the continued fraction of $\sqrt[3]{2}$? and the references given there, but it is not quite the construction I was asking).

Answer 1

Note that for any $m$ which isn't a leaf, due to Bertrand's postulate, there must be a prime in the range $\frac{n}{2m} < p \leq \frac{n}m$, and then $mp$ must be a leaf. Therefore, we have $p(T_{n,m}, 1) \leq 1$, which easily proves the first conjecture. Regarding the second one, we can see that for every $p > \sqrt n$, $T_{n,p}$ is a leaf, so $c(n) = \sum_{p\leq n\\ p\text{ prime}}p(T_{n,p},1) \geq \sum_{\sqrt n<p\leq n\\ p\text{ prime}}p(T_{n,p},1) = \sum_{\sqrt n<p\leq n\\ p\text{ prime}} 1 = \pi(n) - \pi(\sqrt n) \approx \pi(n)$ (the $p$ there is a bit confusing, but it should be obvious from context which $p$ is which), so by sandwich with the first inequality we get $c(n) \approx \pi(n)$.