Advertisement
MatsGranvik

Faster higher dimensional sums for the Möbius function

Oct 1st, 2021 (edited)
470
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
Advertisement