一般性数字变换问题之一

无心人

假设两素数$p,q$满足$(p, q) = 1$
对任何正整数$n$进行下列变换
1、如果$p | n$，则$n = n / p$，如果$n = 1$则终止。
2、否则$n = q * n + 1$，转步骤1

请问，是否任何组合$p, q$下任何的$n$均在有限步骤内能变换到$1$

gxqcn

这不是“角谷猜想”的推广形式吗？
这么巧妙的推广叙述还是第一次看到。

mathe

我觉得应该不成立，对于大部分(p,q),应该会落在一个不包含1的循环里面。
倒是是否会存在某个(p,q),使得对于某个初试值n,这个迭代过程是否会发散到无穷是个问题

无心人

昨天晚上睡觉的时候
睡不着
发现
$n=2, p=3, q=5$可能会单调上升

所以现在增加一个问题
如果证明有$p, q$组合对$n$的变换不会收敛到$1$
那么是否能找到满足收敛的$p,q$的一般条件？
如果不能，是否能找到满足部分收敛的$p, q, n$的一般条件？

无心人

还有一个问题
是否存在非本题的迭代公式$q*n + k$使得不满足
本题条件的任何$n$均收敛的$p,q$组合达到绝大部分$n$收敛的要求

mathe

可以按概率计算，那么当$q>p^{2/{p-1}+2/{p^2-1}+...+2/{p^t-1}+...}$时，应该会基本上发散到无穷

无心人

怎么得到的结论？

mathe

我们假设某个n不是p的倍数，那么它需要连续使用规则2若干次，比如说k次达到p的倍数，那么这k次递推得到的值可以用递推式写成:
$(n+1/{q-1})q^t-1/{q-1}, t=0,1,2,...,k$
这个式子模p可以写成
$(n+x)q^t-x$的形式，其中$x(q-1)=1(mod p)$
也就是需要$(n+x)q^t=x(mod p)$,我们知道，t最多需要$phi(p)=p-1$次，那么平均来说不会超过${p-1}/2$次。
当然，这个结果是p的倍数的期望次数,也就是每经过一次我们可以认为大概有$2/{p-1}$的概率变成p的倍数。同样有$2/{p^2-1}$的概率是p^2的倍数，等等。
有了这些信息，我们就大概有上面的估计式了，当q大到上面数据时，就应该发散了。
但是不是说只要q要在那个范围才会发散。比如比较特殊的情况:
取$(q-1,p)=1$,但是$p|n(q-1)+1$
那么我们就可以得到$p|(n+x)$但是p不是x的倍数，所以$(n+x)q^t-x$永远不是p的倍数，也就是从这样的n出发，必然会趋向无穷（一直使用规则2）
其实我们可以看出，只要q-1不是p的倍数时，总存在n使得$p|n(q-1)+1$。所以我们得出如果q-1不是p的倍数，必然存在结果发散的初试值

无心人

昨天晚上我也猜测了

是否(3, 7)的组合是比较合适的？

另外有个猜想
假设迭代公式是$q*n + m,  0 < |m|  < p$，是否对所有符合条件的$m$，只要有一个例子发散，就整体发散

mathe

(3,7)选择初试值2计算下去好像就很难收敛，你计算过吗？到底是否收敛？
后面一个猜想我觉得应该不成立，不过要找到反例估计也很难