在Raku中，如何计算出主要分解的正分裂总和？

Question

---

在raku中，给定一个对列表（2 =＆gt; 3，3 =＆gt; 2，5 =＆gt; 1，7 =＆gt; 4）（表示 n的主要因素= 2 ³ ·3 ² ·5 ¹ ·7 ⁴ ），如何为 =（2 ⁰ + 2 ¹ + 2 ² + 2 ³ ）·（3 ⁰ + 3 ¹ + 3 ^{2 2 ）·（ 5 0 + 5 1 ）·（7 0 + 7 1 + 7 2 + 7 3 + 7 4 ）？}

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

---

根据@raiph的答案，更新1

，以下程序将整个过程分为新来的Raku（例如我）……

sub MAIN()
  {
  my $pairList = (2 => 3, 3 => 2, 5 => 1, 7 => 4) ;
  say '$pairList' ;
  say $pairList ;
  say $pairList.WHAT ;

  # Goal:
  #   from $pairList,
  #   the product (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5) * (1 + 7 + 49 + 343 + 2401)
  #   the product (15) * (13) * (6) * (2801)
  #   sigma ( 2^3 * 3^2 * 5^1 * 7^4 )
  #   3277170

  # Stage 1 : ((1 2 4 8) (1 3 9) (1 5) (1 7 49 343 2401))
  my $stage1 = $pairList.map: { (.key ** (my $++)) xx (.value + 1) } ;
  say '$stage1 : lists of powers' ;
  say $stage1 ;
  say $stage1.WHAT ;

  # Stage 2 : ((1 + 2 + 4 + 8) (1 + 3 + 9) (1 + 5) (1 + 7 + 49 + 343 + 2401))
  my $stage2 = $stage1.map: { sum $_ } ;
  say '$stage2 : sum each list' ;
  say $stage2 ;
  say $stage2.WHAT ;

  # Stage 3 : (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5) * (1 + 7 + 49 + 343 + 2401)
  my $stage3 = $stage2.reduce( &infix:<*> ) ;
  say '$stage3 : product of list elements' ;
  say $stage3 ;
  say $stage3.WHAT ;
  } # end sub MAIN

---

相关帖子出现在 数学”堆栈交换 。

---

更新2

我最初的动机是计算 > s（n）=σ（n）-n 。我发现每个 n 的主要分解不是必需的，而且似乎效率低下。 raku和c ++程序计算 s（n） for n = 0…10 ⁶ 关注…

raku

sub MAIN()
  {
  constant $limit = 1_000_000 ;

  my @s of Int = ( 1 xx ($limit + 1) ) ;
  @s[0] = 0 ;
  @s[1] = 0 ;

  loop ( my $column = 2; $column <= ($limit + 1) div 2; $column++ )
    {
    loop ( my $row = (2 * $column); $row <= $limit; $row += $column )
      {
      @s[$row] += $column ;
      } # end loop $row
    } # end loop $column

  say "s(", $limit, ") = ", @s[$limit] ; # s(1000000) = 1480437
  } # end sub MAIN

c ++

（观察到比Raku的执行速度要快得多）

#include <iostream>
#include <vector>
using namespace std ;

int main ( void )
  {
  const int LIMIT = 1000000 ;
  vector<int> s ( (LIMIT + 1), 1 ) ;
  s[0] = 0 ;
  s[1] = 0 ;
  for ( int col = 2 ; col <= (LIMIT + 1) / 2 ; col++ )
    for ( int row = (2 * col) ; row <= LIMIT ; row += col )
      s[row] += col ;
  cout << "s(" << LIMIT << ") = " << s[LIMIT] << endl ; // s(1000000) = 1480437
  } // end function main

---

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 `
有数十亿美元的方式。我忽略了算法效率。我写的第一件事：
say [*] (2 => 3, 3 => 2, 5 => 1, 7 => 4) .map: { sum .key ** my $++ xx .value + 1 }

显示：
3277170

解释
 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        }

Answer 2

对于这种操作，Raku不太可能比C ++更快。它仍然是生命的早期，并且有很多优化的优化，但是原始处理速度并不是它发光的地方。

如果您试图在连续范围内找到所有数字的等分试样总和，那么质量分解肯定不如您所获得的方法效率。有点像eratosthenes的反向筛。您可以更改一些事情以使其更快，尽管

在我的系统上的速度可能比C ++慢得多：

constant $limit = 1_000_000;

my @s = 0,0;
@s.append: 1 xx $limit;

(2 .. $limit/2).race.map: -> $column {
    loop ( my $row = (2 * $column); $row <= $limit; $row += $column ) {
       @s[$row] += $column ;
    }
}

say "s(", $limit, ") = ", @s[$limit] ; # s(1000000) = 1480437

质量分解方法真正发光的是找到 nutyary nutyary 等分的总和。

当反向筛子可能需要几个小时时，这会在一秒钟内产生答案。使用 prime :: factor module ：来自raku生态系统

use Prime::Factor;
say "s(", 2**97-1, ") = ", (2**97-1).&proper-divisors.sum;
# s(158456325028528675187087900671) = 13842607235828485645777841