valuation(2, prime(n)-1)

[Pieter Moree]

Cloitre wrote:

> Letting S(n)=sum(i=2, n, valuation(2, prime(i)-1) )
>
> I suppose limit n-->infty S(n)/n = 2
This is true and is not too difficult to prove:

The primes

(*) p=1(mod 2^m) that are not =1(mod 2^{m+1})

have
density 2^{-m} and contribute m/2^m to the density.
Summing this for m is 1 to infty then yields the result.
(This is the idea, in the proof one ought be a bit more careful.)

In my recent preprint `Asymptotically exact heuristics for prime
divisors of the sequence a^k+b^k, k=1,2,....

valuation(2,p-1) also plays  an important role in the form
of sum_{p\le x}2^{-valutation(2,p-1)} (and more complicated ones).
Vide the ArXiv or http://staff.science.uva.nl/~moree/preprints.html.

The primes satisfying (*) are the primes that split completely in
the cyclotomic field Q(\zeta_{2^m}) and do not split completely
in Q(\zeta_{2^{m+1}). Counting these primes yields an error term
of order sqrt{x}logx if one believes in the Riemann Hypothesis
for the Dedekind zeta function associated to Q(\zeta_{2^{m+1}}).

> I asked myself if (2n-S(n))/sqrt(n) is bounded with S(n)<2n
In my opinion this is rather too optimistic. If one assumes
the Generalized Riemann Hypothesis then one can show there
is a constant c such that if one replaces aqrt(n) by
sqrt(n)(log n)^c, then the quotient is bounded.

>and if
> limit n-->infty (2n-S(n))/sqrt(n) exist ?
I am convinced the answer is: NO. S(n) is quite irregular.
The analog to think of is: (pi(x)-Li(x))/sqrt{x}.
It can be proved that this does not have a limit.
Presumably variations of these techniques can be used to deal with
the latter two questions conclusively.

> With n=40000 I obtained (2n-S(n))/sqrt(n) = 0.7....
>
> sum(i=2,40000,valuation(prime(i)-1,2))=79859 and
> (2*40000-79859)/sqrt(40000)=0.705
>
> I don't believe that's specific to primes but thanks for confirming or
> not this fact.
Oh yes it is ! Instead of the primes take the odd integers
<=x. A different
picture emerges there ! The fluctations will be quite small
now (indeed bounded by a constant times (log x)^2...)

If instead of primes one takes
primes =a(mod d) with a and d coprime and d odd, then the same
features should arise, however.

Pieter Moree