MatsGranvik

Faster higher dimensional sums for the Möbius function

Oct 1st, 2021 (edited)
493
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.08 KB | None | 0 0
  1. This formulation of the Möbius function:
  2.  
  3. (*start*)
  4. (*Mathematica*)
  5. nn = 2^7 - 1
  6. Monitor[
  7. Table[
  8. +If[n == 2^0, 1, 0]
  9. - If[n < 2^1, 0, Sum[If[a == n, 1, 0], {a, 2, n/2^0}]]
  10. + If[n < 2^2, 0,
  11. Sum[Sum[If[a*b == n, 1, 0], {a, 2, n/2^1}], {b, 2, n/2^1}]]
  12. - If[n < 2^3, 0,
  13. Sum[Sum[Sum[If[a*b*c == n, 1, 0], {a, 2, n/2^2}], {b, 2,
  14. n/2^2}], {c, 2, n/2^2}]]
  15. + If[n < 2^4, 0,
  16. Sum[Sum[Sum[
  17. Sum[If[a*b*c*d == n, 1, 0], {a, 2, n/2^3}], {b, 2, n/2^3}], {c,
  18. 2, n/2^3}], {d, 2, n/2^3}]]
  19. - If[n < 2^5, 0,
  20. Sum[Sum[Sum[
  21. Sum[Sum[If[a*b*c*d*e == n, 1, 0], {a, 2, n/2^4}], {b, 2,
  22. n/2^4}], {c, 2, n/2^4}], {d, 2, n/2^4}], {e, 2, n/2^4}]]
  23. + If[n < 2^6, 0,
  24. Sum[Sum[Sum[
  25. Sum[Sum[Sum[If[a*b*c*d*e*f == n, 1, 0], {a, 2, n/2^5}], {b, 2,
  26. n/2^5}], {c, 2, n/2^5}], {d, 2, n/2^5}], {e, 2, n/2^5}], {f,
  27. 2, n/2^5}]]
  28. - If[n < 2^7, 0,
  29. Sum[Sum[Sum[
  30. Sum[Sum[Sum[
  31. Sum[If[a*b*c*d*e*f*g == n, 1, 0], {a, 2, n/2^6}], {b, 2,
  32. n/2^6}], {c, 2, n/2^6}], {d, 2, n/2^6}], {e, 2,
  33. n/2^6}], {f, 2, n/2^6}], {g, 2, n/2^6}]]
  34. + If[n < 2^8, 0,
  35. Sum[Sum[Sum[
  36. Sum[Sum[Sum[
  37. Sum[Sum[If[a*b*c*d*e*f*g*h == n, 1, 0], {a, 2, n/2^7}], {b,
  38. 2, n/2^7}], {c, 2, n/2^7}], {d, 2, n/2^7}], {e, 2,
  39. n/2^7}], {f, 2, n/2^7}], {g, 2, n/2^7}], {h, 2, n/2^7}]], {n,
  40. 1, nn}], n]
  41. Monitor[Table[MoebiusMu[n], {n, 1, nn}], n]
  42. %% - %
  43. Count[%, 0]
  44. (*end*)
  45.  
  46. should be possible to combine with this Hurwitz zeta function:
  47.  
  48. (*start*)
  49. Clear[a, b, c, sigma, n, s];
  50. nn = 200;
  51. a = 2;
  52. b = 3;
  53. c = 7;
  54. sigma = 1/2;
  55. s = sigma + c*I;
  56. Limit[Sum[1/k^s, {k, 1, a*n}] - Sum[1/k^s, {k, 1, b*n}], n -> 100]
  57. Clear[n];
  58. Show[ListPlot[
  59. Table[Re[Sum[1/k^s, {k, 1, a*n}] - Sum[1/k^s, {k, 1, b*n}]], {n, 1,
  60. nn}]],
  61. ListLinePlot[
  62. Table[Re[HurwitzZeta[s, b*n + 1] - HurwitzZeta[s, a*n + 1]], {n, 1,
  63. nn}], PlotStyle -> Red]]
  64. Chop[N[Table[
  65. Re[Sum[1/k^s, {k, 1, a*n}] - Sum[1/k^s, {k, 1, b*n}]], {n, 1,
  66. nn}] - Table[
  67. Re[HurwitzZeta[s, b*n + 1] - HurwitzZeta[s, a*n + 1]], {n, 1,
  68. nn}]]]
  69. "This transformation given by Mathematica should be possible to use \
  70. in the Möbius function sum:"
  71. Chop[N[Table[Re[Sum[1/k^s, {k, 1, a*n}]], {n, 1, nn}] -
  72. Table[Re[Zeta[s] - HurwitzZeta[s, a*n + 1]], {n, 1, nn}]]]
  73. (*end*)
  74.  
  75. The main obstacle though is the missing exact formula for the
  76. Dirichlet Divisor problem, as well as higher dimensional variants
  77. thereof known as the Piltz divisor problem.
  78.  
  79.  
  80. (*start*)
  81. (* Feb 9 2022 fungerande Mathematica*)
  82. nn = 2^7 - 1
  83. m1 = Table[+If[n == 2^0,
  84. 1, \
  85. \
  86. 0], {n, 1, nn}]
  87. m2 = Table[-If[n < 2^1, 0,
  88. Sum[
  89. If[a == n, 1, 0], {a, 2,
  90. n/2^0}] ], {n, 1, nn}]
  91. m3 = Table[+If[n < 2^2, 0,
  92. Sum[Sum[If[a*b == n, 1, 0], {a, 2, n/2^1}], {b, 2,
  93. n/2^1}]], {n, 1, nn}]
  94. m4 = Table[-If[n < 2^3, 0,
  95. Sum[Sum[If[a*b == n, m3[[a]], 0], {a, 2, n/2^1}], {b, 2,
  96. n/2^1}]], {n, 1, nn}]
  97. m5 = Table[-If[n < 2^4, 0,
  98. Sum[Sum[If[a*b == n, m4[[a]], 0], {a, 2, n/2^1}], {b, 2,
  99. n/2^1}]], {n, 1, nn}]
  100. m6 = Table[-If[n < 2^5, 0,
  101. Sum[Sum[If[a*b == n, m5[[a]], 0], {a, 2, n/2^1}], {b, 2,
  102. n/2^1}]], {n, 1, nn}]
  103. m7 = Table[-If[n < 2^6, 0,
  104. Sum[Sum[If[a*b == n, m6[[a]], 0], {a, 2, n/2^1}], {b, 2,
  105. n/2^1}]], {n, 1, nn}]
  106. m8 = Table[-If[n < 2^7, 0,
  107. Sum[Sum[If[a*b == n, m7[[a]], 0], {a, 2, n/2^1}], {b, 2,
  108. n/2^1}]], {n, 1, nn}]
  109. m9 = Table[-If[n < 2^8, 0,
  110. Sum[Sum[If[a*b == n, m8[[a]], 0], {a, 2, n/2^1}], {b, 2,
  111. n/2^1}]], {n, 1, nn}]
  112. Accumulate[m1 + m2 + m3 + m4 + m5 + m6 + m7 + m8 + m9]
  113. Monitor[Accumulate[Table[MoebiusMu[n], {n, 1, nn}]], n]
  114. %% - %
  115. Count[%, 0]
  116. M1 = Table[
  117. Sum[If[Mod[n, k] == 0, m1[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  118. M2 = Table[
  119. Sum[If[Mod[n, k] == 0, m2[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  120. M3 = Table[
  121. Sum[If[Mod[n, k] == 0, m3[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  122. M4 = Table[
  123. Sum[If[Mod[n, k] == 0, m4[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  124. M5 = Table[
  125. Sum[If[Mod[n, k] == 0, m5[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  126. M6 = Table[
  127. Sum[If[Mod[n, k] == 0, m6[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  128. M7 = Table[
  129. Sum[If[Mod[n, k] == 0, m7[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  130. M8 = Table[
  131. Sum[If[Mod[n, k] == 0, m8[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  132. M9 = Table[
  133. Sum[If[Mod[n, k] == 0, m9[[n/k]], 0], {k, 1, nn}], {n, 1, nn}]
  134. M1 + M2 + M3 + M4 + M5 + M6 + M7 + M8 + M9
  135. Accumulate[%]
  136. (*end*)
  137.  
  138.  
  139. (*start better*)
  140. (*Feb 9 2022 fungerande Mathematica*)
  141. nn = 2^7 - 1
  142. "1"
  143. m1 = Table[+If[
  144. n == 2^0, 1,
  145. 0] \
  146. , {n, 1, nn}]
  147. "2"
  148. m2 = Table[-If[n < 2^1, 0,
  149. Sum[If[ a == n, 1, 0], {a, 2,
  150. n/2^0}] ] , {n, 1, nn}]
  151. "3"
  152. m3 = Table[-If[n < 2^2, 0,
  153. Sum[Sum[If[a*b == n, m2[[a]] , 0], {a, 2, n/2^1}], {b, 2,
  154. n/2^1}]], {n, 1, nn}]
  155. "4"
  156. m4 = Table[-If[n < 2^3, 0,
  157. Sum[Sum[If[a*b == n, m3[[a]], 0], {a, 2, n/2^1}], {b, 2,
  158. n/2^1}]], {n, 1, nn}]
  159. "5"
  160. m5 = Table[-If[n < 2^4, 0,
  161. Sum[Sum[If[a*b == n, m4[[a]], 0], {a, 2, n/2^1}], {b, 2,
  162. n/2^1}]], {n, 1, nn}]
  163. "6"
  164. m6 = Table[-If[n < 2^5, 0,
  165. Sum[Sum[If[a*b == n, m5[[a]], 0], {a, 2, n/2^1}], {b, 2,
  166. n/2^1}]], {n, 1, nn}]
  167. "7"
  168. m7 = Table[-If[n < 2^6, 0,
  169. Sum[Sum[If[a*b == n, m6[[a]], 0], {a, 2, n/2^1}], {b, 2,
  170. n/2^1}]], {n, 1, nn}]
  171. "8"
  172. m8 = Table[-If[n < 2^7, 0,
  173. Sum[Sum[If[a*b == n, m7[[a]], 0], {a, 2, n/2^1}], {b, 2,
  174. n/2^1}]], {n, 1, nn}]
  175. "9"
  176. m9 = Table[-If[n < 2^8, 0,
  177. Sum[Sum[If[a*b == n, m8[[a]], 0], {a, 2, n/2^1}], {b, 2,
  178. n/2^1}]], {n, 1, nn}]
  179. Accumulate[m1 + m2 + m3 + m4 + m5 + m6 + m7 + m8 + m9]
  180. Monitor[Accumulate[Table[MoebiusMu[n], {n, 1, nn}]], n]
  181. %% - %
  182. (*end better*)
Advertisement
Add Comment
Please, Sign In to add comment