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

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

$\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?

  • $\begingroup$ 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. $\endgroup$ Jun 20, 2012 at 19:48

1 Answer 1


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}} $$


$$ \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}$.

  • $\begingroup$ 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) $\endgroup$ Dec 20, 2011 at 17:48
  • $\begingroup$ 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! $\endgroup$ May 11, 2012 at 17:56
  • $\begingroup$ Oh, thanks very much! If there is more to say about the general case, I'll let you know! $\endgroup$ May 23, 2012 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.