论坛 › 难题征解 › 降低一下＂谷角猜想＂的难度

282842712474 发表于 2009-7-28 19:53:52

降低一下＂谷角猜想＂的难度

取任意正整数，如果为奇数，就加1；偶数，就除以2。按照这个法则进行下去，最终结果为1。

想想要如何证明

无心人 发表于 2009-7-28 20:30:25

4n -> n
4n + 1 -> n + 1
4n + 2 -> n + 1
4n + 3 -> n + 1

无心人 发表于 2009-7-28 20:33:14

哦，想复杂了

n >= 1时
2n -> n
2n + 1 -> 2n + 2 -> n + 1
即任何大于1整数，必定在此变换下，最多两步变小
所以...

282842712474 发表于 2009-7-28 20:37:55

简单来说就是要证明：对于大于1的n，经过若干步后必定变小，而到达1后则会陷入循环，所以最终结果为1

无心人 发表于 2009-7-28 20:41:54

对

而角谷猜想则不会找到这个类型的式子
比如
4n -> 2n -> n
4n + 1 -> 12n + 4 -> 6n + 2 -> 3n + 1
4n + 2 -> 2n + 1 -> 6n + 4 -> 3n + 2
4n + 3 -> 12n + 10 -> 6n + 5 -> 18n + 16 -> 9n + 8
此时4n + 3形式数字无法判定是否必然变小

无心人 发表于 2009-7-28 20:45:00

使用非2^k形式的则更麻烦
6n -> 3n
6n + 1 -> 18n + 4 -> 9n + 2(1)
6n + 2 -> 3n + 1
6n + 3 -> 18n + 10 -> 9n + 5 (2)
6n + 4 -> 3n + 2
6n + 5 -> 18n + 16 -> 9n + 8(3)
此时存在3个无法判定的形式

282842712474 发表于 2009-7-28 20:47:00

我们可以证明更细一点，例如：形如16n+3的数就可以经过若干步变小，关键是不能寻找到所有

无心人 发表于 2009-7-28 20:52:20

继续
8n -> 4n -> 2n -> n
8n + 1 -> 24n + 4 -> 12n + 2 -> 6n + 1
8n + 2 -> 4n + 1 -> 12n + 4 -> 6n + 2 -> 3n + 1
8n + 3 -> 24n + 10 -> 12n + 5 -> 36n + 16 -> 18n + 8 -> 9n + 4 (1)
8n + 4 -> 4n + 2 -> 2n + 1 -> 6n + 4 -> 3n + 2
8n + 5 -> 24n + 16 -> 12n + 8 -> 6n + 4 -> 3n + 2
8n + 6 -> 4n + 3 -> 12n + 10 -> 6n + 5 -> 18n + 16 -> 9n + 8 (2)
8n + 7 -> 24n + 22 -> 12n + 11 -> 36n + 34 -> 18n + 17 -> 54n + 52 -> 27n + 26 (3)
也不行

实际上4n + k形式的无法有限步变小是最少的

无心人 发表于 2009-7-28 20:56:55

16n情况只考虑
16n + 3
16n + 6
16n + 9
16n + 15
4种情况

282842712474 发表于 2009-7-28 21:56:37

还有
16n + 1
16n + 5
16n + 13

查看完整版本: 降低一下＂谷角猜想＂的难度