问题标签 [oeis]

我最近在 OEIS（整数序列在线百科全书）上，试图查找我拥有的特定序列。

现在，这个数据库相当大。该网站称，如果 2006 年（！5 年前）版本印刷，它将占据 750 卷文本。

我确信这也是 Google 必须处理的同一类问题。但是，他们也有一个分布式系统，可以利用负载平衡。

然而，忽略负载平衡，与数据库大小相比，执行查询需要多少时间？

或者换句话说，查询相对于数据库大小的时间复杂度是多少？

编辑：为了使事情更具体，假设输入查询只是查找一串数字，例如：

OEIS 的 A010784 序列是仅包含具有不同数字的数字的序列。这是一个有限的数量。

我一直在尝试做的是在这个序列中找到几个具有某些属性的数字。
例如：6 是 10 等的不同数字。这可以找到如下：

• 6 x 1 = 6
• 6 x 2 = 12
• 6 x 3 = 18
• 6 x 4 = 24
• 6 x 5 = 30
• 6 x 6 = 36
• 6 x 7 = 42
• 6 x 8 = 48
• 6 x 9 = 54
• 6 x 10 = 60
• 6 x 11 = 66（两个六；这些不是两个不同的数字。）

现在我正在尝试几个数量级的最高数字。
假设所有订单从 1 到 20。

我目前正在做的是从可能的最高不同数字（即 9,876,543,210）和 1 级的最高唯一数字循环到一个非常低的数字。
这种方法感觉效率极低。至少，对我来说确实如此。

我很确定我错过了一些关于因式分解应该能够使事情变得更快的东西。

我一直面临着找到这个序列的一般术语或递归关系的挑战

5,18,44,96,195.... 我唯一的提示是这个序列是一个应用的斐波那契序列。有人可以建议找到复发或第n个术语的方法。我查看了 OEIS，但没有发现这个特定整数序列的注释。我搜索了很多地方，但都没有成功。另外，我认为这个序列的项可以用对数时间来确定。任何帮助将不胜感激。

这对我来说是一个相当困难的挑战，因为我是 Python 新手。我将如何根据这个序列函数在 python 中编写程序：

http://oeis.org/A063655

并执行以下操作：

它询问序列的值并返回相应的数字。例如，对应于序列的第 10 个值的数字是 7。我希望能够对超过 300,000,000 的值执行此操作。

因此，最终产品将如下所示：

任何想法从哪里开始？我有一个框架来生成序列，其中 (x) 将放置一个数学方程或数字，但我不确定如何从这里开始或如何实现“输入值”部分：

你得到一个整数 n，你需要找到它在斯特恩双原子序列中第一次出现的索引。

序列定义如下：

见数学世界。

因为 n 可以达到 400000，所以暴力破解它不是一个好主意，特别是因为时间限制是 4000 毫秒。

这个序列很奇怪：8 的第一次出现是 21，但 6 的第一次出现是 33。

任何想法如何解决这个问题？

也许这可能会有所帮助：OEIS

我需要计算滚动 K 骰子可能产生的不同可能掷骰的数量，每个骰子都有 N 面。我对 roll 的定义是 {1, 1, 2, 3, 4} 等价于 {1, 4, 3, 1, 2} （顺序无关紧要），但不等于 {1, 1, 3 , 3, 3} （它们不是同一组结果）。例如：Yahtzee 是一个涉及掷 5 个 6 面骰子的游戏——至少最初是在重新掷骰之前——因此不同掷骰的数量为 252。当 N = K 的情况导致OEIS 序列 A001700。

如果我没记错的话，这是由“（N-1 + K）选择（N-1）”给出的，或者等效地，“（N + K-1）选择K”，它K ! <: K + N在J中。这导致我有四种不同的默认表示：

• d =: ([ ! [: <: +). 简单的火车，没有括号，但我需要使用帽子。
• d =: ([ (! <:) +). 没有上限，但将内钩括起来。
• d =: (] !&<: +). 只有三个动词训练，但使用 Compose。它使用(<: N) ! <: K + N版本。
• d =: (([ ! +) * ] % +). 这个将“C(N+K-1, K)”重写为“C(N+K, K) * N / (N+K)”。它更丑陋，但在 0 面 0 骰子的情况下，它给出的是 0 而不是 1，这可以说是一个不那么荒谬的答案。

其中哪一个是最“J-ish”的解决方案？

此外，所有这些的一元案例是没有意义的：1 0 0 0 0 ...对于前三个和0 1 1 1 ...第四个。这个动词的一个更合乎逻辑的单子是反身，由 给出d~，那么将这个动词定义为 会更好(d~ : d)吗？

问题：

设计一个程序，找出从 1 到 1000 的所有数，其质因数相加时总和为质数（例如，12 的质因数为 2、2 和 3，总和为 7，即质数） . 实现该算法的代码。

我将问题修改为仅对唯一因子求和，因为我不明白为什么您要计算一个因子两次，就像他使用 12 的示例一样。

我的解决方案。有什么好的（阅读：自动化）方法来验证我的程序的输出吗？

1 到 1000 的样本输出：

更新：我已经解决了我的问题并使用OEIS 给定系列验证了我的程序的输出，正如@MVW 所建议的那样（在我的新 github 解决方案给出的源代码中显示）。将来，我的目标是通过执行以下零个或多个（取决于问题的范围/重要性）来测试我的程序：

• 谷歌关键字找到问题的现有解决方案，如果我找到它，将其与我的解决方案进行比较
• 单元测试组件在构建和集成时的正确性，将这些测试与已知的正确输出进行比较

在过去的几天里，我一直在努力让正确安装感到高兴，虽然我发现不仅要解决cabal install happy错误（通过安装happy-1.19和apt-get添加/opt/happy/1.19.3/bin到PATH）具有挑战性，但现在它会贯穿源代码直到它到达ProduceCode(15 /18) 并且似乎进入了一个无限循环。Ctrl+C当整个系统变得无响应时，它会累积内存，直到我点击或关闭电源。

我想我记得这对 GHC-HEAD 根本不是问题，但我不想使用 head，因为它似乎每隔几天更新一次，需要我不断地重建我的包，除非我有什么技巧不知道从 迁移head到head+1。

好的，这里是一个整数序列。在数学堆栈交换中，我了解了这个序列的含义。基本上：

• 给定 n 个项目，a(n) 是您可以创建的三个组的数量，其中没有两个组有多个共同项目。

所以如果你有 7 个项目，用字母 ag 表示，你可以组成这七个组：

'a'并且'b'只一起出现一次，与'a'and'c'和每隔一对相同。

我正在尝试编写一个小程序，可以为我提供任意数量的这些三重奏。现在它适用于一个长度为 n 个字符的字符串。这就是我所拥有的。我认为它很好地解释了自己。

您可以在此处查看正常运行的 JSFiddle。

它适用于七个或更少的字符，给出您期望从序列中获得的三重奏数量。但是超过七个它就坏了。

它输出的三重奏列表总是符合标准，但似乎缺少一些，我不知道在哪里。

整数序列在线百科全书支持搜索包含您的查询作为子序列的序列，例如。搜索subseq:212,364,420,428将返回8*n+4序列。（http://oeis.org/search?q=subseq:212,364,420,428）

这个惊人的功能显然是由 Russ Cox 和http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的，但没有具体说明这是用什么算法实现的。

我想知道它是如何完成的。显然，每次搜索都要经过近一百万个序列对于搜索引擎来说是不切实际的。仅仅保留第一个数字的索引（这就是 Russ Cox 所做的 Google Code Regex Search 的方式）并强制其余的数字也行不通，因为0几乎所有序列中都有类似的数字。事实上，一些查询喜欢0 1匹配整个数据库的很大一部分，所以算法需要一个对所需输出大小敏感的运行时间。

有谁碰巧知道这个功能是如何实现的？