在线整数序列百科全书支持搜索包含您的查询作为子序列的序列,例如.搜索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对谷歌代码正则表达式搜索的方式)的第一个数字和暴力强迫其余的也不起作用,因为数字0几乎在所有序列中.实际上,一些查询0 1匹配总数据库的高百分比,因此算法需要对所需输出大小敏感的运行时间.
有谁碰巧知道这个功能是如何实现的？
你得到一个整数n,你需要在斯特恩的双原子序列中找到它的第一次出现的索引.
序列定义如下:
a[0] = 0
a[1] = 1
a[2*i] = a[i]
a[2*i+1] = a[i] + a[i+1]
参见MathWorld.
因为n可以高达400000,所以强制它不是一个好主意,特别是因为时间限制是4000毫秒.
序列很奇怪:第一次出现8是21,但第一次出现6是33.
任何想法如何解决这个问题？
也许这可能会有所帮助:OEIS
我有兴趣计算三角形序列1,这是一对对的序列,(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ...
它们迭代所有(i, j)具有限制的对i >= j.具有限制i> j的相同序列也是有趣的.
除了其他之外,这些序列表示从n元素集(对于序列直到(n, n)2)或矩阵3的下部三角元素的索引选择2(可能相同)元素的所有方式.i单独的值序列是OEIS中的A003056,而j单独的是A002262.该序列经常出现在组合算法中,其中它们的性能可能是关键的.
在序列中生成下一个值的简单但分支的方法是:
if (i == j) {
j = 0;
i++;
} else {
j++;
}
}
然而,当计算序列的初始元素时,这会在检查条件时遭受许多错误预测(i == j)- 通常每次i增加一次误预测.随着序列的增加,误预测的数量变得越来越低,因为i随着频率的降低而递增,因此j++分支占主导地位且得到很好的预测.尽管如此,某些类型的组合搜索会反复迭代序列中的小项,因此我正在寻找一种无分支方法或其他方法,这些方法可能会减少错误预测.
对于许多用途,序列的顺序并不重要,因此如果它导致更好的解决方案,则生成不同于上述顺序的值是允许的.例如,j可以倒计时而不是倒数:(0, 0), (1, 1), (1, 0), (2, 2), …
language-agnostic performance sequences bit-manipulation oeis
目前,我可以使用以下暴力Prolog代码枚举带根的 平面 未标记二进制树.
e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].
注意:请参阅下面的输出列表.
并使用增加大小输出它们
es(S) :-
length(Ls, _),
phrase(e, Ls), % or e(Ls,[]),
atomic_list_concat(Ls,S).
然而,这是低效的强力算法.
是否有更有效的算法来枚举带根的平面未标记二进制树？
注意:树可以通过使用前两次迭代中的树来生成,想一想Fibonacci数,并添加一元分支或二元分支,但这会导致重复的树.我自己可以做那个版本,我正在寻找的是一种算法,它可以在没有重复的情况下以高效的方式生成树.
注意:二叉树也称为二进制表达式树或K <= 2 的K-ary树.
我对M(15)的暴力版本需要1小时27分钟,而M(15)的高效版本需要大约2秒钟.
显然,有效的算法就是这样,效率更高,为什么我问这个问题.
具有N根节点平面未标记二进制树的节点的树的数量由Motzkin数给出.见:OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
具有N个内部节点的树的数量由带有根的平面未标记二进制树由加泰罗尼亚数字给出.有一种更有效的算法,用于使用加泰罗尼亚数生成有根平面二叉树.
注意:
基于加泰罗尼亚数字的树的数量没有一元分支,只计算内部节点.
而
基于Motzkin数字的树的数量 …
language-agnostic algorithm binary-tree oeis motzkin-numbers
我一直试图让快乐正确安装,在过去几天,虽然我发现它具有挑战性的获得cabal install happy不只是错误(通过安装happy-1.19与apt-get并添加/opt/happy/1.19.3/bin到PATH),现在它通过源运行,直到它到达ProduceCode(15/18)并且似乎进入无限循环.Ctrl+C当整个系统无响应时,它会累积内存,直到我点击或关闭电源.
我想我记得这根本不是GHC-HEAD的问题,但我不想使用头部,因为它似乎每隔几天更新一次,要求我不断重建我的包裹,除非有一个技巧我不要不知道从哪里迁移head到head+1.
$ ghc -v
Glasgow Haskell Compiler, Version 7.8.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /opt/ghc/7.8.2/lib/ghc-7.8.2/package.conf.d/package.cache
Using binary package database: /home/house/.ghc/x86_64-linux-7.8.2/package.conf.d/package.cache
package oeis-0.3.5-26e4c8a4e89d20dbd9e2d89ad4774bd0 is unusable due to missing or recursive dependencies:
HTTP-4000.2.12-2793df5d0fb675f1a42bc04cfdf74851
hiding package Cabal-1.18.1.3 to avoid conflict with later version Cabal-1.20.0
hiding package Cabal-1.19.2 to avoid conflict with later version Cabal-1.20.0
wired-in package …浏览令人敬畏 的整数序列在线百科全书(参见en.wikipedia.org),我偶然发现了以下整数序列:
A031877:非平凡反转数字(数字是其反转的整数倍),不包括回文数和10的倍数.
通过重新使用我为相关问题" 在Prolog中更快地实现语音算法 "的答案而编写的一些代码,我可以毫不费力地写下解决方案 - 感谢clpfd!
:- use_module(library(clpfd)).
我们基于
(先前定义)定义核心关系 :a031877_ndigits_/3digits_number/2
a031877_ndigits_(Z_big,N_digits,[K,Z_small,Z_big]) :-
K #> 1,
length(D_big,N_digits),
reverse(D_small,D_big),
digits_number(D_big,Z_big),
digits_number(D_small,Z_small),
Z_big #= Z_small * K.
核心关系是确定性的,只要是具体的整数,就会
普遍终止N_digit.亲眼看看前100个值N_digit!
?- time((N in 0..99,indomain(N),a031877_ndigits_(Z,N,Zs),false)).
% 3,888,222 inferences, 0.563 CPU in 0.563 seconds (100% CPU, 6903708 Lips)
false
让我们运行一些查询!
?- a031877_ndigits_(87912000000087912,17,_). true % succeeds, as expected ; false. ?- a031877_ndigits_(87912000000987912,17,_). false. % fails, …
我正在尝试使用递归定义来实现Hofstadter的Q序列：
Q(1) = 1
Q(2) = 1
Q(n) = Q(n - Q(n-2)) + Q(n - Q(n-1)) for n > 2
我得到的错误结果n > 3。这是我到目前为止的内容：
: Q recursive
dup 3 <
if
drop 1
else
dup dup 2dup 2 - Q - Q -rot 1- Q - Q +
then ;
在线尝试： http : //ideone.com/PmnJRO（编辑：现在具有固定，正确的实现）
我认为这是行不通的，因为每次调用Qwhere n大于之后，都会向堆栈中添加值2，从而使-rot行不通。
是否有一个简单的调整即可完成这项工作？还是我需要使用其他方法，也许将变量用于n？
OEIS：A005185
oeis ×7
algorithm ×3
performance ×2
binary-tree ×1
cabal ×1
clpfd ×1
forth ×1
gforth ×1
ghc ×1
happy ×1
haskell ×1
optimization ×1
prolog ×1
recursion ×1
search ×1
sequence ×1
sequences ×1
subsequence ×1