# Can the relative count of the primefactors in $\small \lim_{w\to\infty}\prod_{k=1}^w (p_k-1)$ be determined analytically?

(I've posted this question earlier to MSE but did not receive answers, so I'll try it here. I also condensed the wording, hopefully not too much)

Let
$\displaystyle \small \qquad f_w = (2-1)(3-1)(5-1)\ldots(p_w-1) \qquad = \prod_{k=1}^w (prime(k)-1)$
or in general with a natural number for the exponent n
$\displaystyle \small (1) \qquad f_w(n) = (2^n-1)(3^n-1)(5^n-1)\ldots(p_w^n-1) \qquad = \prod_{k=1}^w (prime(k)^n-1)$
with w going to infinity.

Then let's denote the canonical primefactorization of that product
$\displaystyle \small (2) \qquad f_w(n) = 2^{a_{n,1}} \cdot 3^{a_{n,2}} \cdot 5^{a_{n,3}} \cdot \ldots \cdot q_k^{a_{n,k}} \cdot \ldots$
using q for the primefactors here to avoid confusion between the two representations.

I am interested, whether there is an analytical expression for the relative frequencies
$\small (3) \qquad r_w(n,k) = a_{n,k} / w$
in the limit in the latter expression.

Empirically (using the first 600000 primes in formula (1)) I found approximations to rational values for the relative frequencies of the first few primefactors q in formula (2) giving a somehow meaningful table, where, after scaling near to integers, for small primes q the error was in the near of 1/1000 . However, I cannot determine, whether the deviations from my estimated analytical formula are random and are vanishing in the limit or whether they keep a bias. Especially the primefactor q=2 in the formula (2) seems to have a nonrandom bias which might survive in the limit.

Here is the table. The entries $\small e_{n,q}$ give the rounded empirical frequencies $\small e_{n,q} \approx a_{n,k}/w \cdot (q-1)^2$

$\small \qquad \begin{array} {r|rrrrrrrrrrrr} n&2&3&5&7&11&13&17&19&23& (\ldots \text{ primefactor }q)\\ \hline \\ 1&2&3&5&7&11&13&17&19&23 \\ 2&4&6&10&14&22&26&34&38&46 \\ 3&2&5&5&21&11&39&17&57&23 \\ 4&5&6&20&14&22&52&68&38&46 \\ 5&2&3&9&7&55&13&17&19&23 \\ 6&4&10&10&42&22&78&34&114&46 \\ 7&2&3&5&13&11&13&17&19&23 \\ 8&6&6&20&14&22&52&136&38&46 \\ 9&2&7&5&21&11&39&17&171&23 \\ 10&4&6&18&14&110&26&34&38&46 \\ 11&2&3&5&7&21&13&17&19&253 \\ 12&5&10&20&42&22&156&68&114&46 \\ 13&2&3&5&7&11&25&17&19&23 \\ 14&4&6&10&26&22&26&34&38&46 \\ 15&2&5&9&21&55&39&17&57&23 \\ 16&7&6&20&14&22&52&272&38&46 \\ 17&2&3&5&7&11&13&33&19&23 \\ 18&4&14&10&42&22&78&34&342&46 \end{array}$

The heuristical formula that I extrapolated (letting w increase towards infinity) has two forms:

if q=2 and n is even (gcd(n,q)=2):
$\small \qquad e_{n,2} = (3 + \operatorname{val}( n,2 ) )$
where the function val(n,q) means: the exponent, to which primefactor q occurs in n

For all other cases
$\small \qquad e_{n,q} = \gcd(n,q-1) \cdot (q + (q-1)\cdot \operatorname{val}(n,q) )$

Then
$\small \qquad \displaystyle a_{n,q} = { e_{n,q} \cdot w \over (q-1)^2 }$

Can the guessed formula be confirmed by an analytical argument?

• I just found an extremely interesting and entertaining article "prime number races" by A.Granville and G.Martin in "The American Mathematical Monthly, Vol. 113, No. 1 (Jan., 2006), pp. 1-33" with a permanent online-link at jstor.org/stable/27641834 . That article exhibits another view into the problem, with which I had also tried to confirm my guesses here. – Gottfried Helms Jun 20 '12 at 19:48

Mr Helms,

This is the $n=1$ case. Your formula gives $e_{1,q}=q$. Say we want to study how often prime $q=q_k$ divides $\prod_{p \leq x}(p-1)$. Maybe write this product as $$\left(\prod_{i=1}^m\prod_{\substack{p \leq x\\ p \in (q^{i-1}\mathbb{Z}+1)\setminus(q^{i}\mathbb{Z}+1)}}(p-1)\right) \times \prod_{\substack{p \leq x\\ p \in (q^{m}\mathbb{Z}+1)}}(p-1).$$ If $m$ is the right size relative to $x$, then counting primes $p$ in $(q^{i-1}\mathbb{Z}+1)\setminus(q^{i}\mathbb{Z}+1)$, $i \leq m$ can be done by an asymptotic version of Dirichlet's theorem on primes in arithmetic progressions. (Siegel-Walfisz theorem)

Equating $\prod_{p \leq x}(p-1)$ and $\prod_{k=1}^{w}(p_k-1)$, we get $w \approx x/\log x$.

If $q^i \ll (\log x)^N$, as required by Siegel-Walfisz theorem, then the number of primes $p \leq x$ in $(q^{i-1}\mathbb{Z}+1)\setminus(q^{i}\mathbb{Z}+1)$, $i>1$, is $\frac{q-1}{\varphi(q^i)}\frac{x}{\log x} + O\left(x \exp(-c_N (\log x)^{1/2})\right) = \frac{x}{q^{i-1}\log x} + O\left(x \exp(-c_N (\log x)^{1/2})\right)$. The number of primes $p \leq x$ in $q^m\mathbb{Z}+1$ is $\frac{x}{q^{m-1}(q-1)\log x}+O\left(x \exp(-c_N (\log x)^{1/2})\right)$. So, a lower bound for $a_{1,k}/w$ is

$$\left(\left(\frac{m}{q^{m-1}(q-1)}+\sum_{i=1}^m\frac{i-1}{q^{i-1}}\right)\frac{x}{\log x} + O\left(x \exp(-c_N (\log x)^{1/2})\right)\right)/\left(x/\log x\right)$$ where $q^m \ll (\log x)^N$. Upon taking $x \rightarrow \infty$, we may replace

$$\frac{m}{q^{m-1}(q-1)}+\sum_{i=1}^m\frac{i-1}{q^{i-1}}$$

with

$$\sum_{i=1}^{\infty}\frac{i-1}{q^{i-1}} = \frac{q}{(q-1)^2}$$

and what is obtained agrees with your formula for $e_{1,q}$.

• Hmm, thank you for your input - I'll need a certain time to digest this. I was approaching the problem using little Fermat/Euler's totient function (and the connection to geometric series for the infinite case) but, for instance, was unsecure, what effect the higher fermat-quotients would introduce- they should "lift" the sums of primefactors q - but their occurences have no simple formula. Well, such effects should vanish if w goes to infinity (if their occurences are finite), but we do not know this (that was one of the main reasons, that I looked into experimental heuristics at all) – Gottfried Helms Dec 20 '11 at 17:48
• I'm "accepting" the answer because there has been no more activity for a long time. Your derivation is helpful anyway and I'll try to generalize it. Thanks for your input! – Gottfried Helms May 11 '12 at 17:56
• Oh, thanks very much! If there is more to say about the general case, I'll let you know! – Timothy Foo May 23 '12 at 11:03