Product of primes below some number $n$

Question

I was asked this question in an exam

For an integer $n>3$ denote by $f(n)$ the product of all prime numbers less than $n$. So $f(6) = 30$, $f(5) = 6$. Which of the following are true?

A. There are only finitely many $n$ such that $n|f(n)$.

B. There are only finitely many $n$ such that $n>f(n)$.

C. Given any $k,l \in \mathbb N$, $f(n)=kn+l$ has infinitely many solutions.

D. Let $S_k=\{l\in \mathbb N : f(l)=k\}$. Let $a_k=\frac 1 {|S_k|}$ if $S_k\neq\phi$, else $a_k=0$. Then $\sum_{i=1}^\infty a_i$ does not converge to a rational number.

Now, for A, I figured out an idea. Consider the set of the first $k$ primes $P_k=\{p_i : i\in \mathbb N_k \}$ where $\mathbb N_k=\{1,2,\dots ,k\}$ and let the $(k+1)$-th prime be $p_{k+1}$. Now consider the set of all possible products in $P_k$ given by $\prod P_k=\left\{\prod_{i=1}^m p_{\pi (i)} : p_j\in P_k, m\in \mathbb N_k, \pi \text{ is any permutation of }\mathbb N_k \right\}$. Now, if there is at least one element $x\in\prod P_k$ which is in the interval $(p_k,p_{k+1})$, then it is trivial that $x|f(x)$. And, I guess, there will always be such an $x$. However, a proof of this, or a better way will be appreciated.

For B, it is clear that $f(n)$ increases much much faster than $n$. So, it's no doubt that it's true. Again, I would like to have a rigorous proof of this.

For C, if we put $k=l=1$, we can intuitively see that $f(n)=n+1$ will not have infinitely many solutions (since $f(n)$ increases much much faster than $n+1$). Again, a proof of this will be appreciated.

My main problem was with D. I can figure out that $|S_k|\neq \phi$ iff $k$ is of the form $\prod_{i=1}^m p_i$ where $p_1,p_2,\dots ,p_m$ are the first $m$ primes. So, $a_k$ will either be $0$ (when $|S_k|=\phi$), or $a_k$ will be equal to the number of integers between $(p_{m}+1)$ and $p_{m+1}$. But, I can't see how to relate it with whether the sum will converge to a rational number or not. Please help me in these.

Edit: The answers of this question (according to the answer key) are B and D, all of which are done either on the comments or in the answers!!! Thanks to you all :)

Answer 1

Are you sure that the statement of D is correct? Could you check it please? Otherwise the series is divergent to infinity: $$\sum_{i=1}^\infty a_i=\sum_{k=0}^{\infty}\frac{1}{p_{k+1}-p_k}>\sum_{k=0}^{\infty}\frac{1}{p_{k+1}}=\infty.$$ For the last step see: Divergence of the sum of the reciprocals of the primes.

A proof of D if $a_k=\frac{|S_k|}{k}$ (which riminds the traditional irrationality proof of $e$).

We have that $$\sum_{i=1}^\infty a_i=\sum_{k=0}^{\infty}\frac{p_{k+1}-p_k}{\prod_{j=1}^kp_j}.$$ Assume that such series converges to the rational number $\frac{a}{b}$ with $a,b\in\mathbb{N}^+$. Then $$\frac{a}{b}=\sum_{k=0}^{\infty}\frac{p_{k+1}-p_k}{\prod_{j=1}^kp_j}.$$ Let $N>0$ be such that $b\leq \prod_{j=1}^Np_j$, then $$\prod_{j=1}^Np_j\left(\frac{a}{b}-\sum_{k=0}^{N}\frac{p_{k+1}-p_k}{\prod_{j=1}^kp_j}\right)=\sum_{k=N+1}^{\infty}\frac{p_{k+1}-p_k}{\prod_{j=N+1}^kp_j}.$$ Now the LHS is a positive integer, that is $LHS\geq 1$. We have a contradiction as soon as we show that the $RHS<1$. Since $p_{k+1}/p_k\to 1$, we may assume that $N$ is large enough such that $p_{k+1}-p_k<\frac{p_k}{2}$. Then $$RHS=\sum_{k=N+1}^{\infty}\frac{p_{k+1}-p_k}{\prod_{j=N+1}^kp_j}<\frac{1}{2}\sum_{k=N+1}^{\infty}\frac{1}{\prod_{j=N+1}^{k-1}p_j}\leq \sum_{k=N+1}^{\infty}\frac{1}{2^{k-N}}=1.$$

Answer 2

(a) for any prime $p$, clearly $2p$ divides $f(2p)$. (b) Suppose, for contradiction, there is an $n>3$ such that $n>f(n)$, then n> $p_1 p_2 ... p_k$ where $p_k$ is the maximum prime less than $n$, however for $n>3$ we have $p_1 p_2 ... p_{k-1} > p_1 = 2$ so $n> 2p_k >p_k$, however by Bertrand's postulate there is at least one prime $q$ strictly between $2p_k$ and $p_k$, so $n>q>p_k$, contradicting that $p_k$ is the greatest prime less than $n$. Hence there are no $n>3$ such that $n>f(n)$.

Answer 3

Proofs for B and C:

B) From Bertrand's Postulate, for any $n>3$, a prime $p$ exists such that $\lceil \frac{n}{2}\rceil\leq p<n$. Now, for $n>8$, we have that $n<6p\leq f(n)$. This means that the only possible $n$ where $n>f(n)$ are $n\leq 8$, which means that there are finitely many, making B true. In fact, testing these cases show that $f(n)-n>0$ for all $n>3$.

C) It's a problem worth further discussion to find how many solutions $f(n)=kn+l$ has for any given $k,l\in\mathbb{N}$. However, any pairing of $k,l$ will have at most finitely many solutions, as $f(n)$ grows faster than linearly with respect to $n$. This can be proven in many ways. One such example is to use the following generalization of Bertrand's Postulate, proven by Erdos: for any $m\in\mathbb{N}$, there exists $N_m$ such that for all $n>N_m$, there are at least $m$ distint primes between $n$ and $2n$. This means that $f(2n)>n^mf(n)$ for sufficiently large $n$. Then, we can use Bertrand's Postulate to show that $f(n)>6n$ for $n>8$, and we can substitute this into the above expression to show that $f(2n)>6n^{m+1}$. Replace $n$ with $\frac{n}{2}$ to get that $f(n)>\frac{3n^{m+1}}{2^m}$. Then, substitute $m=2$ to get that for all $n>N_2$, $f(n)>\frac{3n^3}{4}>n^2$. Now, because there are at most two integer solutions of $n^2=kn+l$, and that for $n>N_2$, $f(n)>n^2$ and increases faster than $n^2$, we can place an upper bound on the number of solutions of $N_2+2$ for any $k,l$ (realistically, we can probably greatly shrink this upper bound, as well as actually substitute the correct value for $N_2$, which I believe is $6$ but haven't seen any proof for its actual value, but the point here is to show that the number of solutions is finite).