On the sizes of the maximal prime powers divisors of factorials Dan Levy Abstract . Let p p be any prime, and p ν p ​ ( n ! ) p^{\nu_{p}\left(n!\right)} the maximal power of p p dividing n ! n! . It is proved that there exists a positive integer n 0 n_{0} , which depends only on p p , such that q ν q ​ ( n ! ) < p ν p ​ ( n ! ) q^{\nu_{q}\left(n!\right)} p q>p . For twin primes p p and q = p + 2 q=p+2 it is proved that the minimal n 0 n_{0} satisfying q ν q ​ ( n ! ) < p ν p ​ ( n ! ) q^{\nu_{q}\left(n!\right)}p\text{.} Corollary 1.2 . Let m be any positive integer and let p_{1}3^{\nu_{3}\left(n!\right)}>5^{\nu_{5}\left(n!\right)}>\cdots>p_{m}^{\nu_{p_{m}}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}\text{; }\forall n\geq n_{0}\left(m\right) for any prime q which is larger than p_{m} . Proof. This follows from Theorem ( 1.1 ) by taking n_{0}\left(m\right)=\max\left\{n_{0}\left(p_{1}\right),\ldots,n_{0}\left(p_{m}\right)\right\} . Corollary 1.3 . Let q be any odd prime, and n\geq 2 any integer. Then 2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)} with the single exception q=n=3 . Remark 1.4 . Shortly after uploading the first version (arXiv:submit/7138707) of the present paper, I have learned about a paper by Mehdi Hassani, published in 2005, with results similar to Theorem ( 1.1 ) and Corollary ( 1.3 ) ( [ 4 ] Theorem (5.2) and Corollary (5.3)). It can be checked that Theorem ( 1.1 ) and Corollary ( 1.3 ) of the present paper imply, respectively, Hassani’s Theorem (5.2) and Corollary (5.3), but not the other way around. I am grateful to Carlo Sanna for informing me about Hassani’s results. Let p be a fixed prime. The prime successor of p , denoted p_{\text{succ}} , is the smallest prime which is strictly larger than p . As we shall see, the proof of Theorem ( 1.1 ) shows that any positive integer solution n of \left\lfloor\log_{p}n\right\rfloor<\left(n-1\right)h_{p}\left(p_{\text{succ}}\right)-\frac{p-2}{p-1}\text{,} where h_{p}\left(x\right):=\frac{1}{p-1}-\frac{\log_{p}x}{q-1} , satisfies q^{\nu_{q}\left(n!\right)}p . Moreover, there exists n_{0}\in\mathbb{N} such that the above inequality holds true for all n\geq n_{0} . Note that since p_{\text{succ}} is uniquely determined by p , the minimal such n_{0} is a function of p , and hence we refer to this minimal value as n_{0}\left(p\right) . It is easy to see that the existence of n_{0}\left(p\right) implies, in turn, the existence of a minimal positive integer n_{\min}\left(p\right) such that p_{\text{succ}}^{\nu_{p_{\text{succ}}}\left(n!\right)}2 ), and if so, can n_{\min}\left(p\right) be written in polynomial form whose coefficients are parametrized by p_{\text{succ}}-p ? 2. Proofs 2.1. Proof of Theorem ( 1.1 ) Lemma 2.1 . Let pp we have h_{p}\left(q\right)\geq h_{p}\left(p_{\text{succ}}\right)>0\text{.} Proof. The differentiability of h_{p}\left(x\right) in [p,\infty) is clear. In order to prove that it is monotonically increasing we compute its first derivative in [p,\infty) h_{p}^{\prime}\left(x\right)=\frac{1}{\ln p}\frac{1}{\left(x-1\right)^{2}}\left(\ln x+\frac{1}{x}-1\right)\text{,} and check that h_{p}^{\prime}\left(x\right) is positive in [p,\infty) . Clearly, for any x\in[p,\infty) we have h_{p}^{\prime}\left(x\right)>0 iff g\left(x\right):=\ln x+\frac{1}{x}-1>0 . For p=2 we have g\left(2\right)=\ln 2+\frac{1}{2}-1 \geq 0.693-\frac{1}{2}>0 . For p\geq 3 we have \ln p>1 and hence g\left(p\right)=\ln p+\frac{1}{p}-1>\frac{1}{p}>0 . Thus g\left(p\right)>0 for all primes p . Now g^{\prime}\left(x\right)=\frac{1}{x}-\frac{1}{x^{2}} and g^{\prime}\left(x\right)>0 for all x\in[p,\infty) since p>1 . It follows that g\left(x\right) is monotonically increasing in [p,\infty) , which together with g\left(p\right)>0 shows that g\left(x\right)>0 for all x\in[p,\infty) . Hence h_{p}^{\prime}\left(x\right)>0 for all x\in[p,\infty) , and so h_{p}\left(x\right) is monotonically increasing in [p,\infty) . This implies that for any u>p the function h_{p}\left(x\right) has a global minimum in [u,\infty) , given by h_{p}\left(u\right) . The value h_{p}\left(u\right) is strictly positive since h_{p}\left(p\right)=0 , and h_{p}\left(x\right) is monotonically increasing in [p,\infty) . Choosing u=p_{\text{succ}} concludes the proof. Proof of Theorem ( 1.1 ). Let p be any prime. We have to prove the existence of n_{0}\in\mathbb{N} , which may depend on p , such that q^{\nu_{q}\left(n!\right)}p\text{ .} Since q^{\nu_{q}\left(n!\right)}\geq 1 we must have n_{0}\geq p . Under this assumption \nu_{p}\left(n!\right)>0 for all n\geq n_{0} and hence q^{\nu_{q}\left(n!\right)}p and all n\geq n_{0} with q>n . Hence it suffices to show that there exist n_{0}\in\mathbb{N} such that n_{0}>p and q^{\nu_{q}\left(n!\right)}0 , and hence, any positive integer n satisfying (2.8) \left\lfloor\log_{p}n\right\rfloor<\left(n-1\right)h_{p}\left(p_{\text{succ}}\right)-\frac{p-2}{p-1}\text{,} also satisfies ( 2.7 ) for all primes q such that pq^{\nu_{q}\left(n!\right)} for all primes q>2 and all integers n\geq n_{0} . By ( 2.1 ) we have (2.11) h_{2}\left(2_{\text{succ}}\right)=h_{2}\left(3\right)=1-\frac{1}{2}\frac{\ln 3}{\ln 2}>0.2075>\frac{1}{5} and hence we get that any n satisfying \left(\ast\ast\right)~\left\lfloor\log_{2}n\right\rfloor\leq\frac{n-1}{5}\text{,} also satisfies \left(\ast\right) . By inspection, the smallest integer solution of \left(\ast\ast\right) is n=21 , and \left(\ast\ast\right) also holds true for all 21\leq n\leq 31 . Now, \left\lfloor\log_{2}n\right\rfloor is a step function which is constant on each step (an interval of the form \left[2^{k},2^{k+1}-1\right] ) and increases by one unit from step to step. On the other hand, \frac{n-1}{5} is a linear function of n that increases by \frac{2^{k}}{5} along the step \left[2^{k},2^{k+1}-1\right] . Since n=32 corresponds to k=5 , and \frac{2^{5}}{5}>6>1 , it is clear that \left(\ast\ast\right) holds also for all n\geq 32 . We have thus shown that 2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)} holds true for all n\geq 21 and all primes q>2 . It remains to consider the interval 2\leq n\leq 20 . Since this interval is finite and the relevant values of q are the odd primes in this same interval, namely the primes 3,5,7,11,13,17,19 , one can check ”by hand”, e.g., an easy to write GAP ( [ 3 ] ) program, that 2^{\nu_{2}\left(n!\right)}>q^{\nu_{q}\left(n!\right)} holds true for all integers 2\leq n\leq 20 and all primes q\in\left\{3,5,7,11,13,17,19\right\} with the single exception q=n=3 . 2.2. Proof of Theorem ( 1.5 ) Let n\geq 1 and b\geq 2 be integers. Recall that the base b representation of n is the unique sequence \left(n\right)_{b}:=\left(d_{l}\text{,}d_{l-1},\ldots,d_{1},d_{0}\right) of non-negative integers (the base b digits of n ) d_{i} , 0\leq i\leq l such that d_{i}\in\left\{0,1,\ldots,b-1\right\} , d_{l}\geq 1 , and n=d_{l}b^{l}+d_{l-1}b^{l-1}+\cdots+d_{1}b+d_{0}\text{.} Furthermore we say that n is an l+1 digit number in base b , and s_{b}\left(n\right):=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i} . Lemma 2.3 . With notation as above, n-s_{b}\left(n\right)=0 for all 1\leq n\leq b-1 , and n-s_{b}\left(n\right)>0 for all n\geq b . Furthermore, \left(b-1\right)|\left(n-s_{b}\left(n\right)\right) . Proof. The first claim is clear. For n\geq b we have: n-s_{b}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}b^{i}-\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}\left(b^{i}-1\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l}d_{i}\left(b^{i}-1\right)\overset{d_{l}\geq 1}{\geq}b^{l}-1>0\text{.} Moreover, \left(b-1\right)|\left(b^{i}-1\right) for all 1\leq i\leq l , so \left(b-1\right)|\left(n-s_{b}\left(n\right)\right) follows. Let p be a prime such that p+2 is also a prime. Set q:=p+2\text{, }k:=\frac{p^{2}+p}{2}-1\text{.} In order to prove Theorem ( 1.5 ) we have to prove that q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)}\text{;} and (2.12) ~~~~~~p^{\nu_{p}\left(n!\right)}>q^{\nu_{q}\left(n!\right)}\text{; }\forall n\geq k+1\text{.} Lemma 2.4 . \nu_{q}\left(k!\right)=\nu_{p}\left(k!\right)=\frac{p-1}{2}\text{,} and consequently q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)} . Proof. We calculate the exponents \nu_{q}\left(k!\right) and \nu_{p}\left(k!\right) using ( 1.3 ). We have k=\left(\frac{p-1}{2}\right)\left(p+2\right)\Longrightarrow\left(k\right)_{p+2}=\left(\frac{p-1}{2},0\right)\Longrightarrow s_{p+2}\left(k\right)=\frac{p-1}{2}\text{.} Similarly k=\left(\frac{p-1}{2}\right)p+p-1\Longrightarrow\left(k\right)_{p}=\left(\frac{p-1}{2},p-1\right)\Longrightarrow s_{p}\left(k\right)=\frac{3}{2}\left(p-1\right)\text{.} Substituting in ( 1.3 ) gives: \nu_{q}\left(k!\right)=\frac{k-s_{q}\left(k\right)}{q-1}=\frac{\left(\frac{p-1}{2}\right)\left(p+2\right)-\frac{p-1}{2}}{p+1}=\frac{p-1}{2} \nu_{p}\left(k!\right)=\frac{k-s_{p}\left(k\right)}{p-1}=\frac{\left(\frac{p-1}{2}\right)p+p-1-\frac{3}{2}\left(p-1\right)}{p-1}=\frac{p}{2}+1-\frac{3}{2}=\frac{p-1}{2}\text{.} Having proved \nu_{q}\left(k!\right)=\nu_{p}\left(k!\right) , q^{\nu_{q}\left(k!\right)}>p^{\nu_{p}\left(k!\right)} follows from q>p . Proving ( 2.12 ) requires more effort. First, ( 2.12 ) is equivalent to (2.13) r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)}>\left(\frac{\ln\left(p+2\right)}{\ln p}\right)\left(\frac{p-1}{p+1}\right)\text{; }\forall n\geq k+1=\frac{p^{2}+p}{2}\text{,} by Lemma ( 2.1 ). Note that n-s_{p+2}\left(n\right)>0 by Lemma ( 2.3 ) ( p+2\leq n since n\geq k+1 and p\geq 3 ). For a fixed odd prime p we view r\left(n,p\right) as a function from the set of all integers n satisfying n\geq k+1 into the set of positive rational numbers. Lemma 2.5 . r\left(k+1,p\right)=1 . Proof. Using \left(k\right)_{p} and \left(k\right)_{p+2} from the proof of Lemma ( 2.4 ), gives \left(k+1\right)_{p}=\left(\frac{p+1}{2},0\right)\text{ and }\left(k+1\right)_{p+2}=\left(\frac{p-1}{2},1\right)\text{.} Hence s_{p}\left(k+1\right)=s_{p+2}\left(k+1\right)=\frac{p+1}{2} , and the claim follows. Lemma 2.6 . r\left(n,p\right) has a global minimum in the interval n\geq\frac{p^{2}+p}{2} . Proof. First we prove \lim_{n\rightarrow\infty}r\left(n,p\right)=1 . Write r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)}=\frac{1-\frac{s_{p}\left(n\right)}{n}}{1-\frac{s_{p+2}\left(n\right)}{n}}\text{,} and use the bounds 1\leq s_{p}\left(n\right)\leq\left(p-1\right)\left(1+\log_{p}n\right) (see the proof of Theorem ( 1.1 )). Since a similar inequality applies to s_{p+2}\left(n\right) , we get: (2.14) \frac{1-\frac{\left(p-1\right)\left(1+\log_{p}n\right)}{n}}{1-\frac{1}{n}}\leq r\left(n,p\right)\leq\frac{1-\frac{1}{n}}{1-\frac{\left(p+1\right)\left(1+\log_{p+2}n\right)}{n}}\text{.} Since p is fixed, we have \lim_{n\rightarrow\infty}\frac{\left(p-1\right)\left(1+\log_{p}n\right)}{n}=\lim_{n\rightarrow\infty}\frac{\left(p+1\right)\left(1+\log_{p+2}n\right)}{n}=0\text{,} and \lim_{n\rightarrow\infty}r\left(n,p\right)=1 follows. Now assume by contradiction that r\left(n,p\right) has no global minimum in the interval n\geq k+1 . By Lemma ( 2.5 ) we have r\left(k+1,p\right)=1 . Since this cannot be a global minimum in the interval n\geq k+1 , there exists an infinite monotonically increasing sequence of integers k+1=i_{0}r\left(i_{1},p\right)>r\left(i_{2},p\right)>\cdots is a monotonically decreasing sequence of positive rational numbers. It follows that this sequence is bounded from below by some nonnegative rational number less than 1 . Therefore there exists 0\leq l<1 such that \lim_{j\rightarrow\infty}r\left(i_{j},p\right)=l . This contradicts \lim_{n\rightarrow\infty}r\left(n,p\right)=1 . We will prove that ( 2.13 ) holds true for all n\geq k+1 by showing that the global minimum of r\left(n,p\right) in the interval n\geq k+1 satisfies ( 2.13 ). The following theorem gives the necessary information about the global minimum of r\left(n,p\right) . Theorem 2.7 . (a) The smallest integer m at which the global minimum of r\left(n,p\right) in the interval n\geq k+1 occurs is given by (2.15) m=\left\{\begin{array}[]{c}\left(p+2\right)^{2}\text{ if }p\in\left\{3,5\right\}\\ p^{2}-4\text{ if }p\geq 11\text{.}\end{array}\right. (b) The value of the global minimum of r\left(n,p\right) in the interval n\geq k+1 is given by: \displaystyle r\left(m,3\right) \displaystyle= \displaystyle r\left(25,3\right)=\frac{5}{6} \displaystyle r\left(m,5\right) \displaystyle= \displaystyle r\left(49,5\right)=\frac{5}{6} \displaystyle r\left(m,p\right) \displaystyle= \displaystyle r\left(p^{2}-4,p\right)=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{; }\forall p\geq 11\text{.} Before proving Theorem ( 2.7 ) we check that it implies ( 2.12 ). As we already saw, ( 2.12 ) is equivalent to ( 2.13 ). Since r\left(m,p\right) is the global minimum of r\left(n,p\right) in the interval n\geq k+1 , ( 2.13 ) follows iff (2.16) r\left(m,p\right)>\left(\frac{\ln\left(p+2\right)}{\ln p}\right)\left(\frac{p-1}{p+1}\right)\text{.} Lemma 2.8 . Assuming that Theorem ( 2.7 ) is correct, ( 2.16 ) holds true for all p such that p and p+2 are twin primes. Proof. For each p we compare the value of the r.h.s. of ( 2.16 ) with the value of r\left(m,p\right) as given by Theorem ( 2.7 ). 1. p=3 \frac{\ln\left(p+2\right)}{\ln p}\cdot\frac{p-1}{p+1}=\frac{\ln 5}{\ln 3}\cdot\frac{2}{4}<0.733\left(p-2\right)\ln\left(p+2\right) \displaystyle\Longleftrightarrow \displaystyle\left(p-1\right)\ln p-\left(p-2\right)\ln\left(p+2\right)>0 Set f\left(x\right):=\left(x-1\right)\ln x-\left(x-2\right)\ln\left(x+2\right)\text{; }\forall x\geq 11\text{.} We will show that f\left(x\right) is positive in its domain of definition. \displaystyle f\left(x\right) \displaystyle=x\left(\ln x-\ln\left(x+2\right)\right)+2\ln\left(x+2\right)-\ln x \displaystyle=x\ln\left(\frac{x}{x+2}\right)+\ln\left(x+2\right)^{2}-\ln x \displaystyle=-x\ln\left(\frac{x+2}{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right) \displaystyle=-\ln\left(\left(\frac{x+2}{x}\right)^{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right) \displaystyle=-\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)+\ln\left(\frac{\left(x+2\right)^{2}}{x}\right)\text{.} Using \lim_{x\rightarrow\infty}\left(1+\frac{2}{x}\right)^{x}=e^{2}\text{,} we have -\lim_{x\rightarrow\infty}\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)=-\ln e^{2}=-2\text{.} Moreover -\ln\left(\left(1+\frac{2}{x}\right)^{x}\right) is monotonically decreasing towards its limit. On the other hand \ln\left(\frac{\left(x+2\right)^{2}}{x}\right) is monotonically increasing for x\geq 11 and for x=11 we have \ln\left(\frac{\left(11+2\right)^{2}}{11}\right)=\ln\frac{13}{11}+\ln 13>\ln\frac{13}{11}+\ln e^{2}>2\text{.} We get: f\left(x\right)>-\lim_{x\rightarrow\infty}\ln\left(\left(1+\frac{2}{x}\right)^{x}\right)+\ln\left(\frac{\left(11+2\right)^{2}}{11}\right)>-2+2=0\text{.} Now we prove Theorem ( 2.7 ). Given that part (a) is established, deriving part (b) from part (a) is an easy task. Proof of Theorem ( 2.7 )(b) assuming (a). These are just routine calculations that are required for substituting n\leftarrow m into r\left(n,p\right):=\frac{n-s_{p}\left(n\right)}{n-s_{p+2}\left(n\right)} . Equality ( 2.15 ) immediately yields: 1. If p=3 then m=25 and \displaystyle\left(m\right)_{3}=\left(25\right)_{3}=\left(2,2,1\right)\text{, }s_{3}\left(25\right)=5 \displaystyle\left(m\right)_{3+2}=\left(25\right)_{5}=\left(1,0,0\right)\text{, }s_{5}\left(25\right)=1\text{.} 2. If p=5 then m=49 and \displaystyle\left(m\right)_{5}=\left(49\right)_{5}=\left(1,4,4\right)\text{, }s_{5}\left(49\right)=9 \displaystyle\left(m\right)_{5+2}=\left(49\right)_{7}=\left(1,0,0\right)\text{, }s_{7}\left(49\right)=1\text{.} 3. If p\geq 11 then m=p^{2}-4=\left(p-2\right)\left(p+2\right)=\left(p-1\right)p+p-4 and hence \displaystyle\left(m\right)_{p}=\left(p-1,p-4\right)\text{, }s_{p}\left(p^{2}-4\right)=2p-5 \displaystyle\left(m\right)_{p+2}=\left(p-2,0\right)\text{, }s_{p+2}\left(p^{2}-4\right)=p-2 By definition: r\left(m,p\right)=\frac{m-s_{p}\left(m\right)}{m-s_{p+2}\left(m\right)}\text{.} The explicit expressions for r\left(m,p\right) in the various cases are as follows: r\left(m,3\right)=\frac{25-s_{3}\left(25\right)}{25-s_{5}\left(25\right)}=\frac{25-5}{25-1}=\frac{5}{6}\text{.} r\left(m,5\right)=\frac{49-s_{5}\left(49\right)}{49-s_{7}\left(49\right)}=\frac{49-9}{49-1}=\frac{5}{6}\text{.} For all p\geq 11 we get \displaystyle r\left(m,p\right)=\frac{p^{2}-4-s_{p}\left(p^{2}-4\right)}{p^{2}-4-s_{p+2}\left(p^{2}-4\right)} \displaystyle=\frac{p^{2}-4-\left(2p-5\right)}{p^{2}-4-\left(p-2\right)}=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{.} Finally we turn to prove part (a) of Theorem ( 2.7 ). First we show that the global minimum of r\left(n,p\right) in the interval n\geq k+1 occurs at m , and then we show that for all k+1\leq nr\left(m,p\right) . Therefore m is the smallest integer in the interval n\geq k+1 at which the global minimum of r\left(n,p\right) in this interval occurs. We begin by arguing that the global minimum of r\left(n,p\right) occurs ”not too far” from k+1 . To this end we use the lower bound ( 2.14 ) on r\left(n,p\right) : r\left(n,p\right)\geq\frac{1-\frac{\left(p-1\right)\left(\log_{p}\left(n\right)+1\right)}{n}}{1-\frac{1}{n}}>1-\frac{\left(p-1\right)\left(\log_{p}\left(n\right)+1\right)}{n}\text{; }\forall n\geq q\text{.} Since \log_{p}\left(n\right)=\frac{\ln n}{\ln p} we have (2.17) ~r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln n}{\ln p}+1\right)\frac{1}{n}\text{; }\forall n\geq q\text{.} Lemma 2.9 . The real function f\left(x\right):=\left(\frac{\ln x}{\ln p}+1\right)\frac{1}{x}\text{; }\forall x\geq 1 is positive and monotonically decreasing. Proof. Positivity is clear. To show that the function is monotonically decreasing, we calculate its first derivative: f^{\prime}\left(x\right)=\frac{1}{\ln p}\frac{1}{x^{2}}+\left(\frac{\ln x}{\ln p}+1\right)\frac{-1}{x^{2}}=\frac{1}{x^{2}}\left(\frac{1}{\ln p}-\frac{\ln x}{\ln p}-1\right)\text{.} Since p\geq 3>e , we have \frac{1}{\ln p}<1 and \frac{1}{\ln p}-1<0 . Hence, since \frac{\ln x}{\ln p}\geq 0 for all x\geq 1 , f^{\prime}\left(x\right)<0 , finishing the proof of the lemma. Corollary 2.10 . Let \widetilde{n}\geq q be an integer. Then, for all integers n\geq \widetilde{n} we have r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}\text{.} Proof. Let n\geq \widetilde{n} be an integer. Since \widetilde{n}\geq q and n\geq \widetilde{n} we have n\geq q and therefore, by 2.17 , r\left(n,p\right)>1-\left(p-1\right)\left(\frac{\ln n}{\ln p}+1\right)\frac{1}{n}\text{.} In the notation of Lemma ( 2.9 ) we have r\left(n,p\right)>1-\left(p-1\right)f\left(n\right)\text{.} Since f\left(x\right) is monotonically decreasing for all x\geq 1 , 1-\left(p-1\right)f\left(x\right) is monotonically increasing for all x\geq 1 . Hence, since n\geq \widetilde{n} , r\left(n,p\right)>1-\left(p-1\right)f\left(n\right)\geq 1-\left(p-1\right)f\left(\widetilde{n}\right)\text{.} To utilize the last corollary we look for \widetilde{n}\geq q such that (2.18) 1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}\geq r\left(m,p\right)\text{,} where m is given by ( 2.15 ). Given such \widetilde{n} , Corollary ( 2.10 ) implies r\left(n,p\right)>r\left(m,p\right) for all n\geq\widetilde{n} , and it will remain to establish the claim of part (a) of Theorem ( 2.7 ) for the range k+1\leq n<\widetilde{n} . Lemma 2.11 . Define m by ( 2.15 ). (a) For p=3 ( 2.18 ) holds true for \widetilde{n}=3^{4} . (b) For p=5 ( 2.18 ) holds true for \widetilde{n}=5^{3} . (c) For any prime p\geq 11 ( 2.18 ) holds true for \widetilde{n}=4p^{2} . Proof. (a) If p=3 and \widetilde{n}=3^{4} we have: \displaystyle 1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}=1-2\left(\frac{\ln 3^{4}}{\ln 3}+1\right)\frac{1}{81}=1-\frac{10}{81} \displaystyle=\frac{71}{81}>\frac{5}{6}=r\left(25,3\right)\text{.} (b) If p=5 and \widetilde{n}=5^{3} we have: \displaystyle 1-\left(p-1\right)\left(\frac{\ln\widetilde{n}}{\ln p}+1\right)\frac{1}{\widetilde{n}}=1-4\left(\frac{\ln 5^{3}}{\ln 5}+1\right)\frac{1}{5^{3}} \displaystyle=1-\frac{4\cdot 4}{125}=\frac{109}{125}>\frac{5}{6}=r\left(49,5\right)\text{.} (c) If p\geq 11 and \widetilde{n}=4p^{2} we have to show that 1-\left(p-1\right)\left(\frac{\ln 4p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}\geq r\left(m,p\right)\text{; }\forall p\geq 11\text{.} We have \left(\frac{\ln 4p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}=\left(\frac{\ln 4+\ln p^{2}}{\ln p}+1\right)\frac{1}{4p^{2}}=\frac{1}{4}\left(3+\frac{\ln 4}{\ln p}\right)\frac{1}{p^{2}}\text{.} Therefore, setting c_{p}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln p}\right) , we have to show that 1-\frac{c_{p}\left(p-1\right)}{p^{2}}\geq\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)}\text{; }\forall p\geq 11\text{.} We have: \displaystyle 1-\frac{c_{p}\left(p-1\right)}{p^{2}}\geq\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)} \displaystyle\Longleftrightarrow \displaystyle p^{2}\left(p-2\right)\left(p+1\right)-p^{2}\left(p-1\right)^{2}\geq c_{p}\left(p-1\right)\left(p-2\right)\left(p+1\right) \displaystyle\Longleftrightarrow \displaystyle p^{2}\left(p^{2}-p-2\right)-p^{2}\left(p^{2}-2p+1\right)\geq c_{p}\left(p-2\right)\left(p^{2}-1\right) \displaystyle\Longleftrightarrow \displaystyle p^{3}-3p^{2}\geq c_{p}\left(p^{3}-2p^{2}-p+2\right) Set \displaystyle f\left(x\right):=x^{3}-3x^{2}-c_{x}\left(x^{3}-2x^{2}-x+2\right) \displaystyle\text{where }c_{x}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln x}\right) Then f^{\prime}\left(x\right)=3x^{2}-6x-\left(c_{x}\right)^{\prime}\left(x^{3}-2x^{2}-x+2\right)-c_{x}\left(3x^{2}-4x-1\right)\text{.} Substituting \left(c_{x}\right)^{\prime}:=\frac{1}{4}\left(3+\frac{\ln 4}{\ln x}\right)^{\prime}=\frac{\ln 4}{4}\frac{-1}{x\left(\ln x\right)^{2}} gives \displaystyle f^{\prime}\left(x\right) \displaystyle= \displaystyle 3x^{2}-6x+\frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x^{3}-2x^{2}-x+2\right)-c_{x}\left(3x^{2}-4x-1\right) \displaystyle= \displaystyle\left(3x^{2}-4x-1\right)\left(1-c_{x}\right)+\frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x-2\right)\left(x^{2}-1\right)+1-2x\text{.} In order to prove that f^{\prime}\left(x\right)>0 for all x\geq 11 , start with \frac{\ln 4}{4}\frac{1}{x\left(\ln x\right)^{2}}\left(x-2\right)\left(x^{2}-1\right)+1>1\text{; }\forall x\geq 11\text{.} Then observe that \left(c_{x}\right)^{\prime}<0 for all x\geq 11 so c_{x} is maximal in [11,\infty) at x=11 and hence c_{x}\leq c_{11}<0.895<\frac{9}{10} \Longleftrightarrow 1-c_{x}>\frac{1}{10} for all x\geq 11 . Since 3x^{2}-4x-1>0 for all x\geq 11 we have \left(3x^{2}-4x-1\right)\left(1-c_{x}\right)-2x>\frac{1}{10}\left(3x^{2}-4x-1\right)-2x\text{; }\forall x\geq 11\text{,} and hence it suffices to prove that \frac{1}{10}\left(3x^{2}-4x-1\right)-2x>0 ; \forall x\geq 11 . But the last inequality is equivalent to 3x^{2}-24x=3x\left(x-8\right)>1 which is true for all x\geq 11 . This concludes the proof that f^{\prime}\left(x\right)>0 for all x\geq 11 . Using c_{x}<0.895 for all x\geq 11 , we check that f\left(11\right)>968-1080\cdot 0.895=1.4>0\text{,} which together with the positivity of f^{\prime}\left(x\right) for all x\geq 11 , concludes the proof of the lemma. Proposition 2.12 . Let p\in\left\{3,5\right\} , k:=\frac{p^{2}+p}{2}-1 , m:=\left(p+2\right)^{2} and \widetilde{n}:=p^{4} if p=3 and \widetilde{n}:=p^{3} if p=5 . Then r\left(n,p\right)\geq r\left(m,p\right)=\frac{5}{6} for all k+1\leq n\leq\widetilde{n} , and if k+1\leq nr\left(m,p\right) . Proof. GAP ( [ 3 ] ) calculation. Proposition 2.13 . Let p\geq 11 be a prime such that q:=p+2 is a prime. Let k:=\frac{p^{2}+p}{2}-1 , m:=p^{2}-4 and \widetilde{n}:=4p^{2} . Then r\left(n,p\right)\geq r\left(m,p\right)=\frac{\left(p-1\right)^{2}}{\left(p-2\right)\left(p+1\right)} for all k+1\leq n\leq\widetilde{n} , and if k+1\leq nr\left(m,p\right) . Proof. Let k+1\leq n\leq\widetilde{n} , and let \left(n\right)_{p}:=\left(d_{l},d_{l-1},\ldots,d_{1},d_{0}\right)\text{ and }\left(n\right)_{q}:=\left(e_{l^{\prime}},e_{l^{\prime}-1},\ldots,e_{1},e_{0}\right) be, respectively, the base p and the base q digits of n . Then (see Lemma ( 2.3 )) n-s_{p}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}p^{i}-\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}=\mathop{\textstyle\sum}\limits_{i=0}^{l}d_{i}\left(p^{i}-1\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l}d_{i}\left(p^{i}-1\right)\text{,} and, similarly, n-s_{q}\left(n\right)=\mathop{\textstyle\sum}\limits_{i=1}^{l^{\prime}}e_{i}\left(\left(p+2\right)^{i}-1\right)\text{.} Since k+1\leq n<\widetilde{n}=4p^{2} , and p\geq 11 , we have 4p^{2}<4\left(p+2\right)^{2}0 and condition \left(\ast\right) reads \frac{d_{1}}{e_{1}}\geq\frac{p-1}{p-2} . Since e_{2}=d_{2}=0 we get: n=d_{1}p+d_{0}=e_{1}\left(p+2\right)+e_{0}=e_{1}p+2e_{1}+e_{0}\text{.} Since d_{0}

0 we see, using e_{1}\leq p-5 and p\geq 11 , that the l.h.s is strictly positive. If \alpha=0 we have to prove that d_{2}\left(p-7\right)-e_{1}\geq 0\text{.} By ( 2.19 ), 4e_{2}+2e_{1}+e_{0}=4d_{2}+2e_{1}+e_{0}=\beta\leq p-1 , or, equivalently 2e_{1}\leq p-1-4d_{2}-e_{0}\leq p-1-4d_{2}\text{.} Since d_{2}\geq 1 , this implies e_{1}\leq\frac{p-5}{2} . It follows that \displaystyle d_{2}\left(p-7\right)-e_{1}\geq d_{2}\left(p-7\right)-\frac{p-5}{2} \displaystyle\overset{d_{2}\geq 1}{\geq}\left(p-7\right)-\frac{p-5}{2}=\frac{p-9}{2}>0 as required. This concludes the proof that Condition \left(\ast\right) is true in case (2.1). (2.2). Suppose that e_{2}e_{2}=1 we have d_{2}= \alpha_{1}+1\geq 2 , and hence \alpha_{1}+2\geq 3 . Therefore \alpha_{1}+\alpha_{0}+2\geq 3 and \left(\alpha_{1}+\alpha_{0}+2\right)\left(p-2\right)\geq 3\left(p-2\right)\text{.} But 3\left(p-2\right)\geq 2p+4\Longleftrightarrow p\geq 10\text{.} Hence, for all p\geq 11 we have 3\left(p-2\right)\geq 2p+4 and therefore ( 2.22 ) is true. This concludes the proof that Condition \left(\ast\right) holds true in case (2.2.2). (2.2.3). Suppose that e_{2}=2 . Then d_{2}=\alpha_{1}+2 , and Condition \left(\ast\right) reads: \displaystyle\frac{\left(\alpha_{1}+2\right)\left(p+1\right)+d_{1}}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2} \displaystyle\Longleftrightarrow \displaystyle\frac{2\left(p+1\right)+\alpha_{1}+\alpha_{1}\cdot p+d_{1}}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2}\text{.} Since \alpha_{1}\cdot p+d_{1}=4e_{2}+e_{1}+\alpha_{0}=8+e_{1}+\alpha_{0} , we get the equivalent inequality: \displaystyle\frac{2\left(p+3\right)+e_{1}+\alpha_{0}+\alpha_{1}+4}{2\left(p+3\right)+e_{1}}\geq\frac{p-1}{p-2} \displaystyle\Longleftrightarrow \displaystyle\frac{\alpha_{0}+\alpha_{1}+4}{2\left(p+3\right)+e_{1}}\geq\frac{1}{p-2} \displaystyle\Longleftrightarrow \displaystyle\left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 2\left(p+3\right)+e_{1}\text{.} Since e_{1}\leq p+1 the last inequality certainly holds true if \left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 3p+7\text{.} Since 3\geq d_{2}= \alpha_{1}+2 and d_{2}>e_{2}=2 , we have \alpha_{1}+2=3 , and hence \alpha_{1}+4=5 . Therefore \alpha_{1}+\alpha_{0}+4\geq 5 and \left(\alpha_{0}+\alpha_{1}+4\right)\left(p-2\right)\geq 5\left(p-2\right)\text{.} But 5\left(p-2\right)\geq 3p+7\Longleftrightarrow 2p\geq 17\text{.} Thus, Condition \left(\ast\right) holds true in case (2.2.3).