如何在 J 中惯用地生成罗兰素数序列？

Question

如果您不熟悉罗兰素数列，可以在此处。我在 J 中创建了一个丑陋的程序单子动词来生成此序列中的前 n 项，如下所示：

rowland =: monad define
    result =. 0 $ 0
    t =. 1 $ 7
    while. (# result) < y do.
        a =. {: t
        n =. 1 + # t
        t =. t , a + n +. a
        d =. | -/ _2 {. t
        if. d > 1 do.
            result =. ~. result , d
        end.
    end.
    result
)

这非常有效，并且它确实生成了第一个 n序列中的项。 （n 个术语，我指的是前 n 个不同素数。）

以下是 rowland 20 的输出：

5 3 11 23 47 101 7 13 233 467 941 1889 3779 7559 15131 53 30323 60647 121403 242807

我的问题是，如何用更惯用的 J 语言编写这个？我没有任何线索，尽管我确实编写了以下函数来查找数字列表中每个连续数字之间的差异，这是必需的步骤之一。就是这样，尽管它也可能由比我更有经验的 J 程序员重构：

diffs =: monad : '}: (|@-/@(2&{.) , $:@}.) ^: (1 < #) y'

Answer 1

虽然我已经将埃斯坦福德的答案标记为正确的答案，但自从我提出这个问题以来，我已经与 J 取得了长足的进步。下面是在 J 中生成罗兰素数序列的更惯用的方法：

~. (#~ 1&<) | 2 -/\ (, ({: + ({: +. >:@#)))^:(1000 - #) 7

表达式 (, ({: + ({: +. >:@#)))^:(1000 - #) 7 生成最多 1000 个成员的所谓原始序列。该序列的第一个差异可以通过 | 生成2 -/\，即每两个元素之差的绝对值。 （将其与原始问题中我原来的冗长 diffs 动词进行比较。）

最后，我们删除那些和重复的素数 ~。 (#~ 1&<) 获取素数序列。

这比我之前的做法要好得多。它可以很容易地变成一个动词，通过一点递归来生成 n 个素数。

Answer 2

我还没有完整的答案，但是这篇文章作者：Roger Hui有一个默认构造，您可以使用它来替换显式的 while 循环。另一个（相关的）途径是将块的内部逻辑变成一个默认表达式，如下所示：（

FUNWITHTACIT =: ] , {: + {: +. 1 + #
rowland =: monad define
    result =. >a:
    t =. 7x
    while. (# result) < y do.
      t =. FUNWITHTACIT t
      d =.  | -/ _2 {. t
      result =. ~.result,((d>1)#d)
    end.
    result
)

不过，为了提高效率，您可能希望保留 if 块，因为我以 result 的方式编写代码无论是否满足条件，都会修改 - 如果不满足，则修改无效。 if 逻辑甚至可以通过使用写回到默认表达式中。议程运算符。）

完整的解决方案包括找出如何将 while 循环内的所有逻辑表示为单个函数，然后使用 Roger 的技巧将 while 逻辑实现为默认表达式。我会看看我能找到什么。

顺便说一句，我让 J 为我构建了 FUNWITHTACIT，方法是获取代码的前几行，手动替换您声明的变量值的函数（我可以这样做，因为它们都在操作）以不同的方式对单个参数进行处理），将 t 的每个实例替换为 y 并告诉 J 构建结果表达式的默认等价物：

]FUNWITHTACIT =: 13 : 'y,({:y)+(1+#y)+.({:y)'
   ] , {: + {: +. 1 + #

使用 13 声明 monad 是J 如何知道采用 monad（否则使用 3 : 0 显式声明，或如您在程序中编写的 monad Define）并将显式表达式转换为默认表达式。

编辑：

这是我在评论中提到的为 Avenue (2) 编写的函数：

candfun =: 3 : '(] , {: + {: +. 1 + #)^:(y) 7'
firstdiff =: [: | 2 -/\ ]
triage =: [: /:~ [: ~. 1&~: # ]
rowland2 =: triage @firstdiff @candfun

该函数使用 Rowland 递归关系生成前 n 个候选数字，评估它们的一阶差异，丢弃所有等于 1 的一阶差异，丢弃所有重复项，并按升序对它们进行排序。我认为这还不是完全令人满意，因为该参数设置了要尝试的候选人数量而不是结果数量。但是，这仍然是进步。

示例：

   rowland2 1000
3 5 7 11 13 23 47 101 233 467 941

这是我发布的第一个函数的一个版本，将每个参数的大小保持在最小值：

NB. rowrec takes y=(n,an) where n is the index and a(n) is the
NB. nth member of the rowland candidate sequence. The base case
NB. is rowrec 1 7. The output is (n+1,a(n+1)).
rowrec =: (1 + {.) , }. + [: +./ 1 0 + ]

rowland3 =: 3 : 0
 result =. >a:
 t =. 1 7
 while. y > #result do.
  ts =. (<"1)2 2 $ t,rowrec t
  fdiff =. |2-/\,>(}.&.>) ts
  if. 1~:fdiff do.
   result =. ~. result,fdiff
  end.
  t =. ,>}.ts
 end.
 /:~ result
) 

它找到前 y 个不同的罗兰素数并按升序呈现它们：

   rowland3 20
3 5 7 11 13 23 47 53 101 233 467 941 1889 3779 7559 15131 30323 60647 121403 242807

这个函数的大部分复杂性来自我的处理盒装数组。这不是漂亮的代码，但它只在计算过程中将 4+#result 许多数据元素（以对数比例增长）保留在内存中。原始函数 rowland 将 (#t)+(#result) 元素保留在内存中（按线性比例增长）。 rowland2 y 构建一个包含 y 多个元素的数组，这使得它的内存配置文件几乎与 rowland 相同，尽管它的增长永远不会超出指定范围边界。我喜欢 rowland2 的紧凑性，但没有公式来预测生成 n 个不同素数所需的 y 的确切大小，该任务需要在试错法，因此在冗余计算上可能使用比 rowland 或 rowland3 更多的周期。 rowland3 可能比我的 rowland 版本更高效，因为 FUNWITHTACIT 在每次循环迭代时重新计算 #t -- rowland3 只是增加一个计数器，计算强度较小。

尽管如此，我对 rowland3 的显式控制结构并不满意。似乎应该有一种方法可以使用递归或其他方法来完成此行为。