在 Raku 中，如何计算素因数分解的正因数之和？

Question

---

\n

在 Raku 中，给定一个对列表(\xe2\x80\xaf表示 n = 2 ^{\xe2\x80\xaf3 \} xc2\xb7 3 ^{\xe2\x80\xaf2} \xc2\xb7 5 ^{\xe2\x80\xaf1}(2 => 3, 3 => 2, 5 => 1, 7 => 4)的质因数分解\xc2\xb7 7 ^{\xe2\x80\xaf4} \xe2\x80\xaf)，如何构造\xcf\x83(n) = (\xe2\x80\xaf2 ^{\xe2\x80\xaf0} + 2 ^{\ xe2\x80\xaf1} + 2 ^{\xe2\x80\xaf2} + 2 ^{\xe2\x80\xaf3} \xe2\x80\xaf) \xc2\xb7 (\xe2\x80\xaf3 \ ^xe2\x80\xaf0 + 3 ^{\xe2\ x80\xaf1} + 3 ^{\xe2\x80\xaf2} \xe2\x80\xaf) \xc2\xb7 (\xe2\x80\xaf5 ^{\xe2\x80\xaf0} + 5 ^{\xe2\x80\xaf1} \xe2\x80\xaf) \xc2\xb7 (\xe2\x80\xaf7 ^{\xe2\x80\xaf0} + 7 ^{\xe2\x80\xaf1} + 7 ^{\xe2\x80\xaf2} + 7 ^{\xe2\x80\xaf3} + 7 ^{\xe2\x80\xaf4} \ xe2\x80\xaf)\xe2\x80\xaf?

\n

sub MAIN()\n  {\n  my $pairList = (2 => 3, 3 => 2, 5 => 1, 7 => 4) ;\n  say \'$pairList\' ;\n  say $pairList ;\n  say $pairList.WHAT ;\n  # Goal:\n  #   from $pairList,\n  #   the product (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5) * (1 + 7 + 49 + 343 + 2401)\n  #   = sigma ( 2^3 * 3^2 * 5^1 * 7^4 )\n  } # end sub MAIN\n

\n

---

\n

更新1

\n

根据@raiph的回答，以下程序将整个过程分为几个阶段，供Raku新手（例如我）\xe2\x80\xa6

\n

sub MAIN()\n  {\n  my $pairList = (2 => 3, 3 => 2, 5 => 1, 7 => 4) ;\n  say \'$pairList\' ;\n  say $pairList ;\n  say $pairList.WHAT ;\n\n  # Goal:\n  #   from $pairList,\n  #   the product (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5) * (1 + 7 + 49 + 343 + 2401)\n  #   the product (15) * (13) * (6) * (2801)\n  #   sigma ( 2^3 * 3^2 * 5^1 * 7^4 )\n  #   3277170\n\n  # Stage 1 : ((1 2 4 8) (1 3 9) (1 5) (1 7 49 343 2401))\n  my $stage1 = $pairList.map: { (.key ** (my $++)) xx (.value + 1) } ;\n  say \'$stage1 : lists of powers\' ;\n  say $stage1 ;\n  say $stage1.WHAT ;\n\n  # Stage 2 : ((1 + 2 + 4 + 8) (1 + 3 + 9) (1 + 5) (1 + 7 + 49 + 343 + 2401))\n  my $stage2 = $stage1.map: { sum $_ } ;\n  say \'$stage2 : sum each list\' ;\n  say $stage2 ;\n  say $stage2.WHAT ;\n\n  # Stage 3 : (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5) * (1 + 7 + 49 + 343 + 2401)\n  my $stage3 = $stage2.reduce( &infix:<*> ) ;\n  say \'$stage3 : product of list elements\' ;\n  say $stage3 ;\n  say $stage3.WHAT ;\n  } # end sub MAIN\n

\n

---

\n

相关帖子出现在Mathematics Stack Exchange上。

\n

---

\n

更新2

\n

我最初的动机是计算等分总和 s(n) = \xcf\x83(n) - n。我发现每个n的质因数分解是不必要的，而且似乎效率低下。Raku 和 C++ 程序计算s(n) for n = 0 \xe2\x80\xa6 10 ^{\xe2\x80\xaf6}遵循 \xe2\x80\xa6

\n

乐

\n

sub MAIN()\n  {\n  constant $limit = 1_000_000 ;\n\n  my @s of Int = ( 1 xx ($limit + 1) ) ;\n  @s[0] = 0 ;\n  @s[1] = 0 ;\n\n  loop ( my $column = 2; $column <= ($limit + 1) div 2; $column++ )\n    {\n    loop ( my $row = (2 * $column); $row <= $limit; $row += $column )\n      {\n      @s[$row] += $column ;\n      } # end loop $row\n    } # end loop $column\n\n  say "s(", $limit, ") = ", @s[$limit] ; # s(1000000) = 1480437\n  } # end sub MAIN\n

\n

C++

\n

（观察到执行速度明显快于 Raku）

\n

#include <iostream>\n#include <vector>\nusing namespace std ;\n\nint main ( void )\n  {\n  const int LIMIT = 1000000 ;\n  vector<int> s ( (LIMIT + 1), 1 ) ;\n  s[0] = 0 ;\n  s[1] = 0 ;\n  for ( int col = 2 ; col <= (LIMIT + 1) / 2 ; col++ )\n    for ( int row = (2 * col) ; row <= LIMIT ; row += col )\n      s[row] += col ;\n  cout << "s(" << LIMIT << ") = " << s[LIMIT] << endl ; // s(1000000) = 1480437\n  } // end function main\n\n

\n

---

\n

Answer 1

会有无数种方法。我忽略了算法效率。我写的第一件事是：

say [*] (2 => 3, 3 => 2, 5 => 1, 7 => 4) .map: { sum .key ** my $++ xx .value + 1 }

显示：

3277170

解释

 1 say
 2  [*]                       # `[op]` is a reduction. `[*] 6, 8, 9` is `432`.
 3    (2 => 3, 3 => 2, 5 => 1, 7 => 4)
 4      .map:
 5        {
 6          sum
 7            .key            # `.key` of `2 => 3` is `2`.
 8              **
 9                my          # `my` resets `$` for each call of enclosing `{...}`
10                  $++       # `$++` integer increments from `0` per thunk evaluation.
11                    xx      # `L xx R` forms list from `L` thunk evaluated `R` times
12                      .value + 1
13        }