5
$\begingroup$

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

f[n_]=Sum[MangoldtLambda[i],{i,1,n}];

Sum[(-1)^n(f[n]/n-MangoldtLambda[n]/(2n)),{n,2,Infinity}]
$\endgroup$
5
  • $\begingroup$ What precisely is your problem? $\endgroup$ Nov 14, 2013 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$ Nov 14, 2013 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$ Nov 14, 2013 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$ Nov 14, 2013 at 9:03
  • $\begingroup$ so if you want a ChebyshevPsi function you should got with: Log[LCM@@Range[n]] $\endgroup$
    – Stefan
    Nov 14, 2013 at 9:16

1 Answer 1

15
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Can you tell me the numerical value $\endgroup$
    – Surya
    Nov 14, 2013 at 13:44
  • $\begingroup$ @Surya of what upper bound? $\endgroup$
    – Stefan
    Nov 14, 2013 at 14:04
  • $\begingroup$ Upper bound is infinity. $\endgroup$
    – Surya
    Nov 14, 2013 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, 2013 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, 2013 at 14:27

Your Answer

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

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