由 2x+1、3x+1 和 6x+1 生成的正整数
数列http://oeis.org/A185661
是通过以下方法生成的：
——————————
该数列的第$1$项是$1$。
如果$x$在该数列中，那么把$2x+1$、$3x+1$和$6x+1$加入该数列。
除此之外，该数列不包含其它的正整数。
——————————
问题$1$：
链接里面说该数列的密度是$0$。
也就是说，我们用$f(n)$表示小于或等于$n$的项的数量，那么有$\lim_{n->\infty}f(n)/n=0$。
如何证明这个结论？
问题$2$：
我们用$a(n)$表示该数列的第$n$项。能否用含有$n$的式子近似地表示$a(n)$？
问题$3$：
给定一个正整数$k$，回答$k$是否在数列中的时间复杂度是多少？
（假设运算没有范围限制，对任意大的数进行一次运算的时间复杂度均为$O(1)$） 猜想：
$a(n)=c*n*\ln^p(n)$，其中$c$和$p$是两个待定参数。
回答$k$是否在数列中的期望时间复杂度是$O(\ln(k))$。 很遗憾，我猜错了。
$a(n)$的主要项应该是$c*n^p$，其中$c$和$p$是待定参数，满足$c>0$，$p>1$。
回答$k$是否在数列中的期望时间复杂度可以做到$O(1)$。 又成了根据数据找拟合公式的问题了 假设对于充分大的n,概率为p(n),那么
$1-p(n)=(1-1/2p(n/2))(1-1/3p(n/3))(1-1/6p(n/6))$
由此马上得出如果n趋向无穷$p(n)$极限存在，只能为0 从上面公式看，密度为$log^t(n)$或者说计数为$n/{log^h(n)}$更像 6# mathe
好，回家了我试试这个拟合模式 我原来也是像$5#$那样算概率。
我假设那$3$个事件是相互独立的，于是得到$6#$的结果。
但事实证明那$3$个事件并不相互独立，所以会得到$3#$的结果。 参考文献：
Jeffrey C. Lagarias，Erdős, Klarner, and the $3x+1$ Problem, 美国数学月刊，$2016$年$8$月，第$753$~$776$页。
结论是：
也就是说，该数列不大于$n$的项数只有$O(n^{0.900526...})$项，所以密度为$O(n^{0.900526...}/n)->0$。
导致这一结果的原因如下：
也就是说，因为$1/2+1/3+1/6=1$，所以如果$(2x+1)$、$(3x+1)$、$(6x+1)$互不相干，就可得密度为$O(n^c/n)$，$c->1$。
但是由于$f_2(f_2(f_3(x)))=f_6(f_2(x))=12x+7$，（$f_k(x)=kx+1$），
说明互不相干的假设不成立，$(12x+7)$被重复表示了，
这会引起连锁反应，使得后续一系列的数被重复表示，导致密度大为缩减，
于是$c->1$就不成立了，可以证得$c$的上界只有$0.900526...$。 本帖最后由 qianyb 于 2017-8-23 09:11 编辑
这个密度不是应该是5/9吗
$P=1/2+1/3+1/6-1/2*1/3-1/2*1/6-1/3*1/6+1/2*1/3*1/6$
页:
[1]
2