Can anybody evaluate the following sum for me

$$ \sum\limits_{n=2}^\infty(-1)^n\left(\frac{\psi(n)}{n}-\frac{\Lambda(n)}{2n}\right) $$

where $\psi(n)$ is the Chebyshev function and $\Lambda(n)$ is the von Mangoldt function. Is there any efficient algorithm to evaluate such sum? I used the following code


  • $\begingroup$ What precisely is your problem? $\endgroup$ – Sjoerd C. de Vries Nov 14 '13 at 8:51
  • $\begingroup$ @stefan I expect the OP to say something like "I expect to get ..., because ... but I get ..." or "I get such and such error". $\endgroup$ – Sjoerd C. de Vries Nov 14 '13 at 8:56
  • $\begingroup$ As posted the code defined f as the product of two sums. I take it that was not your intention and I split the code in a definition part and a separate sum, which I suppose demonstrates your problem in some (still to explained) way. $\endgroup$ – Sjoerd C. de Vries Nov 14 '13 at 9:01
  • $\begingroup$ @stefan it is difficult to infer if that was the problem. If the OP had those lines of code in separate cells they probably would have worked. $\endgroup$ – Sjoerd C. de Vries Nov 14 '13 at 9:03
  • $\begingroup$ so if you want a ChebyshevPsi function you should got with: Log[LCM@@Range[n]] $\endgroup$ – Stefan Nov 14 '13 at 9:16

Number theory questions are always a huge accumulator for up votes. :)

From my experience I can say that the builtin MangoldtLambda function is pretty slow.

So let's define a Mangoldt function on our own. The Mangoldt function is defined by:

$\Lambda(n) \equiv \left\{ \begin{array}{1 1} \ln\ p & \quad \text{if n = $p^k$ for p a prime}\\ 0 & \quad \text{otherwise} \end{array} \right.$

This can be implemented as follows:

MangoldtΔ[n_] := If[Length[#] === 1, Log[#[[1, 1]]], 0] &[FactorInteger[n]]

Let's check some identities, if this implementation is correct:

$\sum_{d | n} \Lambda(d) = \ln\ n$

If we check this for n = 13:

Plus @@ (MangoldtΔ[#] & /@ Divisors[13])

==> Log[13]

Which is correct. Another identity is the following:

$\sum_{d | n} \mu(d)\ \ln(d) = -\Lambda(n)$ where $\mu$ is the Möbius function which is defined by:

$\mu(n) \equiv \left\{ \begin{array}{1 1} 0 & \quad \text{if $n$ has one or more repeated prime factors}\\ 1 & \quad \text{if $n=1$}\\ (-1)^k & \quad \text{if $n$ is a product of $k$ distinct primes} \end{array} \right.$

The first clause says nothing else but that n has to be square free:

MySquareFreeQ[n_] := Max[Last /@ FactorInteger[n]] < 2

(There is a SquareFreeQ function in Mathematica, so this is just if you're interested in how to implement such an algorithm)

Although there is a MobiusMu function in Mathematica we can define our own as well:

Moebiusμ[n_ /; MySquareFreeQ[n] == False] := 0
Moebiusμ[1] := 1
Moebiusμ[n_] := (-1)^Length@FactorInteger[n]

Now we can check this identity:

Plus @@ (Moebiusμ[n/#] Log[#] & /@ Divisors[13])

=> Log[13]

which is again correct.

Now let's do some timings with our new MangoldtΔ function:

Timing[Sum[MangoldtLambda[n], {n, 10^4}] // N]
=> {0.187940, 10013.4}

Timing[Sum[MangoldtΔ[n], {n, 10^4}] // N]
=> 0.065199, 10013.4}

We can see some improvement over time with our own implementation, but can we do better?

There is another identity with the Mangoldt which says:

$\psi(x) = \sum_{n \leq x} \Lambda(n)$

where $\psi(x)$ denotes the Chebyshev function. In my comments I already mentioned this function:

Chebyshevψ[x_] := Log[LCM @@ Range[x]]

Let's use the Chebyshevψ instead of Sum[Mangoldt...]:

Timing[ChebyshevPsi[10^4] // N]
=> {0.011974, 10013.4}

even better.

Equipped with these definitions and the proof of their correctness we can implement now your summation formula quite efficient:

Func[i_] := With[{iter = i}, 
    Sum[(-1)^n ((Chebyshevψ[n]/n) - (MangoldtΔ[n]/(2 n))), {n, 2, iter}]]

ListLinePlot[Table[Func[n], {n, 100}]]

Edit: Thank you Artes for pointing out the bug in (MangoldtΔ[n]/2 n)). Now this looks quite different.

enter image description here

  • $\begingroup$ Can you tell me the numerical value $\endgroup$ – Surya Nov 14 '13 at 13:44
  • $\begingroup$ @Surya of what upper bound? $\endgroup$ – Stefan Nov 14 '13 at 14:04
  • $\begingroup$ Upper bound is infinity. $\endgroup$ – Surya Nov 14 '13 at 14:10
  • $\begingroup$ @Surya then there is no numerical value, only a symbolic one. Infinity does not work for e.g. Range. i'm sorry but my solution does not work for infinity and this will be so as long as there is no lazy Range in Mathematica... $\endgroup$ – Stefan Nov 14 '13 at 14:16
  • $\begingroup$ @Stefan Not necessarily memoization, but whatever can avoid calculating the same values many times, e.g. computing Func[100] you compute Func for all smaller arguments so I guess memeoization might be a real improvement. $\endgroup$ – Artes Nov 14 '13 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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