3x+1问题

今天看到一个题在入门版.....
http://www.iteye.com/topic/728160
挪过来看看.

Crusader 写道

3x+1问题，它描述的是这样一个现象：
任取一个自然数，如果它是偶数，就把它除以2，如果它是奇数，就把它乘3再加上1。如此，就得到了一个新的自然数。再按照上述规则反复操作新产生的自然数，我们就会得到一串自然数，而最终得到的自然数序列将陷在4→2→1这个循环中。。。

如 5→16→8→4→2→1→4→2→1。。。
     7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→2→1。。。

这个猜想目前还无法证明，只能穷举，最闲的人已经验证到100*2的50次方。。。

运行的时候，循环改小点，否则估计要运行1千万年左右，应该都活不到那么长吧...

public class _3X1 {
		
	// 是否奇数
	private static boolean isOdd(long i){
		return (i&1L)==1L;
	}
	
	// 判断是否4 | 2 | 1
	private static boolean is_4_2_1(long i){
		return i==4 || i==2 || i==1;
	}
	
	// 判断是否2的次方,如果是,直接断定满足3x+1
	private static boolean isPower2(long i){
		int count = 0;
		while(i>0 && count<2){
			i = i & (i-1L);
			count++;
		}
		return count==1;
	}
	
	// 满足3x+1猜想则返回true,否则死循环
	public static boolean _3x1(long i){
			int flag = 0;
			while(flag<3){
				// 如果是奇数
				if(isOdd(i)){
					i = i*3L+1L;				
				// 如果是偶数
				}else{
					i >>= 1;		
				}
				
				if(is_4_2_1(i)){
					flag++;
				}else{
					flag=0;
				}
			}

		return true;
	}
	
	public static void main(String[] args) {

		for(long i=1; i<Long.MAX_VALUE; i++){

			if(isPower2(i) || _3x1(i)){
				System.out.println(i);
			}

		}

	}

}

评论

6 楼 Crusader 2010-08-06  

抛出异常的爱 写道

不加sysout
用时:1047
你可以试试你的机器上多少

public class _3X1 {  
          
    // 是否奇数  
    private static boolean isOdd(long i){  
        return (i&1L)==1L;  
    }  
       
    // 判断是否2的次方,如果是,直接断定满足3x+1  
    private static boolean isPower2(long i){  
        return 0 == (i & (i-1L));   
    }  
      
    // 满足3x+1猜想则返回true,否则死循环  
    public static boolean _3x1(long i){  
           while(!isPower2(i)){  
                // 如果是奇数  
                if(isOdd(i)){  
                    i += i>>1;
                    i++;
                // 如果是偶数  
                }else{    
                	i >>= 1;        
                }  
 
            }  
           return true;
  
    }  
      
    public static void main(String[] args) {  
        long start = System.currentTimeMillis();  
        for(long i=1; i<1000000L; i++){  
  
            if(_3x1(i)){  
                //System.out.println(i);  
            }  
  
        }  
        System.out.println(System.currentTimeMillis()-start);  
    }  
  
}  

还是要接近3秒，cpu1.8G

5 楼 抛出异常的爱 2010-08-06  

不加sysout
用时:1047
你可以试试你的机器上多少

public class _3X1 {  
          
    // 是否奇数  
    private static boolean isOdd(long i){  
        return (i&1L)==1L;  
    }  
       
    // 判断是否2的次方,如果是,直接断定满足3x+1  
    private static boolean isPower2(long i){  
        return 0 == (i & (i-1L));   
    }  
      
    // 满足3x+1猜想则返回true,否则死循环  
    public static boolean _3x1(long i){  
           while(!isPower2(i)){  
                // 如果是奇数  
                if(isOdd(i)){  
                    i += i>>1;
                    i++;
                // 如果是偶数  
                }else{    
                	i >>= 1;        
                }  
 
            }  
           return true;
  
    }  
      
    public static void main(String[] args) {  
        long start = System.currentTimeMillis();  
        for(long i=1; i<1000000L; i++){  
  
            if(_3x1(i)){  
                //System.out.println(i);  
            }  
  
        }  
        System.out.println(System.currentTimeMillis()-start);  
    }  
  
}  

4 楼 Crusader 2010-08-06  

public class _3X1 {
		
	// 是否奇数
	private static boolean isOdd(long i){
		return (i&1L)==1L;
	}
	
	// 判断是否4 | 2 | 1
	private static boolean is_4_2_1(long i){
		return i==4 || i==2 || i==1;
	}
	
	// 判断是否2的次方,如果是,直接断定满足3x+1
	private static boolean isPower2(long i){
		return 0 == (i & (i-1L)); 
	}
	
	// 满足3x+1猜想则返回true,否则死循环
	public static boolean _3x1(long i){
			int flag = 0;
			while(flag<3){
				// 如果是奇数
				if(isOdd(i)){
					i = i*3L+1L;				
				// 如果是偶数
				}else{
					if(isPower2(i))  
						return true;
					i >>= 1;		
				}
				
				if(is_4_2_1(i)){
					flag++;
				}else{
					flag=0;
				}
			}

		return true;
	}
	
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		for(long i=1; i<1000000L; i++){

			if(_3x1(i)){
				//System.out.println(i);
			}

		}
		System.out.println(System.currentTimeMillis()-start);
	}

}

2890，如果循环加上sysout要28000。。。

3 楼 抛出异常的爱 2010-08-05  

增加cache版
10^6 使用时间4547
效率十倍左右

import java.util.HashSet;
import java.util.Set;

import org.apache.commons.lang.StringUtils;



public class ThreeXone {
	Set cache = new HashSet< Long>();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		ThreeXone x = new ThreeXone();
		x.cache.add(1L);
		long start = System.currentTimeMillis();
		for(int i = 0 ; i <100000 ;i++){
			x.mySelf(i);
		}
		long end = System.currentTimeMillis();
		System.out.println("使用时间"+(end - start) );

	}
	long trimZero(long bin){
		String str = Long.toBinaryString(bin);
		String result = StringUtils.substringBeforeLast(str, "1")+1;
		
		return Long.valueOf(result,2);
	}
	long funcOdd (long odd ){
		odd += odd>>1;
		odd ++;
		return odd;
	}
	void mySelf(long bin ){
		long result = 0;
		//System.out.print(bin+"->");
		long odd = trimZero(bin);
		if(isInMap(odd)){
			//System.out.println();
			return;
		}else{
			result = funcOdd(odd);
			mySelf(result);
			cache.add(bin);
		}
		
		
	}
	boolean isInMap(long odd) {
		
		return cache.contains(odd);
	}

}

2 楼 抛出异常的爱 2010-08-05  

大家如果想用int则录入值不能大于10^5
(会溢出)

1 楼 抛出异常的爱 2010-08-05  

10^5 速度2秒左右
10^6 速度39438

想法.
1,偶数除2等效于二进制去掉尾0
2.奇数乘3必为奇数 再+1必为偶数 等效为 2x + x +1  x左移1 + x +1
如果都除2等效为 x+ x右移1 +1

import org.apache.commons.lang.StringUtils;



public class ThreeXone {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		ThreeXone x = new ThreeXone();
		long start = System.currentTimeMillis();
		for(int i = 0 ; i <10^6 ;i++){
			x.mySelf(i);
		}
		long end = System.currentTimeMillis();
		System.out.println(end - start );

	}
	long trimZero(long bin){
		String str = Long.toBinaryString(bin);
		String result = StringUtils.substringBeforeLast(str, "1")+1;
		
		return Long.valueOf(result,2);
	}
	long funcOdd (long odd ){
		odd += odd>>1;
		odd ++;
		return odd;
	}
	void mySelf(long bin ){
		long result = 0;
		//System.out.print(bin+"--");
		long odd = trimZero(bin);
		if(odd==1){
			//System.out.println();
			return;
		}else{
			result = funcOdd(odd);
			mySelf(result);
		}
		
		
	}

}