2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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]=1 ; a[n_]:=a[n]=Limit[...] ) also b could be precomputed outside the loop, but I doubt that's your bottleneck. $\endgroup$ – george2079 Oct 16 '14 at 14:50
  • $\begingroup$ Yes, thanks I realized that too now. $\endgroup$ – Mats Granvik Oct 16 '14 at 14:51
5
$\begingroup$

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)}

$\endgroup$
2
$\begingroup$

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.

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

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.

$\endgroup$

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.