2
$\begingroup$

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?)

$\endgroup$
1
  • $\begingroup$ It is listed by OEIS: oeis.org/A003961 $\endgroup$ Commented Mar 6, 2016 at 23:46

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • $\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$ Commented Mar 7, 2016 at 0:02
  • $\begingroup$ @MarioCarneiro Roughly speaking I can convince myself that it's true, but in terms of a formal proof... $\endgroup$ Commented Mar 7, 2016 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$ Commented Mar 7, 2016 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$ Commented Mar 7, 2016 at 0:22
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.