For an integer $n \geq 3$ we define the sequence $\alpha_1, \alpha_2, \ldots, \alpha_k$ as the sequence of exponents in the prime factorization of $n! = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}$, where $p_1 < p_2 < \ldots < p_k$ are primes. Determine all integers $n \geq 3$ for which $\alpha_1, \alpha_2, \ldots, \alpha_k$ is a geometric progression.
Problem
Source: MEMO 2017 T8
Tags: number theory, geometric sequence
rafayaashary1
25.08.2017 22:45
One method is to show that for all sufficiently large $n$, $2^{\pi(n)}>n-1\geq v_2(n!)$ by induction and Bertrand's Postulate.
Puzzled417
26.08.2017 01:32
The only such $n!$ for $n \leq 10$ are \begin{align*}3! &= 2 \cdot 3\\4! &= 2^3 \cdot 5\\6! &= 2^4 \cdot 3^2 \cdot 5\\10! &= 2^8 \cdot 3^4 \cdot 5^2 \cdot 7.\end{align*}We prove that these are all such $n!$.
Note that $11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11$. We prove that for $n \geq 11$, $n!$ contains two primes in its prime factorization to the first power.
By Bertrand's Postulate, if $n > 5$ is a positive integer then between $n$ and $2n$ there are at least two different primes. Thus if $n \geq 11$, then between $\dfrac{n}{2}$ and $n$ there are at least two different primes.
Let $p$ be a prime such that $\dfrac{n}{2} < p \leq n$. Then since for $k \geq 2$ we have $n < 2p < kp$, it follows that $p$ appears in the primes factorization of $n!$ exactly once.
Thus since the geometric progression contains two terms equal to $1$, the common ratio must be $1$, which is a contradiction since for $n \geq 4$ the common ratio must be less than $1$. Therefore, the answers are $n = 3,4,6,10$.
euklid
26.08.2017 13:16
Puzzled417 wrote:
The only such $n!$ for $n \leq 10$ are \begin{align*}3! &= 2 \cdot 3\\4! &= 2^3 \cdot 5\\6! &= 2^4 \cdot 3^2 \cdot 5\\10! &= 2^8 \cdot 3^4 \cdot 5^2 \cdot 7.\end{align*}We prove that these are all such $n!$.
We prove that for $n \geq 11$, $n!$ contains two primes in its prime factorization to the first power.
For $n = 11$, we have $n! = 11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11$. Now in order to get a geometric progression in the exponents, $n$ must be the next multiple of $7$, which is $14$ but then we also get a single power of $13$ in $14!$. Then, $n \geq 14$ needs to be the next multiple of $11$ which is $22$, but then we get single powers of $17,19$ in $22$. Now we generalize this process:
We have the intervals $$(14,22),(22,26),(26,34)\ldots = \{(2p_{n-1},2p_n)\}_{n \geq 4},$$where $n$ must go from $2p_{n-1}$ to $2p_n$ in order to make $n!$'s smallest single power prime not a single power (note that no other single power prime is made not single in this process). There exists a prime $P$ such that $$2p_{n-1} < P < 2p_n$$by Bertrand's Postulate, so for every smallest single power of a prime in $n!$, we add at least one more when trying to make it not a single power.
This implies that the common ratio must be $1$, but for $n \geq 4$ the common ratio must be less than $1$, a contradiction. Therefore, $3,4,6,10$ are the answers.
@Puzzled417: You misused Bertrand's Postulate. If $p_{n-1}$ and $p_n$ are consecutive primes then a prime $P$ with $2p_{n-1} < P < 2p_n$ does not need to exist. Counterexample: $p_{n-1}=59$, $p_n=61$. There are no primes between $2\cdot 59=118$ and $2\cdot 61=122$.
smy2012
26.08.2017 15:00
If there are at least two primes in $(n/2,n]$, then $\alpha_k=\alpha_{k-1}=1$ which is impossible. And there are indeed at least two primes in $(n/2,n]$ with several small counter examples.
godjuansan
16.09.2017 17:56
anyone know the bound for $n$ in Andy Loo's proof of the extension of Bertrand's Postulate? (There is a prime number between $3n$ and $4n$) see here : https://en.wikipedia.org/wiki/Bertrand%27s_postulate
rkm0959
19.02.2018 17:28
We will take Bertrand's Postulate for granted. Manually check $n \le 12$ first. By Bertrand's Postulate, there exists a prime $p_k$ such that $\frac{n}{2} < p_k \le n$, and we have $\alpha_k = 1$. Now, notice that $n-1 \ge \alpha_1 \ge 2^{k-1}$. So we have $n \ge 2^{k-1}+1$, where $k= \pi (n)$. But we have $\pi (11) = 5$ and $\pi (2x) \ge \pi(x)+1$ by bertrand. It's not hard to form a contradiction now.
laikhanhhoang_3011
09.09.2021 11:20
file:///C:/Users/HP/Downloads/1195570997.pdf This doc kill this problem. From theorem in doc, we have (n;6/5.n) have a prime then (6/5.n; 36/25.n) also have a prime And 36/25 < 2 so (n;2n) have 2 prime And we are done as above
lazizbek42
11.01.2022 14:59
Bertrand's Postulate
green_leaf
11.01.2022 16:35
Slightly different. Pick the largest prime in $[\tfrac{n}{4}, \tfrac{n}{2})$ and the smallest prime in $[\tfrac{n}{2}, n)$ (which exist due to Bertrand's Postulate). Clearly there is no prime in between the two primes. The former must have $\alpha_i = 3$ and the latter must have $\alpha_{i+1} = 1$. Since they are consecutive terms of the GP, the common ratio must be $3$. Now consider the largest prime in $[ \tfrac{n}{8}, \tfrac{n}{4})$ and the smallest prime in $[ \tfrac{n}{4}, \tfrac{n}{2})$. The former has $\alpha_j \leq 8$ and the latter has $\alpha_{j+1} = 3$, a contradiction to the fact that the common ratio is $3$.