# Order of growth of the prime shift function

The prime shift function $s(n)$ for $n\in\Bbb N$ is defined by $$s\Big(\prod_ip_i^{e_i}\Big)=\prod_ip_{i+1}^{e_i},$$ where $p_i$ is the $i$-th prime.

Here are the values of $s(1),\dots,s(100)$:

\begin{matrix} 1,&3,&5,&9,&7,&15,&11,&27,&25,&21,\\ 13,&45,&17,&33,&35,&81,&19,&75,&23,&63,\\ 55,&39,&29,&135,&49,&51,&125,&99,&31,&105,\\ 37,&243,&65,&57,&77,&225,&41,&69,&85,&189,\\ 43,&165,&47,&117,&175,&87,&53,&405,&121,&147,\\ 95,&153,&59,&375,&91,&297,&115,&93,&61,&315,\\ 67,&111,&275,&729,&119,&195,&71,&171,&145,&231,\\ 73,&675,&79,&123,&245,&207,&143,&255,&83,&567,\\ 625,&129,&89,&495,&133,&141,&155,&351,&97,&525,\\ 187,&261,&185,&159,&161,&1215,&101,&363,&325,&441\\ \end{matrix}

A plot of the first thousand values:

What is the order of growth of $s(n)$? (Also, does $s(n)$ have a name in the literature?)

A start for an upper bound: Let $d_0(n)$ be the number of not necessarily distinct divisors of $n$. We know that $p_{i+1} < 2p_i$ (this follows from the fact that for all $n \geq 1$ there exists $p$ prime such that $n < p \leq 2n$, hence

$$s(n) < 2^{d_0(n)} n$$

Furthermore, $d_0(n) \leq \log_2 n$, so

$$s(n) < n^2$$

And hence $s(n) = O(n^2)$.

• Given that the peaks are at $s(2^n)=3^n$ and $s(3\cdot 2^n)=5\cdot 3^n$, one would guess that the sharpest upper bound is $O(n^{\log_2 3})$. Any ideas on how to show it? – Mario Carneiro Mar 7 '16 at 0:02
• @MarioCarneiro Roughly speaking I can convince myself that it's true, but in terms of a formal proof... – MCT Mar 7 '16 at 0:03
• @MarioCarneiro: apparently Bertrand's postulate can be strengthened to the statement that there is always a prime between $2n$ and $3n$. This should yield the relevant bound. – Dejan Govc Mar 7 '16 at 0:06
• @DejanGovc Actually it turns out that a linear bound is not necessary, so plain Bertrand's postulate does the trick (see my answer). – Mario Carneiro Mar 7 '16 at 0:22

Trying to show $O(n^{\log_23})$, based on Dejan Govc's comment:

Let $n=\prod_ip_i^{e_i}$. We claim that $s(n)\le n^{\log_23}$, with equality for $n=2^k$. We have:

$$\prod_ip_{i+1}^{e_i}\le\prod_i(p_i^{\log_23})^{e_i}=(\prod_ip_i^{e_i})^{\log_23}$$

and hence prove the goal, provided we can show $p_{i+1}\le p_i^{\log_23}$, which for the first two primes reduces to $3\le 3$ and $5\le 5.7\dots$ . For $p_i\ge 4$, we have $p_i^{\log_23}\ge p_i\cdot 4^{\log_23-1}=\frac94p_i\ge 2p_i$, and now Bertrand's postulate applies to give $p_{i+1}\le2p_i$.

Since $p_i\le p_{i+1}$, we immediately have $s(n)\ge n$. A slightly stricter lower bound is $s(n)\ge n+2$, which holds for $n\ge 3$, which is saturated at all the twin primes and hence is sharp, assuming the twin prime conjecture.

To show $s(n)\ge n+2$, let $p_i$ be an odd prime power divisor of $n$. If no such divisor exists, then $n=2^k$ and $s(n)=3^k\ge 2^k+2$ (since $n$ is not $1$ or $2$ by assumption). Since $s$ is multiplicative, $s(n)=s(p_i)s(n/p_i)\ge\frac{p_{i+1}}{p_i}n$. Then $s(n)-n\ge(p_{i+1}-p_i)\frac{n}{p_i}\ge p_{i+1}-p_i\ge 2$, because $p_i$ and $p_{i+1}$ are both odd.

To summarize:

For $n\ge 3$, $$n+2\le s(n)\le n^{\log_23},$$ and assuming the twin prime conjecture, both bounds are attained infinitely many times.