# Can you compute more terms in this sequence?

I am trying to identify a sequence related to the von Mangoldt function matrix. Since I believe/conjecture that the columns in the matrix have period lengths as in this sequence b:

b = Table[Product[Exp[MangoldtLambda[n]], {n, 1, k}], {k, 1, nn}];


and since "b" grows rather fast, the computation capacity needed is above what my old computer can handle.

ii = 9
aa = Range[ii]*0;
Monitor[Do[
Clear[A, a, b, n, k];
b = Table[Product[Exp[MangoldtLambda[n]], {n, 1, k}], {k, 1, nn}];
a = Table[
If[n == 1, 1,
Limit[Zeta[s] Total[
Exp[Divisors[n]]^(s - 1)*MoebiusMu[Divisors[n]]],
s -> 1]], {n, 1, b[[nn]]}];
aa[[nn]] =
Min[Accumulate[
Total[Transpose[
Table[Table[a[[GCD[n, k]]]/k, {k, 2, nn}], {n, 2,
b[[nn]]}]]]]];, {nn, 2, ii}], nn]
aa
Differences[aa]


Ideally in the program above I would like to get the values of "aa" for the parameter "ii" equal to 32, but if not possible any amount of improvement beyond ii=9 is welcome.

The first terms of "aa" is:

{0, -(1/2), -(5/6), -(13/12), -(77/60), -(97/60), -(739/420), -(1583/ 840), -(1583/840)}

And the first differences of "aa" sofar is:

{-(1/2), -(1/3), -(1/4), -(1/5), -(1/3), -(1/7), -(1/8), 0}

The aim is to identify what this latter sequence is.

I would not like to give this away, but to the motivation for this question is that the sequence "aa" is a sure bound on the most negative term in a simplified version of the error term related to the Chebyshev function. It should also extend to the original error term in the Chebyshev function, but I am not sure.

• at a glance it seems only certain a values ever get used so you might make a a function that remembers it value instead of a table ( a=1 ; a[n_]:=a[n]=Limit[...] ) also b could be precomputed outside the loop, but I doubt that's your bottleneck. – george2079 Oct 16 '14 at 14:50
• Yes, thanks I realized that too now. – Mats Granvik Oct 16 '14 at 14:51

my stab at it, unfortunately only a marginal improvement in time:

 ii=13;
Clear[a, b];
b = FoldList[Times, 1, Table[ Exp[MangoldtLambda[n]], {n, 2, ii}]];
a = Prepend[Table[
Limit[
Zeta[s] Total[Exp[Divisors[n]]^(s - 1) MoebiusMu[Divisors[n]]],
s -> 1],
{n, 2, ii}], 1] ;
Monitor[aa = Prepend[Table[
Min[Accumulate[
Total@Table[a[[GCD[n, k]]]/k, {k, 2, nn}, {n, 2, b[[nn]]}]]],
{nn,2, ii}],0], nn] // Timing
aa
Differences[aa]


same results

Edit: this buys you a little more to precompute the inner table and take parts of it in the loop:

 z = Table[a[[GCD[n, k]]]/k, {k, 2, ii}, {n, 2, b[[ii]]}];
Monitor[aa =
Prepend[Table[
Min[Accumulate[Total@z[[;; nn - 1, ;; b[[nn]] - 1]]]],
{nn, 2, ii}], 0], nn]


Now if you look at the dimensions of that table you see for ii=32 you will have 10^15 entries (~30000Terabytes storage), so that this is an obviously impractical approach for large ii.

Edit2: results for ii=17

{0, -(1/2), -(5/6), -(13/12), -(77/60), -(97/60), -(739/420), -(1583/ 840), -(1583/840), -(1919/840), -(21949/9240), -(8343/3080), -( 111539/40040), -(128699/40040), -(430141/120120), -(875297/ 240240), -(15120289/4084080)}

{-(1/2), -(1/3), -(1/4), -(1/5), -(1/3), -(1/7), -(1/8), 0, -(2/5), -( 1/11), -(1/3), -(1/13), -(3/7), -(11/30), -(1/16), -(1/17)}

I realized now that I included unnecessary many terms of the Dirichlet inverse of the Euler totient.

Therefore a better program is:

ii = 13
aa = Range[ii]*0;
Monitor[Do[
Clear[A, a, b, n, k];
b = Table[Product[Exp[MangoldtLambda[n]], {n, 1, k}], {k, 1, nn}];
a = Table[
If[n == 1, 1,
Limit[Zeta[s] Total[
Exp[Divisors[n]]^(s - 1)*MoebiusMu[Divisors[n]]],
s -> 1]], {n, 1, nn}];
aa[[nn]] =
Min[Accumulate[
Total[Transpose[
Table[Table[a[[GCD[n, k]]]/k, {k, 2, nn}], {n, 2,
b[[nn]]}]]]]];, {nn, 2, ii}], nn]
aa
Differences[aa]


The sequence aa:

{0, -(1/2), -(5/6), -(13/12), -(77/60), -(97/60), -(739/420), -(1583/ 840), -(1583/840), -(1919/840), -(21949/9240), -(8343/3080), -( 111539/40040)}

First differences of "aa"

{-(1/2), -(1/3), -(1/4), -(1/5), -(1/3), -(1/7), -(1/8), 0, -(2/5), -( 1/11), -(1/3), -(1/13)}

Might be that further improvement with some mathematical simplification, is possible.

• Shouldn't this be edited into the question itself? – Mr.Wizard Oct 16 '14 at 20:03

Denominators of first sequence: A003418, which are symmetric sequences of greatest divisors <= ii.

The denominators of the differences are these greatest divisors.

See here and here.

Edit: I missed that ii=9 is 840 instead of 2520 in the first sequence and is a zero instead of 9 in the second. So, the symmetry stops at 9. I'll leave this answer in case the links might be of help.