无心人 发表于 2008-5-14 22:08:34

一般性数字变换问题之一

假设两素数$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 发表于 2008-5-15 07:34:15

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

mathe 发表于 2008-5-15 07:46:32

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

无心人 发表于 2008-5-15 07:54:41

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

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

无心人 发表于 2008-5-15 07:56:55

:)

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

mathe 发表于 2008-5-15 09:10:47

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

无心人 发表于 2008-5-15 13:37:34

:)

怎么得到的结论?

mathe 发表于 2008-5-15 14:01:30

我们假设某个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的倍数,必然存在结果发散的初试值

无心人 发表于 2008-5-15 14:14:48

:)

昨天晚上我也猜测了

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

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

mathe 发表于 2008-5-16 08:27:01

(3,7)选择初试值2计算下去好像就很难收敛,你计算过吗?到底是否收敛?
后面一个猜想我觉得应该不成立,不过要找到反例估计也很难
页: [1] 2
查看完整版本: 一般性数字变换问题之一