由 2x+1、3x+1 和 6x+1 生成的正整数

KeyTo9_Fans

数列

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)$）

KeyTo9_Fans

猜想：

$a(n)=c*n*\ln^p(n)$，其中$c$和$p$是两个待定参数。

回答$k$是否在数列中的期望时间复杂度是$O(\ln(k))$。

KeyTo9_Fans

很遗憾，我猜错了。

$a(n)$的主要项应该是$c*n^p$，其中$c$和$p$是待定参数，满足$c>0$，$p>1$。

回答$k$是否在数列中的期望时间复杂度可以做到$O(1)$。

wayne

又成了根据数据找拟合公式的问题了

mathe

假设对于充分大的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

mathe

从上面公式看，密度为$log^t(n)$或者说计数为$n/{log^h(n)}$更像

wayne

6# mathe
好，回家了我试试这个拟合模式

KeyTo9_Fans

我原来也是像$5#$那样算概率。

我假设那$3$个事件是相互独立的，于是得到$6#$的结果。

但事实证明那$3$个事件并不相互独立，所以会得到$3#$的结果。

KeyTo9_Fans

参考文献：

Jeffrey C. Lagarias，Erdős, Klarner, and the $3x+1$ Problem, 美国数学月刊，$2016$年$8$月，第$753$~$776$页。

Erdos_Klarner_and_the_3x 1_Problem.zip (1014.08 KB, 下载次数: 1)

2017-8-22 21:35 上传

点击文件名下载附件

结论是：



也就是说，该数列不大于$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

这个密度不是应该是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$