问题及解答

目前尚不清楚这个循环是否对所有大于1的正整数 $n$ 都会终止.

while(n>1){
	n=T(n);
}

int T(int n){
	if(n%2==0){
		return n/2;
	}else{
		return (3*n+1)/2;
	}
//return (n%2?(3*n+1)/2:n/2);
}

用归纳法证明

\[ T^k(2^k n-1)=3^k n-1,\quad\forall\ k,n>0. \]

3n+1 猜想断言: 对于任意给定的正整数, 经 $T$ 连续作用有限次后均无一例外地落入 $\{4,2,1\}$ 这一数字陷阱.
等价的说法是, 由 $\{1,2,4\}$ 经过 $T$ 的“逆作用” 可以生成所有自然数.

通过复分析研究此猜想已经取得了一些结论, 详见李玉华(云南师范大学)所写的"$3n+1$ 猜想与复解析方法", 见《10000个科学难题(数学卷)》.

20世纪30年代 L.Collatz 为了弄清顶点集是自然数集而有向边 ...

k=1时, 显然成立. 因为 $T(2n-1)=[3(2n-1)+1]/2=3n-1$.

假设对所有n, 有 $T^k(2^k n-1)=3^k-1$. 则

\[T^{k+1}(2^{k+1}n-1)=T(T^k(2^k\cdot 2n-1))=T(3^k\cdot 2n-1)=T(2(3^k n)-1)=3\cdot 3^k\cdot n-1=3^{k+1}n-1.\]

用计算机验证, 对于 n<10000001 都是对的. 即 while 循环能够结束. 更大的数可以考虑使用其他软件验证.

算法有待改进

#include <iostream>
#include <fstream>

using namespace std;

unsigned long int T(unsigned long int n);

void main(){
	ofstream out("terminated.out");
	unsigned long int i,n;//0--4294967295
	for (i=1000001;i<10000001;i++){//注意i不能太大.3i+1应在表示范围内\r
		n=i;
		while(n>1){
			n=T(n);
		}//根据T()的定义,while结束时一定是n=1的时候\r
		//out <<"i="<<i<<endl;
	}
	out<<"Good luck! i="<<i<<endl;
}

unsigned long int T(unsigned long int n){
	if(n%2==0){
		return n/2;
	}else{
		return (3*n+1)/2;//应在unsigned long int	的表示范围内
	}
//return (n%2?(3*n+1)/2:n/2);//a?b:c比if else快\r
}