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:

prime shift

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)$.

  • $\begingroup$ 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? $\endgroup$ – Mario Carneiro Mar 7 '16 at 0:02
  • $\begingroup$ @MarioCarneiro Roughly speaking I can convince myself that it's true, but in terms of a formal proof... $\endgroup$ – MCT Mar 7 '16 at 0:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Dejan Govc Mar 7 '16 at 0:06
  • $\begingroup$ @DejanGovc Actually it turns out that a linear bound is not necessary, so plain Bertrand's postulate does the trick (see my answer). $\endgroup$ – 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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.