MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 . 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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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